第6章-图论(I).ppt

此外，当给定的简单图是无向图时，邻接矩阵是0-1对称矩阵；反之，若给定任何0-1对称矩阵A，显然可以唯一地作出以A为其邻接矩阵的简单图G。 于是，所有n个点的不同编序的简单图的集合与所有n阶0-1对称矩阵的集合可建立一一对应。也就是所有n点的简单图的集合与所有n阶非相似的0-1对称矩阵的集合形成一一对应。 当给定的图是简单有向图时，其邻接矩阵并非一定是对称矩阵，但所有n个结点的不同编序的简单图的集合，与所有n阶0-1矩阵的集合亦可建立一一对应。 不仅如此，通过对矩阵元素的一些计算还可以得到对应图的某些数量的特征。 在给定简单有向图的邻接矩阵中，第i行元素是由结点vi出发的弧所确定，故第i行中值为1的元素数目等于结点vi的出度。同理，第j列中值为1的元素数目等于结点vj的入度。 即d+(vi)= ；d -(vj)= 。 由给定简单图G的邻接矩阵A可计算出矩阵A的l次幂，即Al。若第i行第j列上的元素alij便是G中从第i个结点vi到第j个结点vj长度为l的通道(walk)的数目。为说明此事实，今给出下面定理。 定理7.3.1 设A为简单图G的邻接矩阵，则Al中的i行j列元素alij等于G中联结vi到vj的长度为l的通道的数目。 证：对l用数学归纳法。当l=2时，断言成立。事实上，注意到从vi到vj 的长度为2的通道，必须经过中间的一个点才能到达，也即：vi→vk→vj 如果有通道vivkvj存在，那么aik= akj =1, 即aikakj =1 ，反之若图G中不存在通道vivkvj ，则aik=0或akj =0，即aikakj =0。因此从vi到vj的长度为2的通道的数目等于： 记A(G)2=(aij(2))。那么aij(2)表示从vi到vj的长度为2的通道的数目。 假设对l成立，由 根据邻接矩阵定义aik表示联结vi与vk的长度为1的通道的数目，akj(l)是联结vk与vj的长度为l的通道的数目，故上式右边的每一项表示由vi经过一条边到vk，再由vk经过一条长度为l的通道到vj的总长度为l+1的通道的数目。对所有的k求和，即得akj(l+1)是所有从vi到vj的长度为l+1的通道的数目，定理得证。 在一些实际问题中，有时要判定图中结点vi到结点vj是否可达，或者说vi到vj是否存在一条路。如果要利用图G的邻接矩阵A，则应计算A2，A3，···，An，···。当发现其中某个Ar中 ≥1，就表明vi可达vj或vi到vj存在一条通道。但这种计算繁琐量大，又不知计算Ar到何时为止。 根据定理7.2.2可知，对于有n个结点的图，任何路的长度不大于n-1和任何圈的长度不大于n。因此，只需考虑 就可以了，其中1≤r≤n。即只要计算Bn=A+A2+A3+···+An。 如果关心的是结点间可达性或结点间是否有路，至于结点间的通道存在多少条及长度是多少无关紧要，那么便可用下面的定义图的可达矩阵来表示结点间可达性。 定义7.3.2 给定图G=V，E，将其结点按下标编序得V={v1，v2，…，vn}。定义一个n阶方阵P=(pij)，其中 则称矩阵P是图G的可达矩阵。 可见，可达矩阵表明了图中任意两结点间是否至少存在一条路以及在结点处是否有圈(或回路)。 从图G的邻接矩阵A可以得到可达矩阵P，即令Bn=A+A2+A3+…+An，再从Bn中非零元素改为1而零元素不变，这种变换后的矩阵即是可达矩阵P。 对于G=V,E的邻接矩阵A是关系E的关系矩阵，因为E2=EoE，即若存在一个结点vk，使得viEvk，和vkEvj，则必有viE2vj，亦即从vi到vj若至少存在一条长度为2的通道，那么E2的关系矩阵中的(i,j)元素值为1。这表明矩阵A(2)是关系E2的关系矩阵。以此类推，A(k)是Ek的关系矩阵，k=2,3,···,n。因此 A+=A?A(2)?A(3)?···?A(n) 亦即 A+=A?A(2)?A(3)?···?A(n)=P 可见，关系E的传递闭包E+的关系矩阵A+与可达矩阵相同。 为了计算A+或P，自然可先依次求得A(2)，A(3)，···，A(n)，然后再计算 A(k)，其结果即为所求，这是计算A+或P的一种方法，还可介绍一种现有效的方法—Warshall算法，它由邻接矩阵A依下面给出的步骤便能计算A+。其步骤如下： (1) P?A (2) k?1 (3) i?1 (4) 若pik=1，对j =1, 2, ···, n作pij?pij?pkj (5) i?i+1，若i≤n则转(4) (6) k?k+1，若k≤n则转到(3)，否则停止。 该算法的关键的一步是(4)，它判定如果pik=1，将第i行和第k行的各对应元素作布尔和或逻辑加后送