离散数学 图的矩阵表示

17.3图的矩阵表示无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的可达矩阵2无向图的关联矩阵定义设无向图G=V,E,V={v1,v2,…,vn},E={e1,e2,…,em},令mij为vi与ej的关联次数，称(mij)nm为G的关联矩阵，记为M(G).3e1e2e3e4e51234例:求下图G的关联矩阵上图G的关联矩阵:12342100001110()0011100001MG12345eeeee4无向图的关联矩阵平行边的列相同)4(2)3(),...,2,1()()2(),...,2,1(2)1(,11mmnivdmmjmjiijimjijniij性质：（5）当且仅当vi为孤立点。mjijm1,05有向图的关联矩阵的终点为，不关联与，的始点为jijijiijevevevm10,1定义设无环有向图D=V,E,V={v1,v2,…,vn},E={e1,e2,…,em},令则称(mij)nm为D的关联矩阵，记为M(D).6e5e6e3e2e1e453412例:求图G的关联矩阵。上图G的关联矩阵:12345100000111100()011011000111000000MG123456eeeeee7有向图的关联矩阵(续)jiijmjiijmjiijniijmnivdmvdmmjm,1110)3(,...,2,1),()1(),()1()2(),...,2,1(0)1(性质(4)平行边对应的列相同8定义设有向图D=V,E,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记为A.)1(ija)1(ija有向图的邻接矩阵92341求下图G的邻接矩阵。解上图G的邻接矩阵。12000010()10010010AG给出了图G的邻接矩阵，就等于给出了图G的全部信息。图的性质可以由矩阵A通过运算而获得。10定义设有向图D=V,E,V={v1,v2,…,vn},E={e1,e2,…,em},令为顶点vi邻接到顶点vj边的条数，称()mn为D的邻接矩阵,记作A(D),简记为A.性质的回路数中长度为的通路数中长度为1)4(1)3(,...,2,1),()2(,...,2,1),()1(1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij)1(ija)1(ija有向图的邻接矩阵11D中的通路及回路数)(lija)(liianinjlija11)(niliia1)(定理设A为n阶有向图D的邻接矩阵,则Al(l1)中元素为D中vi到vj长度为l的通路数，为vi到自身长度为l的回路数，为D中长度为l的通路总数，为D中长度为l的回路总数.12D中的通路及回路数(续)例有向图D如图所示,求A,A2,A3,A4,并回答诸问题：(1)D中长度为1,2,3,4的通路各有多少条？其中回路分别为多少条？(2)D中长度小于或等于4的通路为多少条？其中有多少条回路？ninjlijb11)(niliib1)(推论设Bl=A+A2+…+Al(l1),则Bl中元素为D中长度小于或等于l的通路数，为D中长度小于或等于l的回路数.13例(续)长度通路回路1004010410050001010310030104000110020102100300010101100101020001432AAAA合计508181211331414173演示文稿后等共创共赢共创共赢团队忈莒昈152341在下图中v1到v3长度为1、2、3、4的通路分别有多少条，G中共有长度为4的通路多少条，其中回路多少条，长度小于等于4的通路共有多少条，其中回路多少条。16解:因为23412001200122000100010100110011001121000100010100132225642121022212221443212102221AAA17所以，由v1到v3长度为1、2、3、4的通路分别有0、2、2、4条，G中共有长度为4的通路43条，其中回路11条，长度小于等于4的通路共有87条，其中回路22条。注无向图也有相应的邻接矩阵，一般只考虑简单图，无向图的邻接矩阵是对称的，其性质基本与有向图邻接矩阵的性质相同。180111101011011010)(GA例如:下图邻接矩阵为：19有向图的可达矩阵1,0,ijijvvp可达否则称(pij)nn为D的可达矩阵,记作P(D),简记为P.性质:P(D)主对角线上的元素全为1.D强连通当且仅当P(D)的元素全为1.定义设D=V,E为有向图,V={v1,v2,…,vn},令20有向图的可达矩阵(续)例右图所示的有向图D的可达矩阵为1101110111110001P21设G=V,E是n阶简单有向图，V={v1,v2,…,vn}，由可达性矩阵的定义知，当i≠j时，如果vi到vj有路，则pij=1；如果vi到vj无通路，则pij=0；又如果vi到vj有通路，则必存在长度小于等于n–1的通路。又n阶图中，任何回路的长度不大于n，如下计算图G的可达性矩阵P：B=E+A+A2+…+An-1=(bij)n×n其中E是单位矩阵。则1000ijijijbpb22图9.24邻接矩阵A和A2，A3，A4如下：0100010000000100010100010A2301000100000002000202000203A10000010000020200040002024A10000010000010100020001012A24则图G的可达性矩阵B=A0＋A＋A2＋A3＋A4=31000130000043300373003341100011000001110011100111P=25可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。26定义设G=V,E是简单无向图，V={v1,v2,…,vn}P(G)=(pij)n×n其中：i,j=1,…,n称P(G)为G的连通矩阵。简记为P。无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵。求连通矩阵的方法与可达性矩阵类似。01不连通与连通与　jijiijvvvvp