ch9-图的基本概念及其矩阵表示-3rd-hy

第9章图的基本概念及其表示-3胡燕2/389.4图的矩阵表示邻接矩阵定义：设是一个简单有向图，其中的结点集合，并且假定各结点已经有了从结点v1到vn的次序。试定义一个n×n的矩阵A，使得其中的元素,,GVE12{,,}nVvvvij1,,{vvEjvvEija当i(1)0当则称这样的矩阵A是图G的邻接矩阵。3/38邻接矩阵定义：元素或为0或为1的任何矩阵，都称为比特矩阵或布尔矩阵。邻接矩阵是布尔矩阵，第i行上值为1的元素的个数，等于结点vi的出度；第j列上值为1的元素的个数，等于结点vj的入度。4/38邻接矩阵图的邻接矩阵不具有唯一性。对于给定简单有向图来说，其邻接矩阵依赖于集合V中的各元素间的次序关系。,,GVE给定两个有向图和相对应的邻接矩阵，如果首先在一个图的邻接矩阵中交换一些行，而后交换相对应的各列，从而有一个图的邻接矩阵，能够求得另外一个图的邻接矩阵，则事实上这样的两个有向图，必定是互为同构的。5/38邻接矩阵例：写出下图的邻接矩阵，并计算各个节点的出度和入度。解：首先给各结点安排好一个次序，譬如说是。得出邻接矩阵如下：12345,,,,vvvvv12345123450100000100010111000011010vvvvvvvAvvv6/38邻接矩阵上例中，如果重新把各结点排列成，就能写出另外一个矩阵如下：52341,,,,vvvvv52341523410101100100110100000101000vvvvvvvAvvv7/38邻接矩阵对于给定图G，显然不会因结点编序不同而使其结构会发生任何变化，即图的结点所有不同编序实际上仍表示同一个图。换句话说，这些结点的不同编序的图都是同构的，并且它们的n！个邻接矩阵都是相似的。今后将略去这种由于V中结点编序而引起邻接矩阵的任意性。而取该图的任一个邻接矩阵作为该图的矩阵表示。8/38邻接矩阵由邻接矩阵判断有向图的性质：•如果有向图是自反的，则邻接矩阵的主对角线上的各元素，必定都是1。•如果有向图是反自反的，则邻接矩阵的主对角线上的各元素，必定都是0。•对于对称的有向图来说，其邻接矩阵也是对称的，也就说，对于所有的i和j而言，都应有aij=aji。•如果给定有向图是反对称的，则对于所有的i和j和i≠j而言，aij=1蕴含aji=0。9/38邻接矩阵可以把简单有向图的矩阵表示的概念，推广到简单无向图、多重边图和加权图。对于简单无向图来说，这种推广会给出一个对称的邻接矩阵，在多重边图或加权图的情况下，可以令ijijaw其中的wij，或者是边的重数，或者是边的权。另外，若，则。,ijvv,ijvv,ijvvE0ijw在零图的邻接矩阵中，所有元素都应该是0，亦即其邻接矩阵是个零矩阵。10/38邻接矩阵逆图的邻接矩阵：如果给定的图是一个简单有向图，并且其邻接矩阵是A，则图G的逆图的邻接矩阵是A的转置。对于无向图或者对称的有向图来说，应有。,,GVEGTATAA11/38在图上的意义TBAA定义矩阵。设是邻接矩阵中的第i行和第j列上的元素，是矩阵中的第i行和第j列上的元素(i,j)。于是，对于来说，有TBAAija(,)ijijb,1,2,3,,ijn1nijikjkkbaa如果边，则有，如果边，则有。对于某一个确定的k来说，如果和都是给定图的边，则在表示的上述求和表达式中，应该引入基值1。从结点vi和vj二者引出的边，如果能共同终止于一些结点的话，那么这样的一些结点的数目，就是元素的值。,ikvvE1ika,jkvvE1jka,ikvv,jkvvijbijb12/38在图上的意义TBAA例：如图，求TAA解：简单算法：原矩阵A中，第i行和第j行相交，有几个1，AAT的第i行第j列就是几。矩阵的主对角线的元素对应了各个节点的出度。12345123450100000100010111000011010vvvvvvvAvvv12345123450001110101010000010100100TvvvvvvvAvvv1010101000103020001110213TAA13/38在图上的意义TCAA设是邻接矩阵A中的(i,j)元素；是矩阵C中的元素。于是，对于ijaijc1,2,,,in1nijkikjkCaa对于某一个确定的k来说，如果都是给定图的边，则在上式中应引入基值1。可得从图中的一些点所引出的边，如果能够同时终止于结点vi和vj的话，那么这样的一些结点的数目，就是元素Cij的值。,,,kikjvvvv14/38在图上的意义例：如图，求TAA解：简单算法：原矩阵A中，第i列和第j列相交，有几个1，ATA的第i行第j列就是几。矩阵的主对角线的元素对应了各个节点的入度。TCAA12345123450100000100010111000011010vvvvvvvAvvv12345123450001110101010000010100100TvvvvvvvAvvv2101013021001001202101011TAA15/38邻接矩阵的幂对于来说，考察邻接矩阵A的幂An可知，邻接矩阵A中的第i行和第j列上的元素值1，说明了图G中存在一条边vi,vj，也就是说，存在一条从结点vi到vj长度为1的路径。试定义矩阵A2，使得A2中的各元素为2,3,4,n2ija12nijikkjkaaa元素值等于从vi到vj长度为2的不同路径的数目。显然，矩阵中主对角线上的元素的值，表示了结点上长度为2的循环的个数。矩阵A3中的元素值(i,j)依此类推。2ija2iia(1,2,,)ivin16/38邻接矩阵的幂例：2300100010110101121110,211101311101000001001110002111AA4521110131111311123321,233213634301011211102222135232AA17/38邻接矩阵的幂定理：设是一简单有向图，并且A是G的邻接矩阵。对于来说，矩阵Am中的元素(i,j)的值，等于从vi到vj长度为m的路径数目。,,GVE1,2,3,m证：对于m进行归纳证明。当m=1时，由邻接矩阵的定义中能够得到Am=A。设矩阵Ak中的元素(i,j)值是，且对于m=k来说结论为真。因所以应有kija1kkAAA11nijikkjkkkaaa是从结点vi出发，经过结点vk到vj的长度为k+1的各条路径的数目。这里vk是倒数第二个结点。因此，应是从结点vi出发，经过任意的倒数第二个结点到vj的长度为k+1的路径总数。因此，对于m=k+1，定理成立。kikkjaa1kija18/38邻接矩阵的幂根据上述定理，可得出结论：•能使矩阵Am中的元素(i,j)值是非零的最小正整数m，就是距离。•对于和来说，如果矩阵中的(i,j)元素值和(j,i)元素值都为0，那么就不会有任何路径连通结点vi和vj。因此，结点vi和vj必定是属于图G的不同分图。,ijdvv1,2,,1mnijmA19/38邻接矩阵的幂例：给定一个简单有向图，如下图所示，其中的结点集合。试求出图G的邻接矩阵A和A的幂A2，A3,A4。,,GVE12345{,,,,}Vvvvvv1v2v3v5v4v0100010100010000000100010A20/38邻接矩阵的幂解：1v2v3v5v4v20101000200010100000100001A30200020200020000000100010A42020004000202000001000001A21/38可达性矩阵给定一个简单有向图，并且设结点。可知，由图G的邻接矩阵A能够直接确定G中是否存在一条从vi到vj的边。设，由矩阵能够求得从结点vi到vj长度为r的路径数目。试构成矩阵,,GVE,ijvvVrIkA2kkBAAA矩阵Bk的(i,j)元素值表示了从结点vi到vj长度小于或等于r的路径数目。当图中的结点数目为n时，矩阵Bn都能够提供足够的信息，以表明从图中的任何结点到其它结点的可达性。22/38可达性矩阵定义：给定一个简单有向图，其中|V|=n，并且假定G中的各结点是有序的。试定义一个n×n的路径矩阵P，使得其元素为,,GVE10ijijijvvPvv如果从到至少存在一条路径如果从到不存在任何路径路经矩阵P仅表明了图中的任何结点偶对之间是否至少存在一条路径，以及在任何结点上存在循环与否；它并不能指明存在的所有路径。23/38可达性矩阵例：试构成下列有向图的路径矩阵P。解：设邻接矩阵A=A1。在前面的例中，已经求出过矩阵的幂A2，A3和A4,A5。求出矩阵B5和路径矩阵P如下：536343111115865311111,91489511111232221111161166411111BP24/38可达性矩阵注意：对于具有n个结点的图而言，长度为n的路径不可能是基本路径。假定图中的每一个结点，从它本身出发总是可达的，由矩阵Bn-1构成路径矩阵P，或由矩阵Bn构成路径矩阵P，这两种方法都可以采纳。25/38可达性矩阵首先构成矩阵，而后由他们构成矩阵Bn，再由矩阵Bn构成路径矩阵P，太麻烦了。为了减少计算工作量，应该设法使得不产生这些不必要的信息。2,,,nAAA生成路径矩阵的简单方法：布尔矩阵法。布尔和和布尔积：对于两个n×n的布尔矩阵A和B，A和B的布尔和是,A和B的布尔积是，并分别称为矩阵C和D，它们也都是布尔矩阵。把矩阵C和D的元素分别定义成ABAB1,()nijijijijikkjkCabdab26/38可达性矩阵邻接矩阵A是个布尔矩阵。路径矩阵P也是个布尔矩阵。对于，令2,3,r(2)AAA(1)()rrAAA于是，可以把路径矩阵P表示成(2)(3)()()1nnkkPAAAAA注意：A(m)表示布尔矩阵，如果从vi到vj有长度为m的路径的话，矩阵中(i,j)元素为1；Am中(i,j)元素表示从vi到vj的长度为m的路径的个数。27/38可达性矩阵例：对于下述的有向图来说，试求出矩阵A(2),A(3),A(4)),A(5)和P。(2)(3)00100010110101111110,111101111101000001001110001111AA(4)(5)11110111111111111111,111111111101011111101111111111AA(2)(3)(4)(2)(3)(4)(5)1111111111111111111111111AAAAAAAAAP28/38可达性矩阵可以用不同的方法解释矩阵。在简单有向图中，应有，因此可以把集合E看成是V中的二元关系。邻接矩阵A是关系E的关系矩阵。在第四章中，曾经把合成关系定义成这样一种关系：如果存在一个结点v