(完整版)邻接矩阵及拉普拉斯矩阵 .doc

《(完整版)邻接矩阵及拉普拉斯矩阵 .doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、邻接矩阵及拉普拉斯矩阵邻接矩阵图的邻接矩阵能够很方便的表示图的很多信息，且具有描述简单、直观的特点。无向简单图的邻接矩阵定义如下：设图G=(V，E)，有n≥1个顶点,分别为：v1,v2,Lvn,则G的邻接矩阵A是按如下定义的一个n阶方阵。1，（v,v）EA=（aij）nn，aij=ij0,否则直观上，由邻接矩阵我们可以得到如下信息：v邻接矩阵是一个0，1的对称矩阵，对角线元素为0。vi矩阵的各个行和（列和）是各个顶点的度。所有元素相加和为边数的二倍。viiAn的i,j位置元素为v与v之间的长度等于n的ij通路的数目，而i，j位置的元素为v23i到自身

2、的回路的数目。特别的A的i,i位置元素是vi的度；A的i,i位置元素是含vi的三角形数目的二倍。lk(l)viii由3.设SA(l1)，则Sl中i,j位置元素S为顶点vi与vj之间长度小于或li,jk1等于l的通路的个数。若S(n-1)1.之间没有通路。由此我们可以得到一个i,j0，则说明vi与jl判断图G的联通新的重要准则：对于矩阵SAk，若S中所有元素都非零则G是连lk1通图，否则图G是非连通图。ix设G是连通图，将矩阵A的所有是1的aii换成相元素换成-1，并且把对角线元素应顶点2.的度，（i=1,2,L,n），则所得到的矩阵的任何元素的代数余

3、子式都相等，等于G的生成树的数目。拉普拉斯矩阵Laplacianmatrix的定义拉普拉斯矩阵（Laplacianmatrix)），也称为基尔霍夫矩阵,是表示图的一种矩阵。给定一个有n个顶点的图G(V,E)，其拉普拉斯矩阵被定义为:LDW其中为图的度矩阵，为图的邻接矩阵。举个例子。给定一个简单的图，如下：把此“图”转换为邻接矩阵的形式，记为：把的每一列元素加起来得到个数，然后把它们放在对角线上（其它地方都是零），组成一个的对角矩阵，记为度矩阵，如下图所示：根据拉普拉斯矩阵的定义，可得拉普拉斯矩阵为：拉普拉斯矩阵的性质介绍拉普拉斯矩阵的性质之前，首先定

4、义两个概念，如下：①对于邻接矩阵，定义图中A子图与B子图之间所有边的权值之和如下：W(A,B)wijiA,jB其中，wij定义为节点i到节点j的权值，如果两个节点不是相连的，权值为零。②与某结点邻接的所有边的权值和定义为该顶点的度d，多个d形成一个度矩阵（对角阵）ndiwijj1拉普拉斯矩阵具有如下性质：?是对称半正定矩阵；?L101，即的最小特征值是0，相应的特征向量是1。证明：L1(DW)1001?有n个非负实特征值0=12Lnn?且对于任何一个属于实向量fR，有以下式子成立N12f'Lfwij(fifj)2i,j1n其中，LDW,diwij,W

5、(A,B)wij。证明：j1iA,jBnnf'Lff'DffWfdf2ffwiiijiji1i,j1nn1nn1222(difi2fifjwijdjfj)wijfifj2i1i,j1j12i,j1