- 图的矩阵表示9.pptVIP

图的矩阵表示 中国海洋大学 计算机系 主要内容 邻接矩阵 有向图的可达矩阵 无向图的关联矩阵 有向图的关联矩阵 图的运算 学习要点与基本要求 实例分析 邻接矩阵 定义7-3.1 设G=V,E是一个简单图，它有n个结点V={v1, v2, …, vn}, 则n阶方阵A(G)=(aij)称为G的邻接矩阵。其中 邻接矩阵的举例 求下图的邻接矩阵 邻接矩阵的性质 无向简单图的邻接矩阵是对称的；有向图的邻接矩阵不一定对称。 邻接矩阵与结点的标定顺序有关，不同标定顺序对应的邻接矩阵是彼此置换等价的。 在无向图的邻接矩阵中，第i行中非零元的个数等于vi的度，第i列中非零元的个数等于vi的度。 在有向图的邻接矩阵中，第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的一条长 度为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求和，即得akj(l+1)是所有从vi到vj的长度为l+1的路的 数目，故命题成立。 实例1 例1 给定图G=V,E，求v1到v3的长度为1,2,3,4的路的数目。经过v2的回路共有多少条？ 实例1（续） 可达性矩阵 定义7-3.2 令G=V,E是一个简单有向图，|V|=n，假定G的结点已编序，即V={v1, v2, …, vn}, 定义一个n×n矩阵P=(pij)。 其中 关于可达矩阵的说明 可达性矩阵描述任意两结点是否可达，以及对于任意结点是否有通过它的回路。 由邻接矩阵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（续） 根据例1的结果，可得 实例2（续） 使用方法二：把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? vi,vj ∈E 因此，求可达性矩阵就是求R的传递闭包MR+。 注意： 上述的结论也适用于无向图，把无向图的每一条边看成双向边即可。 实例2 实例2 无向图的完全关联矩阵 定义7-3.3 给定无向图G，令v1, v2, …, vp, e1, e2, …, eq分别记为M(G)的结点和边，则矩阵M(G)=(mij) p×q，其中 实例3 例3 求下图的完全关联矩阵。 关联矩阵的性质 1. M(G)中每一列只有两个非零元。 2.每一行中所有元素的和是对应结点的度数。 3.一行中元素全为0，其对应结点为孤立结点。 4. 同一个图当结点或边的编序不同时，其对应的M(G)仅有行序，列序的差别。 有向图的关联矩阵 定义7-3.4 给定简单有向图G=V,E， V={v1, v2, …, vp}, E={e1, e2, …, eq}, p×q阶矩阵M(G)=(mij) p×q，其中 实例 例4 求下图的