《离散数学 图的矩阵表示》由会员分享，可在线阅读，更多相关《离散数学 图的矩阵表示（25页珍藏版）》请在金锄头文库上搜索。
1、7.3 图的矩阵表示 无向图的关联矩阵 有向图的关联矩阵 有向图的邻接矩阵 有向图的可达矩阵 1无向图的关联矩阵定义 设无向图G=, V=v1, v2, , vn, E=e1, e2, , em, 令mij为vi与ej的关联次数，称(mij)nm为G的关联矩阵，记为M(G). 2例:求下图G的关联矩阵l上图G的关联矩阵:3无向图的关联矩阵性质：（5） 当且仅当vi为孤立点。4有向图的关联矩阵定义 设无环有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令则称(mij)nm为D的关联矩阵，记为M(D).5n例: 求图G的关联矩阵。l 上图G的关联矩阵:6有向图的关联矩
2、阵(续)性质(4) 平行边对应的列相同7定义 设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令 为顶点vi邻接到顶点vj边的条数，称( )mn为D的邻接矩阵, 记作A(D), 简记为A. 有向图的邻接矩阵8n求下图G的邻接矩阵。l解 上图G的邻接矩阵。给出了图G的邻接矩阵，就等于给出了图G的全部信息。图的性质可以由矩阵 A通过运算而获得。 9定义 设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令 为顶点vi邻接到顶点vj边的条数，称( )mn为D的邻接矩阵, 记作A(D), 简记为A. 性质有向图的邻接矩阵10D中的通路及回路
3、数定理 设A为n阶有向图D的邻接矩阵, 则Al(l1)中元素为D中vi到vj长度为 l 的通路数，为vi到自身长度为 l 的回路数，为D中长度为 l 的通路总数，为D中长度为 l 的回路总数. 11D中的通路及回路数(续)例 有向图D如图所示, 求A, A2, A3, A4, 并回答诸问题： (1) D中长度为1, 2, 3, 4的通路各有多少条？其中回路分别为多少条？ (2) D中长度小于或等于4的通路为多少条？其中有多少条回路？ 推论 设Bl=A+A2+Al(l1), 则Bl中元素为D中长度小于或等于l 的通路数，为D中长度小于或等于l 的回路数.12例(续)长度 通路 回路 合计 50
4、818 1 211 3 314 1 417 313在下图中v1到v3长度为1、2、3、4的通路分别有 多少条，G中共有长度为4的通路多少条，其中回路 多少条，长度小于等于4的通路共有多少条，其中 回路多少条。14l解:因为 15l 所以，由v1到v3长度为1、2、3、4的通 路分别有0、2、2、4条，G中共有长度为 4的通路43条，其中回路11条，长度小于 等于4的通路共有87条，其中回路22条。l 注 无向图也有相应的邻接矩阵，一般只 考虑简单图，无向图的邻接矩阵是对称的 ，其性质基本与有向图邻接矩阵的性质相 同。16例如:下图邻接矩阵为： 17有向图的可达矩阵称(pij)nn为D的可达矩阵
5、, 记作P(D), 简记为P. 性质:P(D)主对角线上的元素全为1. D强连通当且仅当P(D)的元素全为1.定义 设D=为有向图, V=v1, v2, , vn, 令18有向图的可达矩阵(续)例 右图所示的有向图D的可达矩阵为19设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+A n-1 =(b ij ) nn 其中 E 是单位矩阵。则20
6、图9.24邻接矩阵A和A2，A3，A4如下：2122则图G的可达性矩阵 B= A0AA2A3A4 = P= 23可达性矩阵用来描述有向图的一个结点到另 一个结点是否有路，即是否可达。无向图也 可以用矩阵描述一个结点到另一个结点是否 有路。在无向图中，如果结点之间有路，称 这两个结点连通，不叫可达。所以把描述一 个结点到另一个结点是否有路的矩阵叫连通 矩阵，而不叫可达性矩阵。 24定义 设G=V,E是简单无向图，V=v1,v2,vnP(G)=( pij) nn其中：i,j=1,n称P(G)为G的连通矩阵。简记为P。无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵。求连通矩阵的方法与可达性矩阵类似。 25
