精选优质文档-倾情为你奉上邻接矩阵及拉普拉斯矩阵邻接矩阵图的邻接矩阵能够很方便的表示图的很多信息，且具有描述简单、直观的特点。无向简单图的邻接矩阵定义如下：设图G = (V，E ) ，有n 1 个顶点,分别为：则G 的邻接矩阵 A是按如下定义的一个n阶方阵。直观上，由邻接矩阵我们可以得到如下信息： 1.邻接矩阵是一个0，1的对称矩阵，对角线元素为0。 2.矩阵的各个行和（列和）是各个顶点的度。所有元素相加和为边数的二倍。 3. An 的i, j 位置元素为之间的长度等于n的通路的数目，而i，j位置的元素为到自身的回路的数目。特别的的i,i位置元素是的度；的i,i位置元素是含的三角形数目的二倍。4.由3.设，则中位置元素为顶点与之间长度小于或等于l的通路的个数。若，则说明与之间没有通路。由此我们可以得到一个判断图G的联通新的重要准则：对于矩阵，若S中所有元素都非零则G是连通图，否则图G是非连通图。5.设G 是连通图，将矩阵 A的所有是1的元素换成1，并且把对角线元素换成相应顶点的度，则所得到的矩阵的任何元素的代数余子式都相等，等于G
