离散数学 图的矩阵表示

1、17.3 图的矩阵表示图的矩阵表示 无向图的关联矩阵无向图的关联矩阵有向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵有向图的邻接矩阵有向图的可达矩阵有向图的可达矩阵 2无向图的关联矩阵无向图的关联矩阵定义定义 设无向图设无向图G=, V=v1, v2, , vn, E=e1, e2, , em, 令令mij为为vi与与ej的关联次数，称的关联次数，称(mij)n m为为G的关联矩阵的关联矩阵，记为，记为M(G). 3e1e2e3e4e51234 例例:求下图求下图G的关联矩阵的关联矩阵l上图上图G的关联矩阵的关联矩阵:12342100001110( )0011100001M G12345eee

2、ee4无向图的关联矩阵无向图的关联矩阵平行边的列相同平行边的列相同)4(2)3(),.,2 , 1()()2(),.,2 , 1(2)1(,11mmnivdmmjmjiijimjijniij 性质：（5） 当且仅当当且仅当vi为孤立点。为孤立点。mjijm1, 05有向图的关联矩阵有向图的关联矩阵 的终点的终点为为，不关联不关联与与，的始点的始点为为jijijiijevevevm10,1定义定义 设无环有向图设无环有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 则称则称(mij)n m为为D的关联矩阵的关联矩阵，记为，记为M(D).6e5e6e3e2e1e4

3、53412n例例: 求图求图G的关联矩阵。的关联矩阵。l 上图上图G的关联矩阵的关联矩阵:12345100000111100( )011011000111000000M G123456e ee ee e7有向图的关联矩阵有向图的关联矩阵( (续续) ) jiijmjiijmjiijniijmnivdmvdmmjm,1110)3(,.,2 , 1),()1(),()1()2(),.,2 , 1(0)1(性质性质 (4) 平行边对应的列相同平行边对应的列相同8定义定义 设有向图设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 为顶点为顶点vi邻接到顶点邻接到顶点

4、vj边的条数，边的条数，称称( )m n为为D的邻接矩阵的邻接矩阵, 记作记作A(D), 简记为简记为A. )1(ija)1(ija有向图的邻接矩阵有向图的邻接矩阵 92341n求下图求下图G的邻接矩阵的邻接矩阵。l解解 上图上图G的邻接矩阵。的邻接矩阵。12000010()10010010A G 给出了图给出了图G的邻接矩阵，就等于给出了图的邻接矩阵，就等于给出了图G的全部的全部信息。图的性质可以由矩阵信息。图的性质可以由矩阵 A通过运算而获得通过运算而获得。 10定义定义 设有向图设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 为顶点为顶点vi邻接到顶

5、点邻接到顶点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有向图的邻接矩阵有向图的邻接矩阵 11 D中的通路及回路数中的通路及回路数)(lija)(liia ninjlija11)( niliia1)(定理定理 设设A为为n阶有向图阶有向图D的邻接矩阵的邻接矩阵, 则则

6、Al(l 1)中中元素元素 为为D中中vi到到vj长度为长度为 l 的通路数，的通路数， 为为vi到自身长度为到自身长度为 l 的回路数，的回路数， 为为D中长度为中长度为 l 的通路总数，的通路总数， 为为D中长度为中长度为 l 的回路总数的回路总数. 演 示 文 稿1 23 后 等费洛蒙香水 费洛蒙香水 岙奣尛13D中的通路及回路数中的通路及回路数(续续)例例 有向图有向图D如图所示如图所示, 求求A, A2, A3, A4, 并回答诸问题：并回答诸问题：(1) D中长度为中长度为1, 2, 3, 4的通路各有多的通路各有多 少条？其中回路分别为多少条？少条？其中回路分别为多少条？(2)

7、D中长度小于或等于中长度小于或等于4的通路为多的通路为多 少条？其中有多少条回路？少条？其中有多少条回路？ ninjlijb11)( niliib1)(推论推论 设设Bl=A+A2+Al(l 1), 则则Bl中元素中元素 为为D中长度小于或等于中长度小于或等于l 的通路数，的通路数， 为为D中长度小于或等于中长度小于或等于l 的回路数的回路数.14例(续) 长度长度 通路通路 回路回路 1004010410050001010310030104000110020102100300010101100101020001432AAAA合计合计 50 818 1211 3314 1417 3152341

8、在下图中在下图中v1到到v3长度为长度为1、2、3、4的通路分别有的通路分别有多少条，多少条，G中共有长度为中共有长度为4的通路多少条，其中回的通路多少条，其中回路多少条，长度小于等于路多少条，长度小于等于4的通路共有多少条，其的通路共有多少条，其中回路多少条。中回路多少条。16l解解:因为因为 23412001200122000100010100110011001121000100010100132225642121022212221443212102221AAA17l 所以，由所以，由v1到到v3长度为长度为1、2、3、4的通路的通路分别有分别有0、2、2、4条，条，G中共有长度为中共有长

9、度为4的的通路通路43条，其中回路条，其中回路11条，长度小于等于条，长度小于等于4的通路共有的通路共有87条，其中回路条，其中回路22条。条。l 注注 无向图也有相应的邻接矩阵，一般只考无向图也有相应的邻接矩阵，一般只考虑简单图，无向图的邻接矩阵是对称的，虑简单图，无向图的邻接矩阵是对称的，其性质基本与有向图邻接矩阵的性质相同。其性质基本与有向图邻接矩阵的性质相同。180111101011011010)(GA 例如例如: :下图邻接矩阵为：下图邻接矩阵为： 19有向图的可达矩阵有向图的可达矩阵 1,0,ijijvvp可达否则称称(pij)n n为为D的可达矩阵的可达矩阵, 记作记作P(D),

10、 简记为简记为P. 性质性质: P(D)主对角线上的元素全为主对角线上的元素全为1. D强连通当且仅当强连通当且仅当P(D)的元素全为的元素全为1.定义定义 设设D=为有向图为有向图, V=v1, v2, , vn, 令令20有向图的可达矩阵(续)例例 右图所示的有向图右图所示的有向图D的可达矩阵为的可达矩阵为 1101110111110001P21 设设G= V,E 是是n阶简单有向图，阶简单有向图，V=v1,v2,vn，由可达性矩阵的定义知，当由可达性矩阵的定义知，当ij时，如果时，如果vi到到vj有路，有路，则则pij=1；如果；如果vi到到vj无通路，则无通路，则pij=0；又如果；又

11、如果vi到到vj有通路，则必存在长度小于等于有通路，则必存在长度小于等于n1的通路。的通路。又又n阶图中，任何回路的长度不大于阶图中，任何回路的长度不大于n ，如下计算图，如下计算图G的可达性矩阵的可达性矩阵P： B=E+A+A2+A n-1 =(b ij ) nn 其中其中 E 是单位矩阵。则是单位矩阵。则1000ijijijbpb22 图图9.24邻接矩阵邻接矩阵A和和A2，A3，A4如下：如下：0100010000000100010100010A 2301000100000002000202000203A10000010000020200040002024A 10000010000010

12、100020001012A24则图则图G的可达性矩阵的可达性矩阵 B= A0AA2A3A4 = 31000130000043300373003341100011000001110011100111 P= 25可达性矩阵用来描述有向图的一个结点到另可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称有路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。矩阵，而不叫可达性矩阵。 26 定义定义 设设G= V,E