图的矩阵表示ppt课件.ppt

《图的矩阵表示ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图的矩阵表示中国海洋大学计算机系主要内容邻接矩阵有向图的可达矩阵无向图的关联矩阵有向图的关联矩阵图的运算学习要点与基本要求实例分析邻接矩阵定义7-3.1设G=是一个简单图，它有n个结点V={v1,v2,…,vn},则n阶方阵A(G)=(aij)称为G的邻接矩阵。其中adj表示邻接，nadj表示不邻接。邻接矩阵的举例求下图的邻接矩阵邻接矩阵的性质无向简单图的邻接矩阵是对称的；有向图的邻接矩阵不一定对称。邻接矩阵与结点的标定顺序有关，不同标定顺序对应的邻接矩阵是彼此置换等价的。在无向图的邻接矩阵中，第i行中非零元的个数等于vi的度，第i列中非零元的个数等于vi的度。在有向图

2、的邻接矩阵中，第i行中所有元素之和等于vi的出度，第i列中所有元素之和等于vi的入度。利用图的邻接矩阵可以计算任意两结点间特定长度的路的数目。利用邻接矩阵计算路的数目设有向图G的结点集合V={v1,v2,…,vn},它的邻接矩阵为A(G)=(aij)n×n。下面讨论某一长度的路的数目。这里路是定义意义下的概念，即不同起点的路都看成不同的。(1)A(G)中所有元素之和为G中长度为1的路的数目。(2)G中有长度为2的路vivkvj存在aik=akj=1，所以从结点vi到结点vj的长度为2的路的数目等于利用邻接矩阵计算路的数目从vi到vj的长度为l的路，可以看成是由vi到vk的一条长

3、度为1的路和vk到vj的一条长度为l-1的路合成，所以vi到vj的长度为l的路的数目为：长度为l的路的数目的求法定理7-3.1设A(G)是图G的邻接矩阵，则(A(G))l中的i行，j列元素aij(l)等于G中联结vi与vj的长度为l的路的数目。证明对l用数学归法当l=2时，由上可知显然成立。设命题对l成立，由(A(G))l+1=A(G)(A(G))l故定理7-3.1的证明aik表示联结vi与vk的长度为1的路的数目，akj(l)是联结vk与vj的长度为l的路的数目，故上式右边的每一项表示由vi与经过一条边到vk，再由vk经过一条长度为l的路到vj的总长度为l+1的路，对所有k求

4、和，即得akj(l+1)是所有从vi到vj的长度为l+1的路的数目，故命题成立。实例1例1给定图G=，求v1到v3的长度为1,2,3,4的路的数目。经过v2的回路共有多少条？实例1（续）v1到v3的长度为1的路有0条v1到v3的长度为2的路有1条v1到v3的长度为3的路有0条v1到v3的长度为4的路有2条经过v2的回路共有a22(2)+a22(3)+a22(4)=2+0+4=6可达性矩阵定义7-3.2令G=是一个简单有向图，

5、V

6、=n，假定G的结点已编序，即V={v1,v2,…,vn},定义一个n×n矩阵P=(pij)。其中称矩阵P是图G的可达性矩阵。关于可达

7、矩阵的说明可达性矩阵描述任意两结点是否可达，以及对于任意结点是否有通过它的回路。由邻接矩阵A可直接得到可达性矩阵P，方法如下：方法1：Bn=A+A2+…An，再把Bn中的非零元均改为1，零元保持不变，得到可达性矩阵P。方法2：把Ai(i=1,2,…,n)中的非零元改为1，零元保持不变，得到布尔矩阵A(i)(i=1,2,…,n)，P=A(1)∨A(2)∨…∨A(n)实例2例2求下图的可达矩阵。解如果图中两结点存在路，那么一定存在长度小于n-1的路，考虑到自身到自身的可达性，只须计算到An为止。由例1可得邻接矩阵A、A2、A3、A4.实例2（续）根据例1的结果，可得实例2（续）使用方

8、法二：把Ai(i=1,2,…,n)中的非零元改为1.实例2（续）P=A(1)∨A(2)∨A(3)∨A(4)∨A(5)利用Warshall算法求P方法3：可用Warshall算法计算。邻接矩阵可以看成V上的关系R的关系矩阵MR，vi,vj∈V，viRvj∈E因此，求可达性矩阵就是求R的传递闭包MR+。注意：上述的结论也适用于无向图，把无向图的每一条边看成双向边即可。实例2A(2,1)=1(2)+(1)→(1)A(1,2)=A(3,2)=1(1)+(2)→(2)(3)+(2)→(2)A(1,3)=A(2,3)=1(1)+(3)→(3)(2)+(3)→(3)实例2A(

9、5,4)=1(5)+(4)→(4)A(4,5)=1(4)+(5)→(5)无向图的完全关联矩阵定义7-3.3给定无向图G，令v1,v2,…,vp,e1,e2,…,eq分别记为M(G)的结点和边，则矩阵M(G)=(mij)p×q，其中称M(G)为完全关联矩阵。实例3例3求下图的完全关联矩阵。e1e2e3e4e5e6v1110011v2111000v3001101v4000110v5000000关联矩阵的性质1.M(G)中每一列只有两个非零元。2.每一行中所有元素的和是对应结点的度数。