毕业答辩图的拟拉普拉斯矩阵整谱性研究

1、研究背景当前，图论中整谱理论的研究内容及其独特的研究方法随着现代科技的不断进步，也越来越显示其独特的作用和魅力。因而，无论从其的理论价值，还是从其实际应用的广度和深度来看，图的整谱理论的研究及其应用的研究都有强大的生命力，并且正处于蓬勃发展的新时期。它在现实生活中的的应用范围很广，不但能应用于自然科学，也能应用于社会科学。电信网络、电电信网络、电力网络、编码力网络、编码理论、人工智理论、人工智能等能等图的整谱理论图的整谱理论图论、组合图论图论、组合图论等学术研究热点等学术研究热点语言学、经济语言学、经济学、运筹学、学、运筹学、遗传学等遗传学等分子物理学、分子物理学、原子物理学、原子物理学、化学

2、等化学等研究目标 本文主要探讨图的一些矩阵的谱全为整数的条件，将已有的邻接整谱、拉普拉斯整谱方法运用到Q-整谱中，期望得到新的成果。 本文主要研究三个问题：（1）图的整谱变化，即在添加一条边后谱发生整数的扰动；（2）对Laplace整图进行研究；（3）研究图的拟拉普拉斯矩阵整谱的问题。论文结构图的拟拉普拉斯矩阵整谱性研究第一章 引言第五章 致谢第二章 图的整谱变化第三章 Laplace整图第四章 图的拟拉普拉斯谱相关概念 定义定义1 1 图G的邻接矩阵A的特征值称为G的特征值。A的特征多项式称为G的特征多项式，记为 。 定义定义2 图G的谱是指G的所有特征值连同其重数的重集，记为Spec G或

3、Spec A，其中A为G的邻接矩阵。对于n阶简单图G，其邻接矩阵为n阶矩阵A=A(G)= 。若 ， 不邻接，记 =0；若 ， 邻接，记 =1。显然A(G)是一个对称的 (0,1)-矩阵。图G的Laplace矩阵L(G)定义为L(G)=D(G)-A(G),拟拉普拉斯矩阵Q(G)=D(G)+A(G),其中 D(G)为图G的度对角矩阵。Q的谱和特征值分别叫做图G的Q-谱和Q-特征值。 ( )Gf, i jaivjv, i jaivjv, i ja 定义定义3 3 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点 和 分别属于这两

4、个不同的顶点集A,B,则称图G为一个二分图(也叫二部图)。 定义定义4 4 每对顶点之间都恰连有一条边的简单图叫完全图。n个端点的完全图有n个端点及n(n- 1)/2条边，以 表示。记 为 的二部完全图； 称为星图，其中 。ivjvnK, r srsKVVrs1,sK3s 研究综述一、图的整谱变化一、图的整谱变化本章主要讨论树的整谱变化。它是一类特殊的图的谱扰动，研究该类扰动的目的是构造Laplace整图。设G为n阶简单图，其顶点集为 。假设 , 是G中两个不邻接的顶点，在G上添加 得到图G+e。适当调整顺序得,L(G+e)=L(G)+K，其中。注意到 。注意到12 ,.,nv vvivjv

