（应用数学专业论文）图的拉普拉斯特征值的排序.pdf

ad i s s e r t a t i o ns u b m i t t e dt o t o n g j iu n i v e r s i t yi nc o n f o r m i t yw i t ht h er e q u i r e m e n t sf o r t h ed e g r e eo fd o c t o ro fp h i l o s o p h y t h e o r d e r i n go fl a p l a c i a n e i g e n v a l u e so fg r a p h s s c h o o l ：s c h o o lo fs c i e n c e d i s c i p l i n e ：丛丛垒皇里煎i 塑 m a j o r ：a p p l i e dm a t h e m a t i c s c a n d i d a t e ： y i n g l i u s u p e r v i s o r ：p r o j i a y us h a o f e b r u a r y , 2 0 0 8 燃 恻1： 删扩年年 薹n 忽 删y 陬保 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定，同意如下 各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学 位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存 论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务； 学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版：在 不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术 活动。 学位论文作者签名： 年月日： 经指导教师同意，本学位论文属于保密，在年解密后适用本授权书。 指导教师签名： 学位论文作者签名： 年月日年月日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 签名： 年月日 摘要 摘要 图谱理论是图论研究的一个非常活跃的重要领域，它在量子化学、统计力 学、通信网络及信息科学中均有一系列重要应用。图谱理论主要是利用线性代 数、矩阵论等成熟的代数理论和技巧，并结合图论和组合数学的理论来研究图 谱及其与图的结构性质以及与图的其它参数( 如色数、度序列、直径、连通度 等) 之间的关系，它将图与网络的代数性质与其拓扑性质紧密结合在一起。 在图论中，为了研究图的性质，人们引进了各种各样的矩阵，诸如图的邻 接矩阵、关联矩阵、距离矩阵、拉普拉斯矩阵、规范拉普拉斯矩阵等等。这些 矩阵与图的结构都有着密切的联系。代数图论的一个主要问题就是研究图的性 质能否以及如何由这些矩阵的代数性质反映出来。这里所指的矩阵的代数性 质，主要指矩阵的特征值。 在上面所提到的矩阵中，最重要的有两个：图的拉普拉斯矩阵和邻接矩 阵。图的拉普拉斯矩阵的特征值和邻接矩阵的特征值都是在图的同构下的不变 量，图的邻接矩阵及特征值是代数图论的一个基本研究课题。在过去的几十年 中，人们对图的邻接矩阵已经进行了大量的研究。和图的邻接矩阵相比，由于 拉普拉斯矩阵中含有图的顶点度的信息，因此图的拉普拉斯矩阵的特征值与图 的很多变量有着更加密切的联系。正如m o h a r 所说：图的拉普拉斯矩阵的特征 值更能反映它的图论性质。所以对图的拉普拉斯矩阵的特征值的研究越来越受 到人们的广泛关注。 人们对拉普拉斯矩阵的研究，可以追溯到1 6 0 多年以前。拉普拉斯矩阵最 著名的应用是在1 8 4 7 年k i r c h h o f f 研究电流理论时所发现的矩阵一树定理： 矩阵一树定理：设g 是一个有n 个顶点的连通图且l ( g ) 是它的拉普拉斯矩阵，去掉l ( g ) 的第i 行及歹列得到一个 佗一1 阶的子矩阵，记为l ( i l j ) 。则l ( i j ) 的行列式的绝对 值等于图g 的生成树的个数。 在数学物理上，由于拉普拉斯矩阵可以被视为拉普拉斯微分算子的离散情 形，故在数学上，该矩阵一般被称为拉普拉斯矩阵。图的拉普拉斯矩阵的特征 值被称为图的拉普拉斯特征值。 在图的拉普拉斯特征值中，最重要的有两个：图的最大拉普拉斯特征值 ( 即拉普拉斯谱半径) 和图的次小拉普拉斯特征值( 即代数连通度) 。1 9 8 1 i 同济大学博士学位论文 年，c v e t k o v i d 指出了图谱理论中进一步研究的十二个方向，其中之一就是用图 的谱对图进行分类和排序。2 0 0 7 年，a b r e u 总结了g r o n e 和m e r r i s 对树的代 数连通度进行排序的结论，指出他们所作的一些工作只是初步的，并提出按照 代数连通度的大小给出所有n 阶树的一全序仍是一公开问题。 本文主要研究了按从大到小的顺序对图的拉普拉斯谱半径以及代数连通度 进行排序的问题，所得结果具体如下： ( 一) 对有礼个顶点的单圈图的拉普拉斯谱半径按照从大到小的顺序进行 排序。在第二章中我们确定了单圈图拉普拉斯谱半径第五大值到第十三大值， 并刻画了达到这些数值的相应的图。 ( 二) 在第三章中我们对有礼= g + k 个顶点且圈长为9 的单圈图的拉普拉 斯谱半径按照从大到小的顺序进行排序，确定了圈长为g 的单圈图的拉普拉斯 谱半径从大n d , 的前吲个图。 ( 三) 在第四章中通过对瓶颈矩阵和图的代数连通度的研究，我们对有2 七 个顶点的具有完美匹配树的代数连通度按照从大n d , 的顺序进行排序，确定了 具有完美匹配树的代数连通度第二大值到第五大值，并刻画了达到这些数值的 相应的图( 或图类) 。 ( 四) 在第五章中对单圈图的代数连通度进行研究，我们按照从d , n 大的 顺序确定了有礼个顶点的单圈图代数连通度第- d , 和第三小的图。 关键词： 图；拉普拉斯矩阵；拉普拉斯特征值；特征多项式；拉普拉斯谱半径； 树；代数连通度；单圈图；嫁接运算；瓶颈矩阵；p e r r o n 分支 1 1 a b s t r a c t a b s t r a c t t h et h e o r yo fg r a p hs p e c t r ai sa na c t i v ea n di m p o r t a n ta r e ai ng r a p ht h e o r y t h e r ea r ee x t e n s i v ea p p l i c a t i o n si nt h ef i e l d so fq u a n t u mc h e m i s t r y , p h y s i c s ，c o i n - p u t e rs c i e n c e ，c o m m u n i c a t i o nn e t w o r ka n di n f o r m a t i o ns c i e n c e t h et h e o r yo f g r a p hs p e c t r ac a nb es e e na sa na t t e m p tt od m c o v e rt h ep r o p e r t i e so n s t r u c t u r e s o fg r a p h sa n dt h er e l a t i o n sb e t w e e nt h es p e c t r aa n df i x e dp a r a m e t e r s ( e g c h r o - m a t i cn u m b e r ，d e g r e es e q u e n c e ，d i a m e t e ra n dc o n n e c t i v i t y ) o fg r a p h sb ym e a n s o ft h ew e l l - d e v e l o p e dt h e o r ya n dt e c h n i q u eo ft h e o r i e so fg r a p h a n dc o m b i n a t o r i c s s oa st oe s t a b l i s hf i r m l ye s s e n t i a lr e l a t i o nb e t w e e nt h ea l g e b r a i cp r o p e r t i e sa n d t o p o l o g i c a lp r o p e r t i e so fg r a p h sa n dn e t w o r k s t h e r ea r ev a r i o u sm a t r i c e st h a ta r en a t u r a l l ya s s o c i a t e dw i t hag r a p h ，s u c h a u st h ea d i a c e n c ym a t r i x ，t h ei n c i d e n c em a t r i x ，t h ed i s t a n c em a t r i x ，t h el a p l a c i a n m a 乞r i ) 【a n dt h en o r m a l i z e dl a p l a e i a nm a t r i x o n eo ft h em a i np r o b l e m so fa l g e - b r a i cg r a p ht h e o r yi st od e t e r m i n ep r e c i s e l yh o w ，o rw h e t h e r ，p r o p e r t i e so fg r a p h s a r er e f l e c t e di nt h ea l g e b r a i cp r o p e r t i e s ( e s p e c i a l l ye i g e n v a l u e s ) o fs u c hm a t r i c e s a m o n gt h ea b o v em e n t i o n e dm a t r i c e so fg r a p h s t h em o s ti m p o r t a n tt w o a r e t h ea d j a c e n c ym a t r i xa n dt h el a p l a c i a nm a t r i xo fg r a p h s b o t ht h ee i g e n v a l u e s o ft h el a p l a c i a nm a t r i xa n dt h ea d j a c e n c ym a t r i xa r et h ei n v a r i a n t so fg r a p h s u n d e ri s o m o r p h i s m t h el a t t e ri so n eo ft h ee l e m e n t a r yd i r e c t i o no fa l g e b r a i c g r a p ht h e o r y , w h i c hw a sm u c hm o r ei n v e s t i g a t e di nt h ep a s tt h a nt h ee i g e n v a l u e s o ft h el a p l a c i a nm a t r i x h o w e v e r ，s i n c et h ee i g e n v a l u e so ft h el a p l a c i a nm a t r i x h a v eac l o s er e l a t i o nt on u m e r o u sg r a p hi n v a r i a n t s ，i ti sj u s ta sm o h a r s a i dt h a t ： t h e ya r em o r en a t u r a la n dm o r ei m p o r t a n tt h a nt h ee i g e n v a l u e so ft h ea d j a c e n c y m a t f i x l a p l a c i a nm a t r i xh a sal o n gh i s t o r y t h em o s tr e n o w n e da p p l i c a t i o no ft h e l a p l a c i a nm a t r i xl ( c ) o fag r a p hg i si nt h ef o l l o w i n gw e l l - k n o w nm a t r i x - t r e e - t h e o r e mw h i c hi su s u a l l ya t t r i b u t e dt ok i r c h h o f f i i i m a t r i x - t r e e - t h e o r e m l e tgb eag r a p ho i l 礼v e r t i c e sa n d l e tl ( i l j ) b et h em a t r i xo b t a i n e df r o ml ( g ) ，t h el a p l a c i a n m a t r i xo ft h eg r a p hg ，b yd e l e t i n gt h ei t hr o wt h ej t hc o l u m n t h ea b s o l u t ev a l u eo ft h ed e t e r m i n a n to fl ( i l j ) i se q u a lt ot h e n u m b e ro fs p a n n i n gt r e e so ft h eg r a p hg i nm a t h e m a t i c a lp h y s i c s ，t h el a p l a c i a nm a t r i xc a nb ec o n s i d e r e da sa d i s - c r e t i s i z e dl a p l a c ed i f f e r e n t i a lo p e r a t o r s oi ti so f t e nc a l l e dt h el a p l a c i a nm a t r i x o fag r a p hi nm a t h e m a t i c s t h ee i g e n v a l u e so ft h el a p l a c i a nm a t r i xo fag r a p h a r ec a l l e dt h el a p l a c i a ne i g e n v a l u e so ft h eg r a p h a m o n gt h el a p l a c i a ne i g e n v a l u e so fag r a p h ，t h em o s ti m p o r t a n t t w oa l e t h el a r g e s tl a p l a c i a ne i g e n v a l u e ( l a p l a c i a ns p e c t r u m ) a n dt h es e c o n ds m a l l e s t e i g e n v a l u e ( a l g e b r a i cc o n n e c t i v i t y ) i n1 9 81 ，c v e t k o v i 5g a v es o m es u g g e s t i o n sf o r t w e l v ep o s s i b l ef u r t h e ri n v e s t i g a t i o n so fg r a p hs p e c t r a o n eo ft h e mw a s c l a s s i f i - c a t i o na n do r d e r i n go fg r a p h s i n2 0 0 7 ，a b r e uf o u n dt h a ta l t h o u g hg r o n ea n d m e r r i sp r o v i d e dd i s t i n c tp a r t i a lo r d e r sb ya l g e b r a i cc o n n e c t i v i t yo nd i f f e r e n ts u b - c l a s s e so ft r e e s ，t h e i rr e s u l t sw e r en o te n o u g ht og i v eu sat o t a lo r d e r i n go ns e to f a l lt r e e s h ep r o p o s e dat o t a lo r d e r i n go ft r e e sb ya l g e b r a i cc o n n e c t i v i t yi ss t i l l a l lo p e np r o b l e m i nt h i sp a p e r ，t h r e et o p i c so nt h el a p l a c i a ne i g e n v a l u e so fg r a p h sh a v eb e e n s t u d i e d ： ( i ) i nc h a p t e r2 ，w ed e t e r m i n e dt h e f i r s tf i f t ht ot h et h i r t e e n t hl a p l a c i a n s p e c t r a lr a d i u so fu n i c y c l i cg r a p h sw i t h 凡v e r t i c e sa n dc o r r e s p o n d i n gg r a p h s ( i i ) i nc h a p t e r3 ，w ed e t e r m i n e dt h ef i r s t 吲u n i c y c l i cg r a p h sw i t hn = g + k v e r t i c e sa c c o r d i n gt ol a p l a c i a ns p e c t r a lr a d i u s ( i i i ) i nc h a p t e r4 ，w ed e t e r m i n e dt h ef i r s tt w o t of i f t ha l g e b r a i cc o n n e c t i v i t y o ft h et r e e sw i t hp e r f e c tm a t c h i n g sa n dc o r r e s p n d i n gg r a p h s ( o rg r a p h sc l a s s ) ( i v ) i nc h a p t e r5 ，w ed e t e r m i n e dt h es m a l l e s tt h r e eu n i e y c l i cg r a p h sw i t hn v e r t i c e sa c c o r d i n gt oa l g e b r a i cc o n n e c t i v i t y k e y w o r d s ：g r a p h ，l a p l a c i a nm a t r i x ，l a p l a c i a ne i g e n v a l u e s ，c h a l a c t e r i s - t i cp o l y n o m i a l ，l a p l a c i a ns p e c t r a lr a d i u s ，t r e e ，a l g e b r a i cc o n n e c t i v i t y , u n i c y c l i c g r a p h ，g r a f t i n g ，b o t t l e n e c km a t r i x ，p e r r o nb r a n c h i v 一一一一 摘要 a b s t r a c t 目录 筇一章绪论 5 1 1 研究- 亍景与进疑 1 2 基本概念 1 3 矩阵论中的基本弓l 理及其在拉蒋挝巅特征值中的应羽 第2 2 章簟嘲图的拉器拉j 诉潜半径的第珏人戗一第一l t 人值8 2 1 币嘲劁的拉普拉期谱? | ， 径的第矗大僚一第九大救8 2 1 1 引言8 2 1 2 阁的移边运算刈 酱拉斯谱半径的影响9 2 1 3 辅助斟丑一五4 1 1 2 1 4 ( g 1 ，g l o ) 以外的图的掩除1 8 2 1 5 阕g 5 一g l o 的硒| 序3 0 2 2 睡崩阁的拉酱拉梵玎诺半径f 勺第一 大馥一第 一三人值3 4 2 2 1 主要f j l 理3 5 2 2 2 币露阁的第十大一第十i ：大托普拉斯谱半径的排宁3 5 藏j 三章湖长嗣定的，罄湖湖的抛普挝斯潜半径排序4 0 3 1 弓| 高4 0 5 3 2 嘲k l 羽定的单陶黼的拇序4 1 第四章其以完美l 眦树的代数连通度的摊摩4 9 4 1g m “4 9 4 2 书要引艘5 1 v i 1 1 5 6 i 同济大学博士学位论文 4 3 其有完美匹配树的篇_ 大q ( t ) 5 1 4 4 其有完美匹配卡时的第：一t 大到第氘大n ( t ) 5 8 笫 章荦湖图代数连通皮从小剑火摊序6 6 5 1 纂本战略和主蜚引理6 6 5 2g 4 ，虢( i ) 相g ( i ，j ，k ) 的摊除6 8 5 3 擎嘲图矾( i ) 的排除和三 = ：璎结朵7 6 致谢8 1 参考文献 个人简历已发表的学术论文与研究成果 v i 8 2 8 8 第一章绪论 第一章绪论 1 1 研究背景与进展 图论是一个应用广泛的数学分支，是处理离散数学问题的强有力的工具。 图论同时也是运筹学、电路网络、通信网络、计算机科学理论研究和实践应用 中不可或缺的数学工具。不仅如此，它在开关理论、编码理论、计算机辅助设 计，乃至于社会科学、化学、物理等领域都有广泛的应用。因而，无论是就其 本身的理论价值，还是就其实际应用的广度和深度来看，图论及其应用的研究 正处于一个蓬勃发展的新时期。图论的研究内容以及其独特的研究方法，随着 现代科技的不断飞速发展越来越显示其独特的作用和魅力。 图谱理论是图论研究的重要领域之一。图谱在量子化学、统计力学、通信 网络及信息科学中有一系列重要的应用。自从上世纪五十年代被认为开创性文 章l c o l l a t z 和矿s i n o g o w i t z 的论文 9 】发表以来，图谱理论的研究不断发展 和深入，这方面的大量研究成果相继发表在国内外的许多重要的学术刊物和专 著中( 【4 ，8 ，1 1 ，1 2 ，4 2 ，4 5 等) 。正因为诸多组合、图论和代数方面的数学家 ( 如a zh o f f m a n ，dd g o d s i l , r a b r u a l d i ，l l o 砸s z ) 以及理论化学家、 物理学家( 如a zb a l a b a n ，a s t r e i t w i e s e r ) 都在这一领域做了许多深入的研 究工作，使得图谱理论在近三十年来成为图论中的一个非常活跃的研究领域。 图谱理论主要是利用线性代数、矩阵理论等成熟的代数理论和技巧，并结 合图论和组合数学的理论来研究图谱及其与图的结构性质以及与图的其它参数 ( 如色数、度序列、直径、连通度等) 之间的关系，它将图与网络的代数性质 与其拓扑性质紧密结合在一起。 经过数十年的研究，人们对图谱理论的认识已经相当广泛和深入。图谱 理论所研究的对象包括图的邻接谱、拉普拉斯谱、规范拉普拉斯谱、q 一 谱等。尽管图谱理论呈现出许多丰富多彩的形式，但各种不同意义的谱之间 有着相互的联系。设g 有礼个顶点的图，a ( g ) ( 简记为a ) 为图的邻接矩 阵，d ( g ) ( 简记为d ) 是以g 的顶点度为对角元的度对角矩阵。令 昆( z ，a ) = d e t ( x i + 入d a ) ， 通过对参数z ，a 取不同的值，就可以将上述各种谱的特征多项式都可以用 b ( z ，入) 来表示。例如 1 同济大学博士学位论文 邻接矩阵的特征多项式： 皿( g ，x ) = d e t ( x i a ) = f g ( z ，0 ) ； 拉普拉斯矩阵的特征多项式： 西( g ，z ) = d e t ( x i 一( d a ) ) = ( - 1 ) n f a ( 一z ，1 ) ； 规范拉普拉斯矩阵的特征多项式： c ( v ，z ) = d e t ( x i 一( ，一d 一 a d 一 ) ) = 气； f o ( o ，1 一z ) ； l 上l q 一矩阵的特征多项式： q ( g ，z ) 2 商抵( z d a ) 2 高如( o ，z ) 尽管这些谱总能转化到昆( z ，入) 形式，但各种不同的谱都有自己的应用背 景和实际价值，所以对各种谱的研究仍很必要，同时也给谱理论的研究提供了 广泛的题材和丰富多彩的内容，其中对邻接谱和拉普拉斯谱的研究最为普遍。 对图的邻接矩阵的特征值的研究，目前已形成比较成熟的理论，详见专著 【4 ，1 1 ，1 2 1 。与图的邻接矩阵的特征值相比，由于拉普拉斯矩阵的特征值与图的 结构之间有着更自然的联系，更能反映图的图论性质 4 8 】，因此对拉普拉斯矩 阵的特征值的研究正越来越引起人们的关注，是当前图论研究中的一个热点问 题。 对拉普拉斯矩阵的研究已有相当长的历史，最早可追溯到1 8 4 7 年k i r c h h o f f 在研究电流理论时所发现的矩阵一树定理。对图的拉普拉斯特征值的研究不仅 具有重要的理论价值，而且还有广泛的应用背景 4 8 】o 拉普拉斯特征值与拉普 拉斯微分算子、谱几何、网络理论、组合优化等数学分支均密切相关，同时在 物理、理论化学、计算机科学、电子工程学中均有重要的应用。 研究拉普拉斯特征值的方法主要有如下三种： ( 1 ) 代数方法：即用矩阵论并结合图的图论性质来研究拉普拉斯特征值， 如文献【2 4 】。 ( 2 ) 几何方法：即研究图的拉普拉斯矩阵l ( g ) = d ( g ) 一a ( g ) 所对应的 二次型并结合图的图论性质来研究拉普拉斯特征值或将图的规范拉普拉斯矩阵 d ( g ) 一三( g ) d ( g ) 一 视为r i e m m a n n 流形上的拉普拉斯算子的离散形式，从 而将拉普拉斯算子理论引入到拉普拉斯特征值的研究中，这方面的代表人物， 前者有m o h a r 等人，后者有fr 皿c h u n g 等人，如文献f 7 ，4 8 1 。 2 第一章绪论 ( 3 ) 概率方法：即通过引入随机路的概念，利用概率论的方法研究拉普拉 斯特征值，如文献【8 】。 另外，也可以借助于计算机来对拉普拉斯特征值进行研究，如文献 5 9 】。 在本文中，我们主要利用代数方法和几何方法来对图的拉普拉斯特征值进行研 究。 在图的拉普拉斯特征值中，最重要的有两个：图的最大拉普拉斯特征值 ( 即拉普拉斯谱半径) 和图的第- d , 的拉普拉斯特征值( 即代数连通度) 。利 用代数方法和几何方法对拉普拉斯特征值进行研究，主要有以下几个方面的工 作： ( 一) 对拉普拉斯谱半径的研究。主要是利用图的顶点度来给出拉普拉斯 谱半径的可达上界，该方面最早的工作是1 9 8 5 年a n d e r s o n 和m o r l e yf 5 0 给出 的如下上界： 设g = ( ve ) 是有礼个顶点的图，则 p ( g ) 也+ d t ，：u v e ) ， 等式成立当且仅当g 是二分正则图或g 是二分准正则图，其中肛( g ) 表示图g 的拉普拉斯谱半径。 1 9 9 7 年，李炯生和张晓东 6 4 1 改进了a n d e r s o n m o r l e y 的上界。自此以 后，有关拉普拉斯谱半径的上界大量涌现，见文献1 3 ，1 4 ，2 6 ，3 1 ，3 8 ，5 3 ，5 6 ，6 0 ， 6 1 ，6 3 ，6 5 1 。郭继明在 2 6 】中给出了图的拉普拉斯半径的若干个新的上界并且给 出了这些上界要优于上面结果的某些实例，同时也给出了一个二分图的拉普拉 斯谱半径的可达上界。 最近，一个有意义的工作是b r a n k o v ，h a n s e n 和s t e v a n o v i c 【5 9 】对已有的 上界进行了研究和比较并利用计算机给出了一些关于拉普拉斯谱半径的上界的 猜想。另外，g r o n e 等人【2 4 】考虑了对某些特殊图类进行收缩运算后，拉普拉 斯谱半径的变化情况。最近，郭继明 2 5 ，2 9 ，3 0 】研究了对一般图进行嫁接、夺 邻、收缩等运算后，拉普拉斯特征值的变化情况。 ( 二) 对代数连通度及其所对应的特征向量的研究。该方面早期的经典 工作是f i e d l e r 在【2 0 1 和【2 1 】中分别研究了图的代数连通度及其所对应的特 征向量，提出了用代数连通度所对应的特征向量来研究代数连通度的新思 路。因此，代数连通度所对应的特征向量通常被称为f i e d l e r 向量。1 9 8 7 年以 来，g r o n e ，m e r r i s 等人对树的代数连通度及f i e d l e r 向量进行了进一步的深入 3 同济大学博士学位论文 研究，见文献【2 3 ，3 9 ，4 0 1 ；最近，f a l l a t 和k i r k l a n d 等通过引入瓶颈矩阵，对 一般图的代数连通度进行了研究，将代数连通度的研究推向了一个新的层面， 见文献 1 6 ，1 7 ，1 8 ，1 9 ，3 4 ，3 5 ，5 2 ，5 5 ，5 7 】。 ( 三) 对拉普拉斯特征值与图的不变量之间的关系的研究。该方面的早期 工作是f i e d l e r 在文献 2 1 】中给出了代数连通度与图的连通度，边连通度之间 的如下关系： 设g 是n 阶图，则 ( 1 ) g 连通的充要条件是其代数连通度q ( g ) 0 ； ( 2 ) 设图g 的连通度和边连通度分别为v ( v ) 和e ( v ) ，则有q ( g ) v ( v ) e ( g ) 。 迸一步的研究发现，可以用拉普拉斯特征值来估计图的诸多不变量，如直 径 7 】，等周数 4 6 ，4 7 】，最大割【4 9 】，扩充子【2 】等等，有些图的不变量的计算 是n p - h a r d 问题，而拉普拉斯特征值则可用多项式理论中渐近求根方法加以计 算。 ( 四) 对图的其它拉普拉斯特征值的研究。在文献【3 ，2 4 ，4 4 中，g r o n e 等研究了拉普拉斯特征值落在某一区间上的重数；在文献【3 6 】中，李炯生等 研究了图的第二大拉普拉斯特征值，给出了第二大拉普拉斯特征值的一个可达 下界；p a t i 【5 4 】研究了图的第三个最小的拉普拉斯特征值及其所对应的特征向 量。 1 9 8 1 年，c v e t k o v i 6 在f 1 0 1 中提出了图谱理论的1 2 个可能的方向，其中一 个方向就是关于谱的排序。最近，a b r e u 在关于代数连通度的最新综述文章 1 】 总结了g r o n e ，m e r r i s 在文章【2 3 】中按照代数连通度大小对n 阶树进行排序的 一些结论，指出文献【2 3 】中所做的一些工作只是初步的，并提出按照代数连通 度的大小给所有礼阶树一个全序仍是一个公开问题。本文中，我们主要研究了 按从大到小的顺序对图的拉普拉斯谱半径以及代数连通度进行排序的问题，得 到的结果如下： ( 一) 对有礼个顶点的单圈图的拉普拉斯谱半径按照从大到小的顺序进行 排序。在第二章中我们确定了单圈图拉普拉斯谱半径第五大值到第十三大值， 并刻画了达到这些数值的相应的图。 ( 二) 在第三章中对有n = 夕+ k 个顶点且圈长为夕的单圈图的拉普拉斯谱 半径按照从大n d , 的顺序进行排序，我们确定了圈长为夕的单圈图的拉普拉斯 4 第一章绪论 谱半径从大到小的前吲个图。 ( 三) 在第四章通过对瓶颈矩阵和图的代数连通度的研究，我们对有2 尼个 顶点的具有完美匹配树的代数连通度按照从大到小的顺序进行排序，确定了具 有完美匹配树的代数连通度第二大到第五大值，并刻画了达到这些数值的相应 的图( 或图类) 。 ( 四) 在第五章中对单圈图的代数连通度进行研究，按照从小到大的顺序 我们确定了有n 个顶点的单圈图代数连通度第- 4 , 和第- - 4 , 的图。 1 2 基本概念 设g = ( ve ) 是有礼个顶点的简单连通图( 不含环和多重边) ，其 中v = 1 ，v 2 ，) 表示点集合、e 是边集合。令d ( v i ) 表示顶点忱的 度，盔( g ) 表示g 的第i 大的度，即有d l ( a ) d 2 ( a ) d n ( g ) ，i y ( g ) i 或i y i 表示图g 的顶点数。 图g 的拉普拉斯矩阵定义为l ( g ) = d ( g ) 一a ( g ) ，其中d = d ( g ) = d i a g ( d ( v 1 ) ，d ( v 2 ) ，d ( v n ) ) 是图g 的度对角矩阵。不难证明l ( g ) 是一个半 正定的实对称矩阵且它的每一行的行和为零。因此，l ( g 1 又是奇异的。从而， 我们可以假设它的特征值按照从大到小的顺序排列为： p 1 ( g ) p 2 ( g ) ( g ) = 0 称胀( g ) 为图g 的第k 大的拉普拉斯特征值。矩阵l ( g ) 的谱称为g 的拉普 拉斯谱，记作s p e c ( g ) ，即s p e c ( g ) = _ p 1 ( g ) ，p 2 ( g ) ，( g ) ) 。特别地， 称p 1 ( g ) 为图g 的拉普拉斯谱半径，记为肛( g ) 。 设x 是图g 的相应于纵( g ) 的一个特征向量，自然地，x 中的分量可以 与图g 的顶点之间建立一个一一对应关系，称为给g 一个点赋值 4 1 】。我们常 将对应于点v i 的x 中的分量记为x ( v f ) 或或以。特别地，假如x 是相应 于p ( g ) 的单位特征向量，则我们有 p ( g ) = x t l ( a ) x = ( x ( 仇) 一x ( ) ) 2 = y m r a x 。 y t l 万矿( g ) y ( 1 2 1 ) 仇巧d 在文献 2 1 】中，f i e d l e r 证明：图g 是连通的当且仅当g 的第二个最小的 拉普拉斯特征值一1 ( g ) 0 。因此，如一1 ( g ) 被f i e d l e r 称为图g 的代数连通 度，记为q ( g ) 。人们把对应于q ( g ) 的特征向量称为f i e d l e r 向量。假如x 是 5 同济大学博士学位论文 一个单位f i e d l e r 向量，则有 q ( g ) = x r l ( g ) x =( x ( 仇) 一x ( 彬= y 娥。l 百y t l ( g ) y ，( 1 2 2 ) 饥吩e ey t e n = o 其中e ，l 是t t 维的全1 列向量。 设b 是一个方阵，用圣( b ) = m ( b ；z ) = d e t ( x i b ) 表示b 的特征多项 式。特别地，如果b = 三( g ) ，则用垂( g ) 或西( g ；z ) 表示圣( l ( g ) ) ，且称西( g ) 为g 的拉普拉斯特征多项式。 在本文中，所用到的未加定义的图论和矩阵论中的一些基本定义和术语可 见文献( 5 ，6 ，3 3 ) 。 1 3 矩阵论中的基本引理及其在拉普拉斯特征值中的应用 由矩阵论中的基本定理可以得到图的拉普拉斯特征值的某些基本性质。在 本节中，我们将只给出与图的拉普拉斯特征值密切相关的矩阵论中的某些最重 要的基本定理，而对于一些其他的矩阵论中的结果，我们将在后面需要的时候 再介绍。 如下的定理通常被称为c o u r a n t - w e y l 不等式( 1 1 】p 5 1 ) 。 引理1 3 1 设入1 ( x ) 入2 ( x ) k ( x ) 表示佗阶实对称矩阵x 的n 个 特征值。设a 和b 都是n 阶实对称矩阵且c = a + b ，则有 入件j + 1 ( c ) a 件1 ( a ) + + 1 ( b ) ， 入n 一 一j ( c ) ) n - i ( a ) + k j ( b ) ， 其中0 i ，j ，i + 歹+ 1 n 特别， 入1 ( c ) a 1 ( a ) + a i ( b ) 设u 和t ，是图g = ( ve ) 中的两个不同点且u vge ，在g 中添加边u v 得到一个新图，记作g 7 = g + u v 。由上面的c o u r a n t - w e y l 不等式，我们有 引理1 3 2 p 1 g 和g 7 的拉普拉斯特征值满足如下的交叉关系，即有 胁+ 1 ( g 7 ) m ( a ) m g )( 1 i n 一1 ) 由引理1 3 2 ，我们有如下的推论。 推论1 3 1 设g 1 是g 的子图，则有 p 1 ( g 1 ) u x ( g ) 6 第一章绪论 定理1 3 1 口j 每一个非负矩阵a 的真主子矩阵的最大特征值f ：不超过a 的 最大值r 进一步，假如a 是不可约的，则总有f r ；假如a 是可约的，则 至少存在一个真主子阵，使得f = r 成立 定理1 3 2 口j 设a 是一个非负矩阵，则a 的谱半径随着a 中元素的增加而 递增进一步，如果a 是不可约的，则a 的谱半径随着a 中元素的增加而严 格递增。 定理1 3 3 剀设g 是一个二分图，则非负对称阵b ( g ) = d ( g ) - i - a ( g ) = l 三( g ) j 和l ( g ) 是首相似的；特别地，如果g 是连通的二分图，则g 的拉普拉 斯谱半径是l ( g ) 的一个单特征值。 由上面的三个定理很容易得到下面的推论。 推论1 3 2 廖刀设g 是连通二分图，g ，是g 的子图，则有 肛1 ( g 7 ) p 1 ( g ) ， 等式成立当且仅当g 7 = g 推论1 3 3 ( c a u c h yi n t e r l a c i n gt h e o r e m ) 1 1 1 设a 是一个n 阶的h e r - m i t i a n 矩阵且有特征值a 1 a 2 k 设b 是a 的一个仇阶主子阵， 具有特征值p 1 肛2 。则 k m “地九 7 同济大学博士学位论文 第二章单圈图的拉普拉斯谱半径的第五大 值一第十三大值 在本章中，我们将主要研究几个顶点的单圈图的拉普拉斯谱半径从大n d , 的排序问题。关于这一问题，郭曙光在文献 3 2 】中确定了n 个顶点的单圈图拉 普拉斯谱半径按照从大到小的顺序前四大值，并刻画了达到这些数值的单圈图 ( 见图2 1 中的g 1 一g 4 ) 。我们在此基础上确定了礼个顶点的单圈图拉普拉 斯谱半径按照从大n d , 的顺序第五大值到第十三大值，并刻画了达到这些数值 的单圈图。 2 1 单圈图的拉普拉斯谱半径的第五大值一第九大值 2 1 1 引言 顶点数等于边数的连通图称为单圈图。令巩是有n 个顶点的单圈图的集 合。令g 1 一g 1 0 是顶点数为仃的单圈图，如图2 1 所示。 越唑 g xg 2g 3g 4 g 5g 6 8 第二章单圈图的拉普拉斯谱半径的第五大值一第十三大值 记瓯是长为k 的圈，忌是有啦个顶点的树。容易看出，将c k = 秽1 忱v k v l 的顶点v i 和树r 某个顶点以粘合成一点就得到单圈图g ，记为 巩( 冗1 ，r 后) 或u ( r 1 ，兄) ( 顶点数几= n l + + n k ) ，称树r 为 有根树，戤为根点。特别地，当有根树尼是，并