毕业设计(论文)-关于图的(距离)Laplacian谱.doc
《毕业设计(论文)-关于图的(距离)Laplacian谱.doc》由会员分享,可在线阅读,更多相关《毕业设计(论文)-关于图的(距离)Laplacian谱.doc(19页珍藏版)》请在三一文库上搜索。
1、1引言题 目 关于图的(距离)Laplacian谱 学生姓名 学号 所在学院 数学与计算机科学学院 专业班级 信息与计算科学 指导教师 完成地点 陕西理工学院 2015 年 6 月 12 日 陕西理工学院毕业设计关于图的(距离)Laplacian谱(陕西理工学院数学与计算机科学学院 信息与计算科学1102班,陕西汉中 723000)指导老师:摘要 本文总结了矩阵特征值的求解方法,讨论了图的Laplacian谱及距离谱,给出求解Laplacian特征值的Matlab程序算法以及幂法求解程序.关键词 Laplacian矩阵;Laplacian特征值;幂法;Laplacian谱;距离谱 I On t
2、he (Distance)Laplacian spectrum of a graphBai Rong(Grade11,Class02,Major information and computing science,mathematics and computer science Dept., Shaanxi University of Technology, Hanzhong 723000,Shaanxi).Tutor: Deng Fang-anAbstract: This paper summarizes the method for solving a matrix eigenvalues
3、.The Laplacian spectra and distance spectrum of a graph are discussed. Then this paper gives the Matlab procedures algorithm of Laplacian eigenvalues and the method of exponent.Key words: Laplacian matrix; Laplacian eigenvalues; the method of exponent ; Laplacian spectrum; distance spectrum目 录1引言12
4、图的矩阵基本概念12.1 关联矩阵12.2 邻接矩阵22.3 度矩阵32.4 Laplacian矩阵42.5 Laplacian矩阵的性质53 矩阵的特征值53.1矩阵特征值的代数求解方法53.2 应用实例63.3矩阵特征值的幂法求解方法63.3.1幂法的简单算法63.3.2幂法的Matlab程序73.4 算法实例实现73.5 矩阵特征值的Matlab库函数求解程序73.6 实例实现84 图的Laplacian谱94.1 主要结论94.1.1 应用实例114.2代数方法求Laplacian谱114.3 Matlab程序求Laplacian谱125 图的距离谱135.1 距离矩阵135.2 距离
5、谱136 结束语14致谢14参考文献14III 1引言图的谱理论是图论和组合矩阵论的重要研究领域之一,在量子化学、统计力学、计算机科学通信网络以及信息科学等领域中均有广泛的应用其主要涉及图的邻接谱、Laplacian谱和 Signless Laplacian谱等.对于图的Laplacian谱的研究一般有2个方向,其中一个方向就是确定给定图的Laplacian谱,因为图的谱是由它的特征值构成的,因此要确定一个图的谱,首先得求出该图对应的矩阵的特征值.由文献1-2,7可知,对图的矩阵表示的研究已经很完善了陈志杰在文献3中提出了矩阵的特征值的代数求解方法侯风波、汪永高等在文献5-6中阐述了矩阵的特征
6、值的幂法求解方法。在文献10中,该作者研究了连通图的Laplacian特征值,利用图的Laplacian矩阵的特征多项式表示式,对存在两个不同顶点,但有相同邻集的一类图,得到一个Laplacian特征值,从而求解图的Laplacian谱本文的主要工作就是整理和总结矩阵的特征值的求解方法,讨论了图的Laplacian谱及距离谱,并把求解矩阵特征值的方法应用到求解图的Laplacian谱及距离谱中.2 图的矩阵基本概念 图可以用集合来定义,也可用图形来表示,此外,还可用矩阵来表示.本部分接下来主要介绍一下图形的几种矩阵表示:2.1 关联矩阵 定义2.11:设无向图,,令为顶点与边的关联次数,则称为
7、的关联矩阵,记为. 很显然,的可能取值为0(与不关联)、1(与关联1次)、(与关联2次,即是以为顶点的环). 例如:图2.1 是图2.1的关联矩阵,不难看出关联矩阵具有以下各条性质: (1)每一列恰好有两个1或者一个2,这是因为每条边关联两个顶点(环关联的顶点重合); (2)第行元素之和为的度数,; (3)所有的元素之和等于,; (4),当且仅当为孤立点; (5)若第列与第列相同,则说明与为平行边. 有向图的关联矩阵:有向图中无环存在.设,顶点集为,边集为,令 ,则称为图的关联矩阵,记作.图2.2为图2.2所示图的关联矩阵,不难看出有如下性质: (1)每一列恰好有一个1和一个-1; (2)第行
8、1的个数等于,-1的个数等于,中所有1的个数等于所有-1的个数,都等于. 2.2 邻接矩阵定义2.21:图的顶点集,边集,.令为顶点邻接到顶点边的条数,称 为的邻接矩阵,记作. 图2.3为图2.3的邻接矩阵,不难看出: (1)所有的元素之和等于边数, (2)第i行元素之和等于,于是 (3)第j列元素之和等于,将无向图的每条边看作方向相反的两条边的有向图,很显然,无向图的邻接矩阵的性质如下: (1)无向图的邻接矩阵是对称矩阵; (2)为中长度为1的回路(环)的个数; (3)若中无环,则中第行(列)的元素之和等于顶点的度数; (4)有两个图和同构的充要条件是存在一个置换矩阵,使得2.3 度矩阵 定
9、义2.33 设图的顶点集为,则图的度矩阵记为 . 定理3 图是阶简单图(既不含平行边也不含环),则关联矩阵,邻接矩阵和度矩阵有下面的关系:. 证明 记.的元素为,的元素就可以记为,若, (1),当且仅当边, (2)当且仅当; 对中任何其余边,由于,当时,对一切,由于,且.故有以下等式成立:.即 .若,则,因此 .2.4 Laplacian矩阵因为图的Laplacian矩阵中融入了顶点的度.因此,图的Laplacian矩阵比图的邻接矩阵能更好地反映图的拓扑结构.目前,关于图的Laplacian矩阵的研究成果最多,相关的应用也最为成熟.定义2.44 给定一个有个顶点的图,它的Laplacian矩阵
10、为:,记为.设是阶简单连通图,和分别是图的顶点集和边集.对于,表示顶点的度,的度序列为(其中),为图的邻接矩阵,为图的度矩阵,称矩阵为图的Laplacian矩阵. 若图为简单图,即有:,例如图: 图2.4则图2.4的邻接矩阵为度矩阵为由此可得的Laplacian矩阵 不难看出,的每行元素之和恒为零的半正定实对称矩阵.2.5 Laplacian矩阵的性质 引理2.15 若是简单无向图,顶点集,边集,则(1)是一个对称的半正定矩阵;(2),其中是图的连通分支的个数;(3)的行和列和恒等于零;(4)的任意两个元素的代数余子式都相等. 引理2.26 图的 Laplacian矩阵的特征值中0特征值的重数
11、等于图的连通分支数.这个引理表明,当图为连通图时,的第二小拉普拉斯谱.因此也被称为图的代数连通度.3 矩阵的特征值3.1矩阵特征值的代数求解方法的特征值就称为图的Laplacian特征值,下面先来介绍一下特征值的概念以及求解方法.定义3.13 设是一个方阵. 如果存在一个非零列向量以及一个数,使得 , (3.1) 则称是矩阵的一个特征值,称为的属于特征值的一个特征向量(3.1)式可以变形为 , (3.2)其中为阶单位阵,这就相当于一个齐次线性方程组,其系数矩阵.存在非零向量相当于齐次线性方程组(3.2)有非零解,其充分必要条件是系数矩阵的行列式等于0,也就是说 (3.3)求解上式特征方程式,得
12、到的就是矩阵的一个特征值3.2 应用实例以(如图2.4)为例,由第二部分的计算可得的Laplacian矩阵为:,记的Laplacian矩阵的特征值为,则有 解得的Laplacian矩阵的特征值,.3.3矩阵特征值的幂法求解方法在许多实际问题应用中,矩阵的阶数可能很大,从而导致计算量也很大.另外,有时也不一定要求出矩阵的全部特征值和特征向量,只需求出在某种意义下的最大或者最小特征值和特征向量,此时我们就要用到幂法5,63.3.1幂法的简单算法 (1)输入矩阵,初始向量,误差,最大迭代次数 ; (2)(为迭代次数),;; (3)计算,; (4)若,输出,否则,转(5); (5)若,置,转(3),否
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 毕业设计 论文 关于 距离 Laplacian
链接地址:https://www.31doc.com/p-3950240.html