您所在位置：网站首页 > 建筑/环境 > 施工组织邻接矩阵及拉普拉斯矩阵

邻接矩阵及拉普拉斯矩阵

5页

卖家[上传人]：re****.1

文档编号：508306968

上传时间：2024-01-30

文档格式：DOCX

文档大小：37.80KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 金贝

/ 5 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、邻接矩阵及拉普拉斯矩阵邻接矩阵及拉普拉斯矩阵邻接矩阵图的邻接矩阵能够很方便的表示图的很多信息，且具有描述简单、直观的特点。无向简单图的邻接矩阵定义如下：设图G = (V，E ) ，有n 1 个顶点,分别为：v1,v2,Lvn,则G 的邻接矩阵 A是按如下定义的一个n阶方阵。 E1，A= ，a= nnij0, 否则直观上，由邻接矩阵我们可以得到如下信息： 1.邻接矩阵是一个0，1的对称矩阵，对角线元素为0。 2.矩阵的各个行和是各个顶点的度。所有元素相加和为边数的二倍。 3. An 的i, j 位置元素为vi与vj之间的长度等于n的通路的数目，而i，j位置的元素为vi到自身的回路的数目。特别的A的i,i位置元素是vi的度；A的i,i位置元素是含vi的三角形数目的二倍。 4.由3.设Sl=23Ak=1lk(l1)，则Sl中i,j位置元素Si(,l)j为顶点vi与vj之间长度小于或等于l的通路的个数。若Si(n-1)=0，则说明vi与vj之间没有通路。由此我们可以得到一个,j判断图G的联通新的重要准则：对于矩阵Sl=图，否则图G是非连通图。 5.设G 是连通图，将矩阵A的所有是1的元素

2、换成1，并且把对角线元素aii换成相Ak=1lk，若S中所有元素都非零则G是连通应顶点vi的度，则所得到的矩阵的任何元素的代数余子式都相等，等于G 的生成树的数目。拉普拉斯矩阵 Laplacian matrix的定义拉普拉斯矩阵，也称为基尔霍夫矩阵, 是表示图的一种矩阵。给定一个有n个顶点的图G=(V,E)，其拉普拉斯矩阵被定义为: L=D-W 为图的邻接矩阵。其中为图的度矩阵，举个例子。给定一个简单的图，如下：把此“图”转换为邻接矩阵的形式，记为：把组成一个的每一列元素加起来得到个数，然后把它们放在对角线上，的对角矩阵，记为度矩阵，如下图所示：根据拉普拉斯矩阵的定义，可得拉普拉斯矩阵为：拉普拉斯矩阵的性质介绍拉普拉斯矩阵的性质之前，首先定义两个概念，如下：对于邻接矩阵，定义图中A子图与B子图之间所有边的权值之和如下： W(A,B)=iA,jBwij 其中，wij定义为节点i到节点j的权值，如果两个节点不是相连的，权值为零。与某结点邻接的所有边的权值和定义为该顶点的度d，多个d 形成一个度矩阵 di=wij j=1n拉普拉斯矩阵具有如下性质：是对称半正定矩阵； L1=01，即的最小特征值是0，相应的特征向量是1。证明： L1=(D-W)1=0=01 有n个非负实特征值0=l1 且对于任何一个属于实向量l2Lln fRn，有以下式子成立 1NfLf=wij(fi-fj)2 2i,j=1 其中，L=D-W,di=wj=1nij,W(A,B)=niA,jBwij。证明： fLf=fDf-fWf=difi-fifjwij2ni=1i,j=1211=(difi2-2fifjwij+djfj2)=wij(fi-fj)2i=12i,j=1i,j=1j=1nnnn

《邻接矩阵及拉普拉斯矩阵》由会员re****.1分享，可在线阅读，更多相关《邻接矩阵及拉普拉斯矩阵》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源