离散数学 图的矩阵表示

1、1,7.3图的矩阵表示,无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵,2,无向图的关联矩阵,定义设无向图G=,V=v1,v2,vn,E=e1,e2,em,令mij为vi与ej的关联次数，称(mij)nm为G的关联矩阵，记为M(G).,3,例:求下图G的关联矩阵,上图G的关联矩阵:,4,无向图的关联矩阵,性质：,（5）当且仅当vi为孤立点。,5,有向图的关联矩阵,定义设无环有向图D=,V=v1,v2,vn,E=e1,e2,em,令则称(mij)nm为D的关联矩阵，记为M(D).,6,例:求图G的关联矩阵。,上图G的关联矩阵:,7,有向图的关联矩阵(续),性质(4)平行边对应的

2、列相同,8,定义设有向图D=,V=v1,v2,vn,E=e1,e2,em,令为顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记为A.,有向图的邻接矩阵,9,求下图G的邻接矩阵。,解上图G的邻接矩阵。,给出了图G的邻接矩阵，就等于给出了图G的全部信息。图的性质可以由矩阵A通过运算而获得。,10,定义设有向图D=,V=v1,v2,vn,E=e1,e2,em,令为顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记为A.性质,有向图的邻接矩阵,11,D中的通路及回路数,定理设A为n阶有向图D的邻接矩阵,则Al(l1)中元素为D中vi到vj长度为l的

3、通路数，为vi到自身长度为l的回路数，为D中长度为l的通路总数，为D中长度为l的回路总数.,12,D中的通路及回路数(续),例有向图D如图所示,求A,A2,A3,A4,并回答诸问题：(1)D中长度为1,2,3,4的通路各有多少条？其中回路分别为多少条？(2)D中长度小于或等于4的通路为多少条？其中有多少条回路？,推论设Bl=A+A2+Al(l1),则Bl中元素为D中长度小于或等于l的通路数，为D中长度小于或等于l的回路数.,13,例(续),长度通路回路,合计508,1,81,2,113,3,141,4,173,演示文稿后等,共创共赢,15,在下图中v1到v3长度为1、2、3、4的通路分别有多少

4、条，G中共有长度为4的通路多少条，其中回路多少条，长度小于等于4的通路共有多少条，其中回路多少条。,16,解:因为,17,所以，由v1到v3长度为1、2、3、4的通路分别有0、2、2、4条，G中共有长度为4的通路43条，其中回路11条，长度小于等于4的通路共有87条，其中回路22条。注无向图也有相应的邻接矩阵，一般只考虑简单图，无向图的邻接矩阵是对称的，其性质基本与有向图邻接矩阵的性质相同。,18,例如:下图邻接矩阵为：,19,有向图的可达矩阵,称(pij)nn为D的可达矩阵,记作P(D),简记为P.性质:P(D)主对角线上的元素全为1.D强连通当且仅当P(D)的元素全为1.,定义设D=为有向

5、图,V=v1,v2,vn,令,20,有向图的可达矩阵(续),例右图所示的有向图D的可达矩阵为,21,设G=V,E是n阶简单有向图，V=v1,v2,vn，由可达性矩阵的定义知，当ij时，如果vi到vj有路，则pij=1；如果vi到vj无通路，则pij=0；又如果vi到vj有通路，则必存在长度小于等于n1的通路。又n阶图中，任何回路的长度不大于n，如下计算图G的可达性矩阵P：B=E+A+A2+An-1=(bij)nn其中E是单位矩阵。则,22,图9.24邻接矩阵A和A2，A3，A4如下：,23,24,则图G的可达性矩阵,B=A0AA2A3A4=,P=,25,可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。,26,定义设G=V,E是简单无向图，V=v1,v2,v