毕业设计（论文）-关于图的(距离)Laplacian谱.doc

1引言题 目 关于图的（距离）laplacian谱 学生姓名 学号 所在学院 数学与计算机科学学院 专业班级 信息与计算科学 指导教师 完成地点 陕西理工学院 2015 年 6 月 12 日 陕西理工学院毕业设计关于图的(距离)laplacian谱(陕西理工学院数学与计算机科学学院 信息与计算科学1102班，陕西汉中 723000)指导老师：摘要 本文总结了矩阵特征值的求解方法,讨论了图的laplacian谱及距离谱,给出求解laplacian特征值的matlab程序算法以及幂法求解程序.关键词 laplacian矩阵；laplacian特征值；幂法；laplacian谱；距离谱 i on 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 723000，shaanxi).tutor: deng fang-anabstract: this paper summarizes the method for solving 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; distance spectrum目 录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 主要结论94.1.1 应用实例114.2代数方法求laplacian谱114.3 matlab程序求laplacian谱125 图的距离谱135.1 距离矩阵135.2 距离谱136 结束语14致谢14参考文献14iii 1引言图的谱理论是图论和组合矩阵论的重要研究领域之一,在量子化学、统计力学、计算机科学通信网络以及信息科学等领域中均有广泛的应用其主要涉及图的邻接谱、laplacian谱和 signless laplacian谱等.对于图的laplacian谱的研究一般有2个方向，其中一个方向就是确定给定图的laplacian谱,因为图的谱是由它的特征值构成的，因此要确定一个图的谱，首先得求出该图对应的矩阵的特征值.由文献1-2，7可知，对图的矩阵表示的研究已经很完善了陈志杰在文献3中提出了矩阵的特征值的代数求解方法侯风波、汪永高等在文献5-6中阐述了矩阵的特征值的幂法求解方法。在文献10中，该作者研究了连通图的laplacian特征值，利用图的laplacian矩阵的特征多项式表示式，对存在两个不同顶点，但有相同邻集的一类图，得到一个laplacian特征值，从而求解图的laplacian谱本文的主要工作就是整理和总结矩阵的特征值的求解方法，讨论了图的laplacian谱及距离谱,并把求解矩阵特征值的方法应用到求解图的laplacian谱及距离谱中.2 图的矩阵基本概念 图可以用集合来定义，也可用图形来表示，此外，还可用矩阵来表示.本部分接下来主要介绍一下图形的几种矩阵表示：2.1 关联矩阵 定义2.11:设无向图,，令为顶点与边的关联次数，则称为的关联矩阵，记为. 很显然，的可能取值为0（与不关联）、1（与关联1次）、（与关联2次，即是以为顶点的环）. 例如：图2.1 是图2.1的关联矩阵，不难看出关联矩阵具有以下各条性质： （1）每一列恰好有两个1或者一个2，这是因为每条边关联两个顶点（环关联的顶点重合）； （2）第行元素之和为的度数，； （3）所有的元素之和等于，； （4），当且仅当为孤立点； （5）若第列与第列相同，则说明与为平行边. 有向图的关联矩阵：有向图中无环存在.设，顶点集为，边集为，令 ,则称为图的关联矩阵，记作.图2.2为图2.2所示图的关联矩阵，不难看出有如下性质： （1）每一列恰好有一个1和一个-1； （2）第行1的个数等于，-1的个数等于，中所有1的个数等于所有-1的个数，都等于. 2.2 邻接矩阵定义2.21:图的顶点集，边集，.令为顶点邻接到顶点边的条数，称 为的邻接矩阵，记作. 图2.3为图2.3的邻接矩阵，不难看出： （1）所有的元素之和等于边数， （2）第i行元素之和等于，于是 （3）第j列元素之和等于，将无向图的每条边看作方向相反的两条边的有向图,很显然,无向图的邻接矩阵的性质如下: （1）无向图的邻接矩阵是对称矩阵； （2）为中长度为1的回路（环）的个数； （3）若中无环，则中第行（列）的元素之和等于顶点的度数； （4）有两个图和同构的充要条件是存在一个置换矩阵，使得2.3 度矩阵 定义2.33 设图的顶点集为，则图的度矩阵记为 . 定理3 图是阶简单图（既不含平行边也不含环），则关联矩阵,邻接矩阵和度矩阵有下面的关系：. 证明 记.的元素为，的元素就可以记为,若， （1），当且仅当边, （2）当且仅当； 对中任何其余边，由于，当时，对一切,由于，且.故有以下等式成立：.即 .若，则，因此 .2.4 laplacian矩阵因为图的laplacian矩阵中融入了顶点的度.因此，图的laplacian矩阵比图的邻接矩阵能更好地反映图的拓扑结构.目前，关于图的laplacian矩阵的研究成果最多，相关的应用也最为成熟.定义2.44 给定一个有个顶点的图,它的laplacian矩阵为:，记为.设是阶简单连通图,和分别是图的顶点集和边集.对于，表示顶点的度,的度序列为(其中),为图的邻接矩阵，为图的度矩阵，称矩阵为图的laplacian矩阵. 若图为简单图,即有：，例如图: 图2.4则图2.4的邻接矩阵为度矩阵为由此可得的laplacian矩阵 不难看出，的每行元素之和恒为零的半正定实对称矩阵.2.5 laplacian矩阵的性质 引理2.15 若是简单无向图，顶点集，边集，则（1）是一个对称的半正定矩阵；(2）,其中是图的连通分支的个数；（3）的行和列和恒等于零；（4）的任意两个元素的代数余子式都相等. 引理2.26 图的 laplacian矩阵的特征值中0特征值的重数等于图的连通分支数.这个引理表明,当图为连通图时,的第二小拉普拉斯谱.因此也被称为图的代数连通度.3 矩阵的特征值3.1矩阵特征值的代数求解方法的特征值就称为图的laplacian特征值，下面先来介绍一下特征值的概念以及求解方法.定义3.13 设是一个方阵. 如果存在一个非零列向量以及一个数，使得 ， （3.1） 则称是矩阵的一个特征值，称为的属于特征值的一个特征向量（3.1）式可以变形为 ， （3.2）其中为阶单位阵，这就相当于一个齐次线性方程组，其系数矩阵.存在非零向量相当于齐次线性方程组（3.2）有非零解，其充分必要条件是系数矩阵的行列式等于0，也就是说 （3.3）求解上式特征方程式，得到的就是矩阵的一个特征值3.2 应用实例以（如图2.4）为例，由第二部分的计算可得的laplacian矩阵为：，记的laplacian矩阵的特征值为，则有 解得的laplacian矩阵的特征值，.3.3矩阵特征值的幂法求解方法在许多实际问题应用中，矩阵的阶数可能很大，从而导致计算量也很大.另外，有时也不一定要求出矩阵的全部特征值和特征向量，只需求出在某种意义下的最大或者最小特征值和特征向量，此时我们就要用到幂法5,63.3.1幂法的简单算法 （1）输入矩阵，初始向量，误差,最大迭代次数 ； （2）(为迭代次数),;； （3）计算，； （4）若，输出，否则，转（5）； （5）若,置，转（3），否则输出失败信息.3.3.2幂法的matlab程序function t,y=mifa11(a,x0,eps,n) % t为所求特征值，y是对应特征向量 k=1; z=0; y=x0./max(abs(x0); % 规范化初始向量 x=a*y; % 迭代格式 b=max(x); if abs(z-b)eps & kn k=k+1; z=b; y=x./max(abs(x); x=a*y; b=max(x); end m,index=max(abs(x); % 这两步保证取出来的按模最大特征值 t=x(index); % 是原值，而非其绝对值 end3.4 算法实例实现以三阶矩阵a为例，结果如截图所示.3.5 矩阵特征值的matlab库函数求解程序 程序如下：说明：其中为特征值构成的对角阵，每个特征值对应于矩阵中列向量（也正是其特征向量），如果只有一个返回变量，则得到该矩阵特征值构成的列向量3.6 实例实现同样以为例实现：%v,m=eig(l)l=3 -1 -1 -1;-1 3 -1 -1;-1 -1 3 -1;-1 -1 -1 3v,m=eig(l)运行结果如截图所示：说明：其中m为特征值构成的对角阵.4 图的laplacian谱 由于拉普拉斯矩阵的特征值与图的结构之间有着更自然的联系，更能反映图的图论性质，因此对拉普拉斯矩阵的特征值的研究越来越引起人们的关注，已经成为当前图论研究中的一个热点问题之一laplacian特征值的集合构成了图的laplacian谱，在谱中，最重要的一个即是图的最大拉普拉斯特征值，被称为图的laplacian谱半径，次小特征值被称为图的代数连通度，次小特征值对应的向量被称为fielder向量这些概念在研究图的连通性方面有很大的优势 设有一个简单连通图，顶点集为,边集为，定点的度记为，图的laplacian矩阵，其中 为图的顶点度矩阵，为图的邻接矩阵.由于是行和恒为零的半正定实对称矩阵，因此其最小特征值恒等于零并且它的特征值(拉普拉斯谱)均为实数.我们将其特征值从大到小记为. 记图的laplacian谱为，此处表示的代数重数.4.1 主要结论 引理110 设为一个阶完全图，则有 . (4.1) 引理29 设为一个图，是给原来的图插入了一个边，则图的特征值和是交错存在的，即 （4.2） 引理310 设图是一个有个顶点，条边的连通图，如果,则图的最大特征值为. 证明 设边集为.由（1）式，可得，因此有： (4.3)由（2）式可得：，,其中 ,类似的，我们可以得到：，因此：如果，则有：. 定理111 设是一个连通图，,和是中和的邻接顶点，如果，则,为图的一个特征值. 证明 设，如果,则因为，然后有.如果，则.因此是laplacian矩阵的一个特征值.如果，则是laplacian矩阵的一个特征值.记是一个顶点在图，另一个邻接顶点在图中的图.引理410 设为一个图，假定顶点度数为2的星图的一个顶点邻接到顶点（）,构成了图,然后就是（如图4.1）的一个laplacian特征值. 证明 由于，,因此是（如图4.1）的一个laplacian特征值.引理510 设为一个图，假定任何一个顶点都邻接到顶点（）,构成了图,然后就是（如图4.2）的一个laplacian特征值.证明 由于（与相邻），,因此 是（如图4.2）的一个laplacian特征值. 引理610 设为一个图，假定的任何一个顶点都邻接到顶点（）,构成了图,然后就是（如图4.3）的一个laplacian特征值.证明 与引理1的证明类似. 图4.1 图4.2 图4.34.1.1 应用实例 例如下图所示，图4.4，由引理6可知是图的最大特征值.在中，因此是图的一个特征值.类似的，也是图的一个特征值.由(3)式，得到.因此4.2代数方法求laplacian谱 以为例，求解的的laplacian谱，先写出的laplacian矩阵的特征方程式：记的laplacian矩阵的特征值为，则有.于是可得的laplacian矩阵的特征值，因此的的laplacian谱为：.4.3 matlab程序求laplacian谱程序如下： %v,m=eig(l) l=; v,m=eig(l) x=m(:) x=sort(x);%排序 d=diff(x;max(x)+1);%求前后的差值 count = diff(find(1;d) ;%找出前后相差大于0值得索引的差值 y =x(find(d) count %对x中的数进行个数的统计以图4.4为例，结果如截图所示： 由此可得，图4.4的laplacian谱为.5 图的距离谱5.1 距离矩阵在图论中，凡是图形都有自己的距离矩阵，在数学中, 一个距离矩阵是一个包含一组点两两之间距离的矩阵(即二维数组).因此给定个欧几里得空间中的点, 其距离矩阵就是一个非负实数作为元素的的对称矩阵.这些点两两之间点对的数量，,也就是距离矩阵中独立元素的数量.距离矩阵和邻接矩阵概念相似，其区别在于后者仅包含元素（点）之间是否互相连通，并没有包含元素（点）之间的连通的成本或者距离.因此，距离矩阵可以看成是邻接矩阵的加权形式. 定义4对于一个图,我们可以根据图各个点之间的距离关系列出它的距离矩阵，,其中表示和 之间的距离.5.2 距离谱 定义11 设有一个顶点集为 的连通图.图的距离矩阵为，它的距离-能量和相等，也就是图的顶点和之间的最短距离12.特征值被认为是图的距离特征值，构成了图的距离谱形式，记为. 因为距离矩阵是对称的，其所有的特征值 ,都是实数并可以标注，以至于有 .这样如果是互异的-特征值，那么-谱记为：，此处表示的代数重数，显然有 .注：距离谱的求解方法与laplacian谱的求解方法类似.6 结束语本文的主要对图的laplacian谱的相关内容进行整理，探讨了laplacian特征值的求法，归纳了矩阵的代数求法和matlab库函数求解方法，给出应用实例.由于水平所限, laplacian的应用方面研究还不够深入,这个将成为以后研究的一个方向.致谢在这篇论文完成之际，我的大学生涯即将结束，在此我想对那些给予我关心和帮助的老师、同学、朋友致以最诚挚的谢意!首先要感谢我的指导老师邓方安对我的帮助和关心.在论文完成过程中，我深刻体会到了邓老师对教学工作的热心负责，对科研工作的兢兢业业，无论现在还是将来都是我学习的榜样.在此我要向我最敬爱的老师致以最崇高的谢意! 感谢信息与计算科学专业的老师们，他们为我传道授业解惑，给我提供了良好的学习和生活环境.感谢信计专业的兄弟姐妹们，一直以来对我工作和学习上孜孜不倦的指导和帮助，衷心的祝愿同学们在学院老师的带领下收获更丰硕的成果.感谢宿舍的舍友，是你们的帮助让我变得更加坚强和勇敢.祝愿大家都能实现自身的价值.最后，感谢父母这么多年给予我的最无私的关爱，为我创造了一个温馨的家，我的每一点进步都来自于他们背后默默地支持和鼓励.参考文献1 耿素云,屈婉玲,张立昂.离散数学m.北京：清华大学出版社,2008.155-165.2 于兰芳.图的矩阵及性质j.承德名族师专学报,2006,vol.26,no.2:13-14.3 陈志杰.高等代数与解析几何m.北京：高等教育出版社,2008.68-73.4 王冬冬.图的无符号拉普拉斯谱和距离谱的研究m.华东理工大学出版社,2015.13-1