《邻接矩阵及拉普拉斯矩阵教学内容.pdf》由会员分享，可在线阅读，更多相关《邻接矩阵及拉普拉斯矩阵教学内容.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 邻接矩阵及拉普拉斯矩阵 精品文档 收集于网络，如有侵权请联系管理员删除 邻接矩阵及拉普拉斯矩阵 邻接矩阵 图的邻接矩阵能够很方便的表示图的很多信息，且具有描述简单、直观的特点。无向简单图的邻接矩阵定义如下：设图G=(V，E)，有 n 1 个顶点,分别为：12,nv vvL则 G 的邻接矩阵 A是按如下定义的一个 n 阶方阵。1v=aa=0,ijij n nijA，（,v）E（），否则 直观上，由邻接矩阵我们可以得到如下信息：1.邻接矩阵是一个 0，1的对称矩阵，对角线元素为 0。2.矩阵的各个行和（列和）是各个顶点的度。所有元素相加和为边数的二倍。3.An 的 i,j 位置元素为vij与v之
2、间的长度等于 n 的通路的数目，而 i，j 位置的元素为vi到自身的回路的数目。特别的2A的 i,i 位置元素是vi的度；3A的 i,i位置元素是含vi的三角形数目的二倍。4.由 3.设1(1)lklkSAl，则lS中,i j位置元素(),Sli j为顶点iv与vj之间长度小于或等于 l 的通路的个数。若(n-1),S0i j，则说明iv与vj之间没有通路。由此我们可以得到一个判断图 G的联通新的重要准则：对于矩阵1lklkSA，若 S 中所有元素都非零则 G是连通图，否则图 G是非连通图。精品文档 收集于网络，如有侵权请联系管理员删除 5.设 G 是连通图，将矩阵 A的所有是 1 的元素换成
3、1，并且把对角线元素iia换成相应顶点iv的度，i=1,2,nL（），则所得到的矩阵的任何元素的代数余子式都相等，等于 G 的生成树的数目。拉普拉斯矩阵 Laplacian matrix 的定义 拉普拉斯矩阵（Laplacian matrix)），也称为基尔霍夫矩阵,是表示图的一种矩阵。给定一个有 n个顶点的图(V,E)G，其拉普拉斯矩阵被定义为:LDW 其中为图的度矩阵，为图的邻接矩阵。举个例子。给定一个简单的图，如下：把此“图”转换为邻接矩阵的形式，记为：把的每一列元素加起来得到个数，然后把它们放在对角线上（其它地方都是零），组成一个的对角矩阵，记为度矩阵，如下图所示：精品文档 收集于网络
4、，如有侵权请联系管理员删除 根据拉普拉斯矩阵的定义，可得拉普拉斯矩阵 为：拉普拉斯矩阵的性质 介绍拉普拉斯矩阵的性质之前，首先定义两个概念，如下：对于邻接矩阵，定义图中 A子图与 B子图之间所有边的权值之和如下：,(A,B)iji A j BWw 其中，ijw定义为节点 i 到节点 j 的权值，如果两个节点不是相连的，权值为零。与某结点邻接的所有边的权值和定义为该顶点的度d，多个 d 形成一个度矩阵 （对角阵）1niijjdw 拉普拉斯矩阵 具有如下性质：是对称半正定矩阵；L 10 1 ，即 的最小特征值是 0，相应的特征向量是 1。证明：1()100 1LD W 精品文档 收集于网络，如有侵权请联系管理员删除 有 n个非负实特征值12n0=L 且对于任何一个属于实向量nfR，有以下式子成立 2,11()2Nijiji jf Lfwff 其中，LDW,1niijjdw,(A,B)iji A j BWw。证明：21,12221,11,111(2)22nniiijijii jnnnniiijijjjijijii jji jf Lff DffWfd ff f wd ff f wd fwff