《离散数学：8图论d- 图的矩阵表示》由会员分享，可在线阅读，更多相关《离散数学：8图论d- 图的矩阵表示（20页珍藏版）》请在金锄头文库上搜索。
1、1n图的基本概念的基本概念n路径与回路路径与回路n欧拉欧拉图与与汉密密尔顿图n图的矩的矩阵表示表示n平面平面图n图的着色的着色n树图论图论西安电子科技大学计算机学院西安电子科技大学计算机学院 鱼亮鱼亮 2图的矩阵表示图的矩阵表示n设设G=是一个线图，其中是一个线图，其中V=v1,v2,vn，则，则n阶方阵阶方阵A(G)=aij 称为称为G的的邻接矩阵邻接矩阵(adjacency matrix)。其中。其中西安电子科技大学计算机学院西安电子科技大学计算机学院 鱼亮鱼亮 3图的矩阵表示图的矩阵表示v1v2v3v4v1v2v3v4西安电子科技大学计算机学院西安电子科技大学计算机学院 鱼亮鱼亮 4图的
2、矩阵表示图的矩阵表示n邻接矩接矩阵可以推广到多重可以推广到多重图和和赋权图。对于多重于多重图，aij代表代表从从vi到到vj的的边的重数；的重数；对于于赋权图，aij代表代表权W(i,j)，从，从vi到到vj不存在不存在边时，规定定aij0。n图G的的邻接矩接矩阵不唯一，与不唯一，与n个个结点的点的标定次序有关，但不定次序有关，但不同的同的邻接矩接矩阵可以通可以通过对行和列的置行和列的置换相互相互变换。因此，。因此，对于于给定的定的图，可以忽略，可以忽略结点的点的标定次序，定次序，选择任意一个任意一个邻接矩接矩阵作作为该图的矩的矩阵表示。表示。西安电子科技大学计算机学院西安电子科技大学计算机学
3、院 鱼亮鱼亮 5图的矩阵表示图的矩阵表示n若为无向简单图，则若为无向简单图，则A(G)是对称的；是对称的；对角线为对角线为0；第第i行中值为行中值为1的元素数目等于的元素数目等于vi的度数，第的度数，第j列中值为列中值为1的元的元素数目等于素数目等于vj的度数，即的度数，即西安电子科技大学计算机学院西安电子科技大学计算机学院 鱼亮鱼亮 6图的矩阵表示图的矩阵表示n若为有向简单图，则若为有向简单图，则A(G)不一定是对称的；不一定是对称的；对角线为对角线为0；第第i行中值为行中值为1的元素数目等于的元素数目等于vi的出度，第的出度，第j列中值为列中值为1的元的元素数目等于素数目等于vj的入度，即
4、的入度，即西安电子科技大学计算机学院西安电子科技大学计算机学院 鱼亮鱼亮 7图的矩阵表示图的矩阵表示n设有向线图设有向线图G，其邻接矩阵为，其邻接矩阵为A，v1v2v3v4西安电子科技大学计算机学院西安电子科技大学计算机学院 鱼亮鱼亮 8图的矩阵表示n现讨论现讨论AAT元素的意义元素的意义设设Bbij AAT ，则，则 当且仅当当且仅当aik和和ajk都是都是1时，时，aikajk1。aik1和和ajk1表示存在边表示存在边和和。于是，从结点。于是，从结点vi和和vj两点引两点引出的边，如果能共同终止于一些结点，这些终止结点的数出的边，如果能共同终止于一些结点，这些终止结点的数目就是目就是bi
5、j的值；当的值；当ij时，对角线上的元素时，对角线上的元素bii就是结点就是结点vi的的引出次数。引出次数。v1v2v3v4=西安电子科技大学计算机学院西安电子科技大学计算机学院 鱼亮鱼亮 9图的矩阵表示图的矩阵表示n现讨论现讨论ATA元素的意义元素的意义设设Bbij ATA ，则，则 当且仅当当且仅当aki和和akj都是都是1时，时，akiakj1。aki1和和akj1表示存在边表示存在边和和。于是，从一些结点引出的。于是，从一些结点引出的边，如果同时终止于边，如果同时终止于vi和和vj，则这些结点的数目就是，则这些结点的数目就是bij的的值；当值；当ij时，对角线上的元素时，对角线上的元素
6、bii就是结点就是结点vi的引入次数。的引入次数。v1v2v3v4=西安电子科技大学计算机学院西安电子科技大学计算机学院 鱼亮鱼亮 10图的矩阵表示图的矩阵表示n设有向图设有向图G，其邻接矩阵为，其邻接矩阵为A，现讨论，现讨论A(n)元素的意义元素的意义n1时，时，aij1，表示存在一条边，表示存在一条边，或者说，从，或者说，从vi到到vj存在一条长度为存在一条长度为1的路径。的路径。n2时，用时，用aij(2)表示表示A(2)的各元素，于是的各元素，于是当且当且仅当当aik和和akj都等于都等于1时， aikakj1，即表示从，即表示从vi经过vk到到vj存在一条路径，存在一条路径，长度度为
7、2；所以；所以aij(2)表示从表示从vi到到vj长度度为2的的不同路径的条数；不同路径的条数；aii(2)表示从表示从vi到到vi长度度为2的不同回路的条数。的不同回路的条数。所以，所以， A(n)的元素的元素aij(n)是表示从是表示从vi到到vj长度度为n的不同路径的的不同路径的条数；条数； aii(n)表示从表示从vi到到vi长度度为n的不同回路的条数。的不同回路的条数。西安电子科技大学计算机学院西安电子科技大学计算机学院 鱼亮鱼亮 11图的矩阵表示图的矩阵表示ij时，时，d(vi,vj)就是使就是使A(m)的元素的元素aij(m)是非零值的最小正整是非零值的最小正整数数m。v1v2v
8、3v4例：在上例：在上图中，中，v2到到v1有两条有两条长度度为2的路径，的路径，且它且它们之之间距离距离为2； v3到到v3有有1条条长度度为3的的回路。回路。 v4到到v3没有没有长度度为2的路径。的路径。12图的矩阵表示图的矩阵表示n设矩阵设矩阵BrAA(2) A(3) A(r)，容易看出，容易看出，bij是表示是表示从从vi到到vj的长度小于和等于的长度小于和等于r的不同路径总数。因此，要研究的不同路径总数。因此，要研究是否存在一条从是否存在一条从vi到到vj的任意长的路径，需求出的任意长的路径，需求出而在而在n个个结点的点的简单有向有向图中，基本路径中，基本路径长度不超度不超过n-1
9、，基，基本回路本回路长度不超度不超过n，因此，因此仅需考察需考察Bn-1AA(2) A(3) A(n-1)，ij时BnAA(2) A(3) A(n)，ij时此此时，bij0，ij时表示从表示从vi到到vj是可达的，是可达的，ij时表示表示经过vi的回路存在；的回路存在；bij0，ij时表示从表示从vi到到vj是不可达的，分属于是不可达的，分属于不同不同强分分图，ij时表示表示经过vi的回路不存在。即的回路不存在。即bij表明了表明了结点点间的可达性。的可达性。13图的矩阵表示图的矩阵表示n如图所示有向图和矩阵如图所示有向图和矩阵B5，由于由于b520，所以，所以v2和和v5分属于不同的强分图；
10、分属于不同的强分图；由于由于b110，所以没有经过，所以没有经过v1的回路；的回路；由于由于b533，所以从，所以从v5到到v3长度不超过长度不超过5的路径有的路径有3条。条。v1v2v4v3v514图的矩阵表示图的矩阵表示有时仅需知道结点之间是否可达，而不必知道结点间存有时仅需知道结点之间是否可达，而不必知道结点间存在多少条路径和怎样的路径，因此引入以下定义：在多少条路径和怎样的路径，因此引入以下定义：n令令G=是一个线图，是一个线图，|V|=n，V=v1,v2,vn，则，则n阶方阵阶方阵P=pij 。其中。其中称矩称矩阵P是是图G的的可达性矩可达性矩阵。如果已知如果已知Bn，则只需将其中非
11、零元素写成只需将其中非零元素写成1，即得可达性，即得可达性矩矩阵。也可以把也可以把邻接矩接矩阵作作为布布尔矩矩阵，用布，用布尔矩矩阵运算直接求运算直接求得。得。15图的矩阵表示图的矩阵表示16图的矩阵表示图的矩阵表示17图的矩阵表示图的矩阵表示n可达性矩阵可达性矩阵P并没有表达出每一结点自身可达的概念，若实际并没有表达出每一结点自身可达的概念，若实际情况需要，可情况需要，可“或上或上”单位矩阵单位矩阵AI，以表达每一结点自身可，以表达每一结点自身可达，即达，即PAIP。v1v2v4v3v518图的矩阵表示图的矩阵表示n利用一个利用一个图的可达性矩的可达性矩阵，可以求出，可以求出这个个图的所有的所有强分分图。设P是是图G的可达性矩的可达性矩阵，其元素，其元素为pij，PT是是P的的转置矩置矩阵，其元素其元素为pijT，则图G的的强分分图可从矩可从矩阵PTP求得。因求得。因为从从vi到到vj可达，可达，则pij1，从，从vj到到vi可达，可达，则pji1，即，即pijT1，于，于是当且是当且仅当当vi和和vj相互可达相互可达时， PTP的第的第(i,j)个元素的个元素的值为1。19图的矩阵表示图的矩阵表示v1v2v4v3v520作业作业8-3：1、3
