邻接矩阵及拉普拉斯矩阵_第1页
邻接矩阵及拉普拉斯矩阵_第2页
邻接矩阵及拉普拉斯矩阵_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

邻接矩阵及拉普拉斯矩阵邻接矩阵图的邻接矩阵能够很方便的表示图的很多信息，且具有描述简单、直观的特点。无向简单图的邻接矩阵定义如下：设图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. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论