资源描述：
《图的邻接矩阵的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、哈尔滨工程大学线性代数精品课：思考创新图的邻接矩阵应用简介图的邻接矩阵能够很方便的表示图的很多信息，且具有描述简单、直观的特点。无向简单图的邻接矩阵定义如下：设图G=(V,E)，有n≥1个顶点,分别为：v,v,?v,则G的邻接矩阵A是按如下定义的一个n阶方阵。12n⎧1,(,vv)∈EijAaa==(),⎨.ijnn×ij⎩0,否则直观上，由邻接矩阵我们可以得到如下信息：1.邻接矩阵是一个0，1的对称矩阵，对角线元素为0。2.矩阵的各个行和（列和）是各个顶点的度。所有元素相加和为边数的二倍。n3.A的i,j位置元素为由v与v之
2、间的长度等于n的通路的数目，而,ii位置的元ij23素为到自身的回路的数目。特别的vA的,ii位置元素是的度；vA的,ii位置ii元素是含的三角形的数目的二倍。vilk(l)4.由3.设Sl=∑A（l≥1），则Sl中i,j位置元素si,j为顶点vi与vj之间长度小于k=1(n−)1或等于l的通路的个数。若si,j=0，则说明vi与vj之间没有通路。由此我们可n−1k以得到一个判断图G的连通性的重要准则：对于矩阵S=∑A，若S中所有k=1元素都非零则图G是连通图，否则图G是非连通图。5.设G是连通图，将矩阵A的所有是1的元素换成
3、−1，并且把对角线元素a换成ii相应顶点的度，v(i=,2,1?.n)，则所得到的矩阵的任何元素的代数余子式都i相等，等于G的生成树的数目。有向简单图的邻接矩阵定义如下：设D(V,E)为有n个顶点，分别为v,v,?v的有向图,则D的邻接矩阵A是按如下定义的一个n阶方阵:12n1哈尔滨工程大学线性代数精品课：思考创新⎧1,(,vv)∈EijAaa==(),⎨.ijnn×ij⎩0,否则类似于无向图的讨论我们有：1.邻接矩阵是一个0，1矩阵，对角线元素为0，但不一定是对称的。2.矩阵的各个行和是相应顶点的出度，各个列和是相应顶点的入
4、度。所有元素相加的和与边数相等。n3.A的i,j位置元素为由v到v的长度等于n的通路的数目，而,ii位置的元素为viji到自身的回路的数目。4.对于有向图的连通性判定，若考察其基础图的邻接矩阵，相应的能够得到有向n−1k图D弱连通的判定准则；若考察其自身的邻接矩阵，可以得到：S=∑A中k=1所有元素都非零，则有向图D是强连通的，否则D不是强连通的。通过邻接矩阵还可以定义图的Laplacian矩阵，图的signlessLaplacian矩阵，以及有向图的可达矩阵等等，这些矩阵都是研究图的很好的工具，并在实际中有着非常广泛的应用。
5、参考文献[1][美]F.哈拉里，《图论》.上海科学技术出版社.1976。[2]RussellMerris:LaplacianMatricesofGraphs:Asurvey.LinearAlgebraAppl.143-174.a,b,ac[3]JianfengWang,QiongxiangHuang,FrancescoBelardo,EnzoM.LicMarzi:OngraphswhosesignlessLaplacianindexdoesnotexceed4.5.LinearAlgebraanditsApplications
6、431(2009)162–178.2
