离散结构课件6章图论基础

16.3图的矩阵表示6.3.1无向图的关联矩阵6.3.2有向无环图的关联矩阵6.3.3有向图的邻接矩阵有向图中的通路数与回路数6.3.4有向图的可达矩阵2无向图的关联矩阵设无向图G=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}.

令mij为vi与ej的关联次数,称(mij)nm为G的关联矩阵,记为M(G).mij的可能取值为:0,1,2例如e1e2e3e4e5e6v5v1v2v3v4M(G)=2110000101110000110000000011003关联矩阵的性质(6)ej是环第j列的一个元素为2,其余为0(5)vi是孤立点第i行全为04无环有向图的关联矩阵则称(mij)nm为D的关联矩阵,记为M(D).设无环有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em}.令(3)ej与ek是平行边

第j列与第k列相同(2)第i行1的个数等于d+(v),第i行1的个数等于d(v)性质:5实例v1v2v3v4e2e1e3e4e5e6e7M(D)=–

11000–110–11000000

–1

–1

–11–1100110

06有向图的邻接矩阵设有向图D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()nn为D的邻接矩阵,记作A(D),简记作A.7实例A=1100001010001020v1v2v3v48有向图中的通路数与回路数定理6.6设A为n阶有向图D的邻接矩阵,则Al(l1)中元素等于D中vi到vj长度为l的通路(含回路)数,等于vi到自身长度为l的回路数,等于D中长度为l的通路(含回路)总数,等于D中长度为l的回路总数.9有向图中的通路数与回路数(续)推论设Bl=A+A2+…+Al(l1),则Bl中元素等于D中vi到vj长度小于等于l的通路(含回路)数,等于D中vi到vi的长度小于等于l的回路数,等于D中长度小于等于l的通路(含回路)数,为D中长度小于等于l的回路数.10实例A=1100001010001020v1v2v3v411实例

说明:在这里,通路和回路数是定义意义下的A=1100001010001020A2=1110100011003100A3=2110110011003310A4=3210110021104310v1到v2长为3的通路有1条v1到v3长为3的通路有1条v1到自身长为3的回路有2条D中长为3的通路共有15条,其中回路3条v1v2v3v412有向图的可达矩阵性质:P(D)主对角线上的元素pii全为1.D强连通当且仅当P(D)的元素全为1.设有向图D=<V,E>,V={v1,v2,…,vn},令

称(pij)nn为D的可达矩阵,记作P(D),简记为P.13实例例6.11(1)v1到v4,v4到v1长为3的通路各有多少条?(2)v1到自身长为1,2,3,4的回路各有多少条?(3)长为4的通路共有多少条?其中有多少条回路?(4)长度小于等于4的回路共有多少条?(5)写出D的可达矩阵,并问D是强连通的吗?解v1v2v3v4A=121000100001001014实例(续)v1到v4长为3的通路有条,A2=1231000100100001A3=1243001000010010A4=12640001001000013v4到v1长为3的通路有条0v1到自身长为1,2,3,4的回路各有条1长为4的通路共有条，其中有条回路163长度小于等于4的回路共有条8可达矩阵非强连通,单连通P=1111011100110011A