关于图的(距离)laplacian谱

《关于图的(距离)laplacian谱》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、1引言题目关于图的（距离）Laplacian谱学生姓名学号所在学院数学与计算机科学学院专业班级信息与计算科学指导教师完成地点陕西理工学院2015年6月12日陕西理工学院毕业设计关于图的(距离)Laplacian谱(陕西理工学院数学与计算机科学学院信息与计算科学1102班，陕西汉中)指导老师：[摘要]本文总结了矩阵特征值的求解方法,讨论了图的Laplacian谱及距离谱,给出求解Laplacian特征值的Matlab程序算法以及幂法求解程序.[关键词]Laplacian矩阵；Laplacian特征值；幂法；Laplacian谱；距离谱I陕西理工学院毕

2、业设计Onthe(Distance)LaplacianspectrumofagraphBaiRong(Grade11,Class02,Majorinformationandcomputingscience,mathematicsandcomputerscienceDept.,ShaanxiUniversityofTechnology,Hanzhong，Shaanxi).Tutor:DengFang-anAbstract:Thispapersummarizesthemethodforsolvingamatrixeigenvalues.TheLapla

3、cianspectraanddistancespectrumofagrapharediscussed.ThenthispapergivestheMatlabproceduresalgorithmofLaplacianeigenvaluesandthemethodofexponent.Keywords:Laplacianmatrix;Laplacianeigenvalues;themethodofexponent;Laplacianspectrum;distancespectrumIII陕西理工学院毕业设计目录1引言12图的矩阵基本概念12.1关联矩

4、阵12.2邻接矩阵22.3度矩阵32.4Laplacian矩阵42.5Laplacian矩阵的性质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.3Matlab程序求Laplacian谱125图的距离谱135.1距离矩阵135.2距离谱136结束语14

5、致谢14参考文献14III陕西理工学院毕业设计1引言图的谱理论是图论和组合矩阵论的重要研究领域之一,在量子化学、统计力学、计算机科学通信网络以及信息科学等领域中均有广泛的应用．其主要涉及图的邻接谱、Laplacian谱和SignlessLaplacian谱等.对于图的Laplacian谱的研究一般有2个方向，其中一个方向就是确定给定图的Laplacian谱,因为图的谱是由它的特征值构成的，因此要确定一个图的谱，首先得求出该图对应的矩阵的特征值.由文献[1-2，7]可知，对图的矩阵表示的研究已经很完善了．陈志杰在文献[3]中提出了矩阵的特征值的代数求

6、解方法．侯风波、汪永高等在文献[5-6]中阐述了矩阵的特征值的幂法求解方法。在文献[10]中，该作者研究了连通图的Laplacian特征值，利用图的Laplacian矩阵的特征多项式表示式，对存在两个不同顶点，但有相同邻集的一类图，得到一个Laplacian特征值，从而求解图的Laplacian谱．本文的主要工作就是整理和总结矩阵的特征值的求解方法，讨论了图的Laplacian谱及距离谱,并把求解矩阵特征值的方法应用到求解图的Laplacian谱及距离谱中.　2图的矩阵基本概念图可以用集合来定义，也可用图形来表示，此外，还可用矩阵来表示.本部分接下

7、来主要介绍一下图形的几种矩阵表示：2.1关联矩阵定义2.1[1]:设无向图,，，令为顶点与边的关联次数，则称为的关联矩阵，记为.很显然，的可能取值为0（与不关联）、1（与关联1次）、（与关联2次，即是以为顶点的环）.例如：图2.1是图2.1的关联矩阵，不难看出关联矩阵具有以下各条性质：（1）每一列恰好有两个1或者一个2，这是因为每条边关联两个顶点（环关联的顶点重合）；（2）第行元素之和为的度数，；（3）所有的元素之和等于，；第14页共14页陕西理工学院毕业设计（4），当且仅当为孤立点；（5）若第列与第列相同，则说明与为平行边.有向图的关联矩阵：有向

8、图中无环存在.设，顶点集为，边集为，令,则称为图的关联矩阵，记作.　图2.2为图2.2所示图的关联矩阵，不难看出有如下性质