《关于图的(距离)laplacian谱》由会员分享，可在线阅读，更多相关《关于图的(距离)laplacian谱（18页珍藏版）》请在金锄头文库上搜索。
1、 1 引言题 目 关于图的（距离）Laplacian 谱 学生姓名 学号 所在学院 数 学 与 计 算 机 科 学 学 院 专业班级 信息与计算科学 指导教师 完成地点 陕西理工学院 2015 年 6 月 12 日陕西理工学院毕业设计I关于图的(距离)Laplacian 谱(陕西理工学院数学与计算机科学学院 信息与计算科学 1102 班，陕西汉中 )指导老师：摘要 本文总结了矩阵特征值的求解方法,讨论了图的 Laplacian 谱及距离谱,给出求解 Laplacian 特征值的Matlab 程序算法以及幂法求解程序.关键词 Laplacian 矩阵；Laplacian 特征值；幂法；Lapla
2、cian 谱；距离谱陕西理工学院毕业设计IIOn the (Distance)Laplacian spectrum of a graphBai Rong(Grade11,Class02,Major information and computing science,mathematics and computer science Dept., Shaanxi University of Technology, Hanzhong ，Shaanxi).Tutor: Deng Fang-anAbstract: This paper summarizes the method for solving
3、a matrix eigenvalues.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; distan
4、ce spectrum陕西理工学院毕业设计III目 录1 引言 .12 图的矩阵基本概念 .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 主要结论 .9
5、4.1.1 应用实例 .114.2 代数方法求 Laplacian 谱 .114.3 Matlab 程序求 Laplacian 谱 .125 图的距离谱 .135.1 距离矩阵 .135.2 距离谱 .136 结束语 .14致谢 .14参考文献 .14陕西理工学院毕业设计第 1 页 共 14 页1 引言图的谱理论是图论和组合矩阵论的重要研究领域之一,在量子化学、统计力学、计算机科学通信网络以及信息科学等领域中均有广泛的应用其主要涉及图的邻接谱、Laplacian 谱和 Signless Laplacian 谱等.对于图的 Laplacian 谱的研究一般有 2 个方向，其中一个方向就是确定给定
6、图的 Laplacian 谱,因为图的谱是由它的特征值构成的，因此要确定一个图的谱，首先得求出该图对应的矩阵的特征值.由文献1-2，7可知，对图的矩阵表示的研究已经很完善了陈志杰在文献3中提出了矩阵的特征值的代数求解方法侯风波、汪永高等在文献5-6中阐述了矩阵的特征值的幂法求解方法。在文献10中，该作者研究了连通图的 Laplacian 特征值，利用图的 Laplacian 矩阵的特征多项式表示式，对存在两个不同顶点，但有相同邻集的一类图，得到一个 Laplacian 特征值，从而求解图的Laplacian 谱本文的主要工作就是整理和总结矩阵的特征值的求解方法，讨论了图的 Laplacian
7、谱及距离谱,并把求解矩阵特征值的方法应用到求解图的 Laplacian 谱及距离谱中.2 图的矩阵基本概念图可以用集合来定义，也可用图形来表示，此外，还可用矩阵来表示.本部分接下来主要介绍一下图形的几种矩阵表示：2.1 关联矩阵定义 2.11:设无向图 , ， ，令 为顶点()GVE,21nvL,21meEKij与边 的关联次数，则称 为 的关联矩阵，记为 .ivjemnij )(GM很显然， 的可能取值为 0（ 与 不关联）、1（ 与 关联 1 次）、（ 与 关联 2 次，ijmivjeij ivj即 是以 为顶点的环）.ji例如： 4v13v2v1ee3图 2.10021)(GM是图 2.
8、1 的关联矩阵，不难看出关联矩阵具有以下各条性质：（1）每一列恰好有两个 1 或者一个 2，这是因为每条边关联两个顶点（环关联的顶点重合）；（2）第 行元素之和为 的度数， ；iiv)(1injivdm（3）所有的元素之和等于 ， ；2)(11ininimjjij vd陕西理工学院毕业设计第 2 页 共 14 页（4） ，当且仅当 为孤立点；mji10iv（5）若第 列与第 列相同，则说明 与 为平行边.kjek有向图的关联矩阵：有向图 中无环存在.设 ，顶点集为 ，边G(,)VE,21nvVL集为 ，,21meEK令 ,不jijiij ev1-0则称 为图的关联矩阵，记作 .mnij)( )
9、(GM1e24e353v2v4v图 2.2 0101)(GM为图 2.2 所示图的关联矩阵，不难看出 有如下性质：)(（1）每一列恰好有一个 1 和一个-1；（2）第 行 1 的个数等于 ，-1 的个数等于 ， 中所有 1 的个数等于所有-1i )(ivd )(ivd)(GM的个数，都等于 . m2.2 邻接矩阵定义 2.21:图 的顶点集 ，边集 ， .(,)GVE,21nK,21neEKmE令 为顶点 邻接到顶点 边的条数，称 为 的邻接矩阵，记作 . )1(ijaivjvija)( )(A3v2v4v1图 2.3陕西理工学院毕业设计第 3 页 共 14 页012)(GA为图 2.3 的邻接矩阵，不难看出： （1）所有的元素之和等于边数， maniji1)(（2）第 i 行元素之和等于 ， ，)(ivd nivdnji ,21),(1)( K于是mvaniiniji 11)()(（3）第 j 列元素之和等于 ， ，)(ivd njdnij ,2),(1)( Kmvaniiniji )(,11)(将无向图的每条边看作方向相反的两条边的有向图,很显然,无向图的邻接矩阵的性质如下:（1）无向图的邻接矩阵是对称矩阵；（2） 为 中长度为 1 的回路（环）的个数；niia1)(D（3）若 中无环，则 中第 行（列）的元素之和等于顶点 的度数；G)(Mi iv（4）
