邻接矩阵及拉普拉斯矩阵(共3页).docx

精选优质文档-倾情为你奉上邻接矩阵及拉普拉斯矩阵邻接矩阵图的邻接矩阵能够很方便的表示图的很多信息，且具有描述简单、直观的特点。无向简单图的邻接矩阵定义如下：设图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 的生成树的数目。拉普拉斯矩阵Laplacian matrix的定义拉普拉斯矩阵（Laplacian matrix)），也称为基尔霍夫矩阵, 是表示图的一种矩阵。给定一个有n个顶点的图，其拉普拉斯矩阵被定义为: 其中为图的度矩阵，为图的邻接矩阵。举个例子。给定一个简单的图，如下：    把此“图”转换为邻接矩阵的形式，记为：    把的每一列元素加起来得到个数，然后把它们放在对角线上（其它地方都是零），组成一个的对角矩阵，记为度矩阵，如下图所示：    根据拉普拉斯矩阵的定义，可得拉普拉斯矩阵 为：拉普拉斯矩阵的性质  介绍拉普拉斯矩阵的性质之前，首先定义两个概念，如下：对于邻接矩阵，定义图中A子图与B子图之间所有边的权值之和如下： 其中，定义为节点i到节点j的权值，如果两个节点不是相连的，权值为零。    与某结点邻接的所有边的权值和定义为该顶点的度d，多个d 形成一个度矩阵 （对角阵） 拉普拉斯矩阵 具有如下性质：·  是对称半正定矩阵；· ，即 的最小特征值是0，相应的特征向量是1。证明： ·   有n个非负实特征值 · 且对于任何一个属于实向量 ，有以下式子成立     其中，,。证明： 专心-专注-专业