5、,ijev v21111nK011()( )( ()( ( )2nniiiiGeGtr L Getr L G定理定理1 1(交错定理) 设G为n阶图，则G的Laplace特征值与G+e的Laplace特征值交错，即：由此我们发现：G在添加一条边后，所有特征值不会减小，且特征值总和增加2.若将加边后的谱扰动限制在整数扰动，则发生变化的特征值仅有下面两种情形：情形情形1 1 一个特征值增加2，其余n-1个特征值保持不变(称该情形为在一处发生谱整变化)；情形情形2 2 恰有2个特征值增加1，其余n-2个特征值保持不变(称该情形为在两处发生谱整变化)。若在添加一个环e后，Laplace谱发生如下整形变

6、化：(情形3)恰有一个特征值增加1，其余n-1个特征值保持不变(称该情形为加环后的在一处发生谱整变化)。112()( )().()( )0nnGeGGeGeG定理定理2 2 设G=(V,E)为一般图，G加环后在一处发生谱整变化当且仅当G时由带有一些环的孤立点构成的图。二、恰有三个不同特征值二、恰有三个不同特征值Laplace整图整图设I,J分别表示(适当阶数的)单位矩阵和全1矩阵，1 1表示(适当阶数的)的全1向量。引理引理1 1 设G为n( n3)阶连通图，L为G的Laplace矩阵。则L有t(2t n)个不同特征值当且仅当存在t-1个不同非零数 ，使得11,.,t11111()( 1)tt

7、itiiiLIJn 推论推论1 1 设G为n(n3)阶连通图，则G恰有两个不同的特征值当且仅当G为完全图。推论推论2 2 设G为n(n3)阶连通图，则G恰有三个不同特征值当且仅当存在两个不同的整数r,s,使得 ，其中 ； ，其中 。定理定理3 3 设G是无三角形的非正则图，则G有三个不同特征值当且仅当G是星图。在此情况下，G是Laplace整的。()();iiirsdr dsdn()()/ijijvvrdsdNNrs n ,( )ijv vE G/ijvvNNrs n ,( )ijv vE G定理定理4 4 连通二部图G具有三个不同特征值当且仅当G是完全正则二部图或星图，对于这两种情形，G均是

8、Laplace整的。三、图的拟拉普拉斯矩阵的谱三、图的拟拉普拉斯矩阵的谱定理定理5 5 二部图的Q-多项式等于Laplace特征多项式。定理定理6 6 设G是具有n个顶点和m条边的简单图，则G的拟拉普拉斯矩阵的最大特征值 ；最小特征值 。其中等号成立的充要条件是G为完全图。112(2)1mnmnn12(2)1nmnmnn定理定理7 7 设G=(V,E)为n个顶点m条边的无向简单图，则图G的拟拉普拉斯谱半径 有： 。定理定理8 8 设图G=(V,E)为n个顶点m条边的无向简单图，且图G无孤立点，则G的拟拉普拉斯谱半径 有： 其中 ， 分别为最大度和最小度，等号成立的充要条件是图G为一些顶点度相同

9、的正则图的并。1( )G12( )(2)mnGmn1( )G21( )422(1)2 (1)Gmn 主要结论命题命题1 1 设图G=(V,E)为具有n个顶点m条边的简单连通图，且顶点的度序列足 ,Q(G)=D(G)+A(G)为G的拟拉普拉斯矩阵，令 为Q(G)的最大特征值，即图G的拟拉普拉斯谱半径，则 ，其中1in。证明： 当i=1时，不等式为 ，该结论显然成立。当2in时，设 ，设图G的拟拉普拉斯矩阵Q(G)的分块形式为12.nddd12111121(1)4()(23)2iiidddddid 11( )2Gd1idd其中 为一个(i-1)(i-1)的矩阵， 为一个(n-i+1)(n-i+1)

10、的矩阵，设x为一个不大于1的正实数，取可逆矩阵 ，则11122122QQQQ11Q22Q1100in ixIUI 111100in iIUxI 111212122( )( )1QxQK GUQ G UQQx考虑矩阵K(G)的行和 ，首先考虑前i-1行的行和，显然第一行的行和最大，则 (1)接着考虑第i行到第n行的行和，显然第i行的行和最大，则 (2)12( ,.,)nr rr111111111111(1)(1)(1)(2)injjjjnjjrdaxadxdxax dx i11111112(1)12(1)(1)iniijijjjniijjirdaaxdaxdix显然， ，令 ，可得到， 。解该方

11、程得：易验证， 时，x=1， 时，0 x1,而另一个根由于x是不大于1的正实数，故舍去。将其代入（1）式，有： 1211max , ,., max(1)(1)(2),2(1)(1)nir rrx dx idix11(1)(1)(2)2(1)(1)ix dx idix211(2)(232)(1)0idixdid xi 2111211(232 )(1)4()(23)2(2)ididdddidxdi 1idd1idd 命题2 设 是 的根顶点，那么图 的拟拉普拉斯多项式为其中推论 设 是 的根顶点，那么图 是拟拉普拉斯整谱图当且仅当多项式a（x）和b(x)的根都为整数。 11112111( )(1)

12、(1)(2)(2)(2)21(1)4()(23)2iiiGx dx ididixdddddid ()nuV KnKr G2( )(3(1)41)a xxnxn3222( ) (33)(241 34 )263 )b xxn rxnnrnr xnrrnr (2)1( )(2)( ( )( )r nrg xnxa xb x()nuV KnKr G命题命题3 3 设 是 的根顶点，那么图 的特征多项式为 ,其中 给出顶点数给出顶点数n=2,3,4,5=2,3,4,5的拟拉普拉斯谱为整的连通的拟拉普拉斯谱为整的连通图图(第一行为邻接矩阵特征值，第二行为拟拉普拉斯特征值） n=2，1.000 -1.000

13、 2.000 0.000 ()nuV KnK1,nrK(1)1( )(1)(1)( )r nrh xxnxc x 2( )(1)c xxnxrn n=3，(1)2.000 -1.000 -1.000 4.000 1.000 1.000(2)1.414 0.000 -1.414 3.000 1.000 0.000 n=4,(1)3.000 -1.000 -1.000 -1.000 6.000 2.000 2.000 2.000(2)2.000 0.000 -1.000 -2.000 4.000 2.000 2.000 0.000(3)1.732 0.000 0.000 -1.732 4.000 2.000 2.