（应用数学专业论文）图的特征值.pdf

摘要 摘要 图谱理论是图论研究的一个非常活跃的重要领域，它在量子化学、统计力 学、通信网络及信息科学中均有一系列重要应用。图谱理论的研究主要是利用 线性代数、矩阵理论等成熟的代数理论和技巧，并结合图论和组合数学的理论 来研究图谱及其与图的结构性质以及与图的其它参数( 如色数、度序列、直径、 连通度等) 之间的关系，它将图与网络的代数性质与其拓扑性质紧密结合在一 起。 在图谱理论中人们引入了多种矩阵，诸如图的邻接矩阵、关联矩阵、距离 矩阵、拉普拉斯矩阵、规范拉普拉斯矩阵等等，这些矩阵与图的结构都有着密 切的联系。图谱理论的一个主要问题就是研究图的性质能否以及如何由这些矩 阵的代数性质反映出来，这里所指的矩阵的代数性质，主要指矩阵的特征值。 上面所提到的各种矩阵中，最重要的就是图的邻接矩阵和图的拉普拉斯矩 阵。本文首先较详细地介绍了图的邻接矩阵和图的拉普拉斯矩阵特征值中几个 重要课题的研究概况，然后分四部分介绍了我们围绕这些课题所取得的主要研 究成果。本文所得的主要结论有： 一在第二章中我们讨论图的邻接谱半径( 即邻接矩阵最大的特征值) ，确定 了直径为n 一4 的所有礼( n 之9 ) 阶连通图中取得最小邻接谱半径的图，所得结 果正面回答了文献 9 3 】( e r v a i ld a m ，r e 。k o o i j ，t h em i n i m a ls p e c t r a lr a d i u s o fg r a p h sw i t hag i v e nd i a m e t e r ，l i n e a ra l g e b r aa p p l 4 2 3 ( 2 0 0 7 ) 4 0 8 - 4 1 9 ) 中的 一个问题，这同时也是【9 3 】中猜想8 中的一种情形。 用u ( n ，a ) 表示最大度为的n 阶单圈图的集合。当+ 3 ) 2 时，我们 确定了甜( 佗，a ) 中邻接谱半径达到最大的图；证明了结论当a ( c ) f 7 n 9 - - f1 时，n ( 仃3 0 ) 阶单圈图g 的邻接谱半径p ( v ) 是其最大度( g ) 的严格增函 数。 二在第三章中我们讨论图的零度，即图的邻接特征值0 的重数。用叼( g ) 表示图g 的零度。通过利用图的邻接特征值的几个经典结论，我们分别刻画 了叩( g ) = 亿一2 的所有n 阶图和7 7 ( g ) = n 一3 的所有佗阶图；证明了结论：n 阶6 ) 双圈图的零度集合是 ，并且刻画了7 7 ( g ) = z , 一4 的所有n 阶9 ) 双圈图和叩( g ) = 礼一5 的所有n 阶( n 1 0 ) 双圈图。 同济大学博士学位论文 三在第四章中我们讨论树的拉普拉斯谱半径( 即拉普拉斯矩阵最大的特征 值) 。用丁( n ，) 表示最大度为的佗阶树的集合。利用图的变形技巧以及特征 多项式的一些技巧我们分别确定了当( n + 1 ) 2 时，丁( 几，) 中拉普拉斯谱 半径达到最大和次大的树，以及丁( 礼，a ) 中拉普拉斯谱半径达到最小的树；证 明了结论当( t ) ( n + 3 ) 2 时，n ( n 4 ) 阶树t 的拉普拉斯谱半径是其最大 度a ( t ) 的严格增函数。 用 t ( 2 k ) 表示2 七阶具有完美匹配的树的集合。通过将t ( 2 k ) 中树分类，我 们确定y t ( e k ) 中拉普拉斯谱半径的第二大至第六大值，并确定了达到这些值 的相应的树。 四在第五章中我们讨论树的代数连通度( 即拉普拉斯矩阵次小的特征值) 。 树t 的代数连通度a ( t ) 和其p e r r o n 分支的b o t t l e n e c k 矩阵m 之间有一个重要 的关系，就是 口( t ) 赢， 其e p p ( m ) 表示( 实对称) 矩阵m 的最大特征值，我们给出了上述不等式中等号 成立的充要条件；确定了所有满足a ( t ) 2 一镛的礼( n 1 5 ) 阶树t ，并对这 些树按照代数连通度的大小作了完全排序。 关键词：图；树；单圈图；双圈图；邻接矩阵；拉普拉斯矩阵；特征值； 邻接谱半径；拉普拉斯谱半径；代数连通度：零度；最大度；直径；p e 舢n 向 量；f i e d l e r 向量 i l 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 i s c o v e rt h ep r o p e r t i e so ns 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 印l l 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 ha 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 st h ea d j 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 t r i xa n dt h en o r m a l i z e dl a p l a c i a nm a t r i x o n eo ft h em a i np r o b l e m so fg r a p h s p e c t r at 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 印l l sa r e r 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 oa 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 l l s i nt h i st h e s i sw ei n t r o - d u c et h ed e v e l o p m e n to fs e v e r a li m p o r t a n tr e s e a r c ht o p i c sa b o u tt h ee i g e n v a l u e s a 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 印l l s ，a n dt h e nt h et h e s i si ss e p a - r a t e df o u rp a r t st oi n t r o d u c eo u rm a i nr e s u l t sa b o u tt h ea b o v et o p i c s w em a i n l y s t u d yt h ee i g e n v a l u e so ft 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 ， a n dt h ef o l l o w i n ga r et h em a i nc o n t e n t so ft h i st h e s i s 1 i nc h a p t e r2w es t u d yt h es p e c t r a lr a d i u so ft h ea d j a c e n c ym a t r i x ，i e ， t h el a r g e s te i g e n v a l u eo ft h ea d j a c e n c ym a t r i x w ed e t e r m i n et h eg r a p h sw h i c h h a v et h em i n i m a ls p e c t r a lr a d i u so ft h ea d j a c e n c ym a t r i xa m o n ga l lt h eg r a p h so f o r d e rn ( n 9 ) w i t ht h ed i a m e t e rn 一4 t h i sr e s u l ts e t t l e sap r o b l e mp r o p o s e d i n 9 3 】( e r v a nd a m ，r e k o o i j ，t h em i n i m a ls p e c t r a lr a d i u so fg r a p h sw i t ha g i v e nd i a m e t e r ，l i n e a ra l g e b r aa p p l 4 2 3 ( 2 0 0 7 ) 4 0 8 - 4 1 9 ) ，w h i c hi sa l s oac a s e o ft h ec o n j e c t u r e8i n 9 3 1 l e tu ( n ，a ) b et h es e to fa l lu n i c y c l i cg r a p h so fo r d e rnw i t hf i x e dm a x i m u m i i i d e g r e ea w h e na ( n + 3 ) 2 ，a m o n g a l lt h eg r a p h si nu ( n ，) w ec h a r a c t e r i z e t h eg r a p hw i t ht h em a x i m a ls p e c t r a lr a d i u s w ea l s op r o v et h a tt h es p e c t r a l r a d i u so fau n i c y c l i cg r a p hgo nn ( n 3 0 ) v e r t i c e ss t r i c t l yi n c r e a s e sw i t hi t s m a x i m u md e g r e ew h e n ( g ) 7 n 9 1 + 1 2 i nc h a p t e r3w es t u d yt h en u l l i t yo fag r a p h ( i e ，t h em u l t i p l i c i t yo ft h e e i g e n v a l u ez e r oo fi t sa d j a c e n c ym a t r i x ) l e tn ( c ) b e t h en u l l i t yo fag r a p hg b y u s i n gs e v e r a lc l a s s i c a lr e s u l t sa b o u tt h ee i g e n v a l u e so ft h ea d j a c e n c ym a t r i x ，w e d e t e r m i n et h eg r a p ho fo r d e r 佗w i t hn ( a ) = 亿一2a n dt h eg r a p ho fo r d e rnw i t h 叩( g ) = n 一3 ，r e s p e c t i v e l y w ea l s oo b t a i nt h en u l l i t ys e to fa l lb i c y c l i cg r a p h s o fo r d e r 礼( 几6 ) w h i c hi s w ea l s oc h a r a c t e r i z ea l lt h eb i c y c l i c g r a p h so fo r d e r 佗( 佗9 ) w i t h 叼( g ) = n 一4a n da l lt h eb i c y c l i cg r a p h so fo r d e r 佗( n 1 0 ) w i t h7 7 ( g ) = 佗一5 3 i nc h a p t e r4w es t u d yt h el a p l a c i a ns p e c t r a lr a d i u s ( i e ，t h el a r g e s te i g e n - v a l u eo ft h el a p l a c i a nm a t r i x ) o ft r e e s l e t 丁( 礼，a ) b et h es e to fa l lt r e e so f o r d e rnw i t hf i x e dm a x i m u md e g r e ea b yu s i n gt h et e c h n i q u eo fm o d i f i c a t i o n s o fg r a p h sa n db yu s i n gs o m et e c h n i q u e so ft h ec h a r a c t e r i s t i cp o l y n o m i a l ，w ed e t e r - m i n et h et w ot r e e sw h i c ht a k et h ef i r s ta n dt h es e c o n dl a r g e s tv a l u e so fl a p l a c i a n s p e c t r a lr a d i u so ft h et r e e si nt ( n ，) ，w h e na + 1 ) 2 a n da m o n gt h e t r e e si n 丁( n ，) ，w ec h a r a c t e r i z et h et r e ew h i c hm i n i m i z e st h el a p l a c i a ns p e c - t r a lr a d i u s f u r t h e r m o r e ，i ti sp r o v e dt h a tt h el a p l a c i a ns p e c t r a lr a d i u so fa t r e eto n 礼( n 4 ) v e r t i c e ss t r i c t l yi n c r e a s e sw i t hi t sm a x i m u md e g r e ew h e n a ( t ) ( 礼+ 3 ) 2 l e t 丁( 2 ) b et h es e to ft r e e so fo r d e r2 kw i t hp e r f e c tm a t c h i n g s b yg i v i n ga p a r t i t i o no ft h et r e e si nt ( 2 k ) ，w ed e t e r m i n et h es e c o n dt ot h es i x t hl a r g e s tv a l u e s o fl a p l a c i a ns p e c t r a lr a d i u so ft h et r e e si nt ( 2 k ) a n da l s og i v et h ec o r r e s p o n d i n g t r e e si nt ( 2 k ) w h o s el a p l a c i a ns p e c t r a lr a d i u sr e a c ht h e s ev a l u e s 4 i nc h a p t e r5w es t u d yt h ea l g e b r a i cc o n n e c t i v i t y ( i e ，t h es e c o n ds m a l l e s t e i g e n v a l u eo ft h el a p l a c i a nm a t r i x ) o ft r e e s t h e r ei s ar e l a t i o nb e t w e e nt h e a l g e b r a i cc o n n e c t i v i t y 乜( t ) o fat r e et a n dt h eb o t t l e n e c km a t r i xmo fi t sp e m 口仃 b r a n c h ，i e ， q ( t ) 丽1 ， i v w h e r ep ( m ) i st h el a r g e s te i g e n v a l u eo ft h e ( r e a lm a ds y m m e t r i c ) m a t r i xm w e g i v es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o n sf o rt h ee q u a l i t yc a s eo ft h a tr e l a t i o n w e d e t e r m i n ea l lt h et r e e so fo r d e r 扎1 5w h o s ea l g e b r a i cc o n n e c t i v i t yi sa tl e a s t 2 一怕a tt h es a m et i m ew eg i v eac o m p l e t eo r d e r i n go ft h e s et r e e sb yt h e i r a 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 ；t r e e ；u n i c y c l i cg r a p h ；b i c y c l i cg r a p h ；a d j a c e n c ym a t r i x ； l a p l a c i a nm a t r i x ；e i g e n v a l u e s ；s p e c t r a lr a d i u so fa d j a c e n c ym a t r i x ；l a p l a c i a n s p e c t r a lr a d i u s ；a l g e b r a i cc o n n e c t i v i t y ；n u l l i t y ；m a x i m u md e g r e e ；d i a m e t e r ；p e r - t o nv e c t o r ；f i e d l e rv e c t o r v 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 签名： 年月日 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定，同意如下 各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学 位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存 论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务： 学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版：在 不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术 活动。 学位论文作者签名： 年月日： 经指导教师同意，本学位论文属于保密，在年解密后适用本授权书。 指导教师签名： 年月日 学位论文作者签名： 年月日 第1 章绪论 第1 章绪论 1 1 研究背景与进展 图论是一个应用广泛的数学分支，是处理离散数学问题强有力的工具。图 论同时也是运筹学、电路网络、通信网络、计算机科学理论研究和实践应用中 不可或缺的数学工具。不仅如此，它在开关理论、编码理论、计算机辅助设 计，乃至于社会科学、化学、物理等领域都有广泛的应用。因而无论是就其本 身的理论价值，还是就其实际应用的广度和深度来看，图论及其应用的研究正 处于一个蓬勃发展的新时期。图论的研究内容以及其独特的研究方法，随着现 代科技的不断飞速发展越来越显示其独特的作用和魅力。 图谱理论是图论研究的重要领域之一。图谱在量子化学、统计力学、通信 网络及信息科学中有一系列重要的应用。自从上世纪五十年代被认为开创性文 章l c o l l a t z ，u s i n o g o w i t z 的论文1 3 1 发表以来，图谱理论的研究不断发展和深 入，这方面的大量研究成果相继发表在国内外的许多重要的学术刊物和专著 中( 6 】，【1 6 ，【l s ，【1 9 【7 7 ，【7 0 等) 。正因为诸多的组合、图论和代数方面的数学 家( 如a j h o f f m a n ，c d g o d s i l ，r a b r u a l d i ，r 尸s t a n l e y ，l l o v 丘s z ，n a s h - w i l l i a n s ) 以及理论化学家，物理学家( 如a t b a l a b a n ，a s t r e i t w i e s e r ) 都在这 一领域做了许多深入的研究工作，使得图谱理论在近三十年来成为图论中一个 非常活跃的研究领域。 图谱理论的研究主要是利用线性代数、矩阵理论等成熟的代数理论和技 巧，并结合图论和组合数学的理论来研究图谱及其与图的结构性质以及与图的 其它参数( 如色数、度序列、直径、连通度等) 之间的关系，将图与网络的代数 性质与图的拓扑性质紧密结合在一起。 经过数十年的研究，人们对图谱理论的认识已经相当广泛和深入。图谱理 论所研究的对象包括图的邻接谱、拉普拉斯谱、规范拉普拉斯谱、q 谱等。尽 管图谱理论呈现出丰富多彩的形式，但各种不同定义的谱之间有着相互联系。 设g 为n 阶图，a ( g ) ( 简记作a ) 为图g 的邻接矩阵，d ( g ) ( 简记作d ) 是以g 的 顶点度为对角元的对角矩阵。令 f g ( z ，a ) = d e t x i + 入d a 】， 同济大学博士学位论文 通过对参数z ，a 取不同的值，就可以将上述各种谱的特征多项式都可用f g ( z ，入) 来表示。 邻接矩阵的特征多项式： m ( g ；z ) = d e t ( x i a ) = f a ，o ) ； 拉普拉斯矩阵的特征多项式： 圣( g ；z ) = d e t ( x i 一( d a ) ) = ( - 1 ) 竹f a ( - x ，1 ) ； 规范拉普拉斯矩阵的特征多项式： 即= d e t ( 小( ，一一a 一) ) = 饼f g ( 0 , 1 - x ) ； q 矩阵的特征多项式： q ( g ；z ) 2 高d e t ( z d a ) 2 亩尼( o ，z ) ； 尽管这些谱总能转化到f c ( x ，a ) 形式，但各种不同的谱都有自己的应用背景 和实际价值，所以各种不同谱的研究仍很必要，同时也给谱理论的研究提供了 广泛的题材和丰富多彩的内容，其中对邻接谱和拉普拉斯谱的研究最为普遍。 对于图的邻接谱的研究，目前已形成比较成熟的理论，详见专著【6 1 ，1 8 1 ， 1 9 】等。图谱理论有一个重要的方面，就是利用一个网络的某种矩阵的特征值来 反映这个网络的某些拓扑性质，比如稳定性( r o b u s t n e s s ) ，直径，连通性等。文 献 9 4 中指出一个图的邻接谱半径( 即邻接矩阵最大的特征值) 在其相应网络的病 毒传播建模中有很大的作用。病毒传播理论( 见文献 2 2 】) 表明存在一个传染极限 指标，记做7 - 。文献 9 4 】给出了下面的表达式 丁2 高， ( l 1 1 ) l ， 其中p ( a ) 是指相应图的邻接谱半径。式( 1 1 1 ) 表明一个图的邻接谱半径越小， 其抵制病毒传播的能力越强。因此文献 9 3 】中提出了下面的问题。 问题1 1 1 【9 3 】在所有礼阶连通图中，哪个图达到最小的邻接谱半径? 记d ( g ) ( 或简记为d ) 为连通图g 的直径。众所周知，在所有礼阶连通图中， 路r 的邻接谱半径最小( 见文献 1 9 】) ，也就是说，路r 具有最大可能的传染极 2 第1 章绪论 限指标，但同时我们知道，路r 的直径也是最大的。一般而言，一个网络要设 计的直径尽量小，因为这样可以提高网络的服务质量( 9 3 】) 。考虑到此，e 冗 v a nd a m 和冗ek o o i j 在文献【9 3 】中将问题1 1 1 中加入了直径这一要素，提出 了如下问题： 问题1 1 2 9 3 1 给定直径d 的所有n 阶连通图中，哪个图达到最小的邻接谱半 径? 设磁裟嚣是一个通过如下方式得到的n l + n 2 + + 礼t + k 阶树：对于 每个i = l ，2 ，t ，在r ( 标号为铷t j l u 七一1 ) 的点；处粘合一个啦+ l 阶悬 挂路。 e r 秒彻，d a m 和r ek o o i j 在文献【9 3 】中对于d 1 ，2 ，h 2 j ，n 一3 ，礼一 2 ，仃一1 ) 时的情形对问题1 1 2 做了回答，并且提出了下面的猜想。 猜想1 1 1 【9 3 1 设e 是一固定整数，当扎充分大时，在所有直径为n e 的n 阶 连通图中，树槲再i ，篡。达到最小的邻接谱半径 er u 口扎d a m 和冗e k o o i j 在文献f 9 3 】中提出上述猜想的同时，也提出了 解决这个猜想的起始情形，即当n 9 时，在所有径为n 一4 的n 阶连通图中， 树t d 。l , n 。- - 一6 3 达到最小的邻接谱半径。 通过利用一类具有“连通和形式”图的邻接矩阵特征多项式的表达式，以及 利用赋权图的边剖分对邻接谱半径的影响的结果，我们确定了直径为佗一4 的 所有n 阶9 ) 连通图中邻接谱半径达到最小的图。所得结果正面回答了猜 想1 1 1 的起始情形，即证明了结论当n 9 时，在所有径为礼一4 的n 阶连通图 中，树p 1 。, n 一- 6 3 达到最小的邻接谱半径。 考虑图的邻接谱半径和其最大度的关系也是一个已得到广泛的研究的课 题。用p ( g ) 和( g ) 分别表示图g 的邻接谱半径和最大度，我们熟知的一个关 系就是下面的结论。 引理1 1 1 f 1 7 对任意一个简单图g ，我们有 、( g ) p ( g ) ( g ) 进一步，如果g 是一个树，g o d s i l 在文献【5 l 】中证明了下述结论。 引理1 1 2 【5 1 】对任意一个树g ，我们有 p ( g ) 2 v a ( a ) - 3 同济大学博士学位论文 用丁( 几，) 表示最大度为的佗阶树的集合。文献 9 1 】确定t t ( n ，a ) 中达 到最大邻接谱半径的图；文献 6 9 】证明了结论当( t ) 2 n 3 一1 时，扎阶 树t 的邻接谱半径p ( t ) 是其最大度a ( t ) 的严格增函数。 用“( n ，) 表示最大度为的扎阶单圈图的集合。当m 十3 ) 2 时，我们 确定t u ( n ，) 中邻接谱半径达到最大的图；证明了结论当a ( g ) f 7 n 9 1 + 1 时，佗( n 3 0 ) 阶单圈图g 的邻接谱半径p ( g ) 是其最大度a ( g ) 的严格增函 数。 图g 的邻接矩阵a ( g ) 是奇异( 非奇异) 的，则称图g 是奇异( 非奇异) 的。 图g 的特征值0 的重数称为g 的零度，记作叩( g ) ( ，7 ( g ) = 0 表示0 不是g 的 特征值) 。在文献 1 3 】中，c o u a t z 和s i n o g o w i t z 首先提出了问题：刻画所有满 足叩( g ) 0 的图g 。这个问题在化学上是很有意义的，正如文献 6 5 】中所指出 的，对于二部图g ( 对应于一个交替碳氢化合物) ，若叩( g ) 0 ，则表明这个图 所表示的分子是不稳定的。图g 的零度在数学上也很有意义，因为它和a ( g ) 的奇异性有关。 对于树的零度已经有一个精确公式( 见定理3 2 1 ) 。在 9 2 】中，柳柏濂教 授等研究了单圈图的零度，他们完全确定了死阶单圈图的零度集合，刻画 了达到最大零度的几阶单圈图；文献4 3 】中证明了：若g 是一个单圈图， 则7 7 ( g ) = 他一2 m ( c ) 一1 ，n 一2 m ( g ) 或者礼一2 m ( g ) + 2 ，其中m ( g ) 表示图g 的匹配数。 对于零度研究的其它结论参见文献f 8 5 】，【3 8 】， 3 0 】等。而对于双圈图零度目 前还没有这方面的结论。通过利用关于图的邻接矩阵特征值的几个经典结论我 们刻画t , 7 ( g ) = n 一2 的所有礼阶图和叩( g ) = n 一3 的所有n 阶图；证明了所 有礼阶( n 6 ) 双圈图的零度集合是 ，并且刻画了叩( g ) = n 一4 的所 有礼阶( n 9 ) 双圈图和叩( g ) = n 一5 的所有礼阶( n 1 0 ) 双圈图。 在图谱理论中对拉普拉斯矩阵的研究也已有相当长的历史，最早可追溯到 1 8 4 7 年k i r c h h o f f 在研究电流理论时所发现的矩阵一树定理。对图的拉普拉斯 特征值的研究不仅具有重要的理论价值，而且还有广泛的应用背景( 7 l 】) 。拉普 拉斯特征值与拉普拉斯微分算子，谱几何，网络理论，组合优化等数学分支均 密切相关，同时在物理，理论化学，计算机科学，电子工程学中均有重要的应 用。研究拉普拉斯特征值的方法主要有如下三种： ( 1 ) 代数方法：即用矩阵论并结合图的图论性质来研究拉普拉斯特征值，如 4 第l 章绪论 文献 3 5 】。 ( 2 ) 几何方法：即研究图的拉普拉斯矩阵l ( g ) = d ( g ) 一a ( g ) 所对应的二 次型，并结合图的图论性质来研究拉普拉斯特征值，或将图的规范拉普拉斯矩 阵d ( g ) 一l ( g ) d ( g ) 一言视为r i e m m a n n 流形上的拉普拉斯算子的离散形式， 从而将拉普拉斯算子理论引入到拉普拉斯特征值的研究中，如文献【1 5 】，【7 1 】。 ( 3 ) 概率方法：即通过引入随机路的概念，利用概率论的方法研究拉普拉斯 特征值，如文献 1 6 】。 另外，也可以借助于计算机来对拉普拉斯特征值进行研究，如文献 8 1 。在 本文中，我们主要利用代数方法和几何方法来对图的拉普拉斯特征值进行研 究。 考虑图的拉普拉斯特征值和其它图的诸多不变量的关系，如直径【1 5 】，等周 数【5 3 】，【5 4 ，最大割【5 5 】，扩充子【1 】，匹配数 4 4 】，控制数 6 7 】等等是一个重要 而有意义的工作，因为我们可以借助图的拉普拉斯特征值来估计图的某些不变 量。事实上有些图的不变量的计算是n p h a r d 问题，而拉普拉斯特征值则可用 多项式理论中渐近求根方法加以计算。 对于图的拉普拉斯谱半径( 即拉普拉斯矩阵最大的特征值，记作p ( g ) ) 和图 的最大度我们有如下关系： 引理1 1 3 3 5 】设g 是一个至少有一务边的n 阶连通图，则有 p ( g ) ( g ) + l ， 等式成立当且仅当a ( g 】= n 一1 通过利用图的变形技巧以及图的拉普拉斯特征多项式技巧我们确定 - f t ( n ，a ) ( a + 1 ) 2 ) 中拉普拉斯谱半径达到最大和次大的树，以 及丁( n ，a ) 中拉普拉斯谱半径达到最小的树。 c v e t k o v i 芒在1 2 1 中指出了图谱理论中进一步研究的十二个方向，其中之一就 是用图的谱对图进行分类和排序，此后各图类依谱，特别是依最大特征值( 即谱 半径) 的排序问题被大量研究( 见文献 5 8 1 ，【1 4 】，【4 2 】等) 。利用拉普拉斯谱半径 对树进行排序，最近也有一些结果出现。在【1 0 6 】中张晓东和李炯生给出了前三 个树；在f 4 8 1 中郭继明给出了前四个树；最近在【9 7 】中余爱梅、陆玫和f 开丰等给 出了前八个树。在郭继明的博士论文 4 6 】中，他进一步给出了前十三个树。 用兀表示7 , 阶树的集合，显然对兀有如下一个划分 5 同济大学博士学位论文 磊= 丁( n ，n 一1 ) u 丁( 佗，竹一2 ) u u t ( - ，1 ) 在第四章中我们证明了下述结论：设五，t 2 磊m 4 ) ，若( 丑) m + 3 ) 2r a ( t 1 ) z x ( t 2 ) ，n u ( t 1 ) p ( t 2 ) 。我们可以看出上述结论给具有较 大拉普拉斯谱半径的树( 比如对于所有满足a ( 佗+ 3 ) 2 的树) 的排序问题提供 了一个基本方法：当i ( t t + 3 ) 2 时，我们只需要考虑集合丁( 礼，i ) 中树( 按照拉 普拉斯谱半径排序) 的内序。 文 4 8 1 郭继明考虑了树的拉普拉斯谱半径和其匹配数的关系。用丁( 2 克) 表 示2 七阶具有完美匹配的树的集合。文 4 8 】给出t t ( 2 k ) 中拉普拉斯谱半径的 最大值，并确定了达到该谱半径相应的树。通过将7 ( 2 k ) 中树分类，我们确定 t t ( 2 k ) 中拉普拉斯谱半径的第二大至第六大值，并确定了达到这些值的相应 的树。 在图的拉普拉斯特征值中得到广泛研究的除了图的拉普拉斯谱半径就是图 的第- d , 拉普拉斯特征值，即代数连通度了。1 9 7 3 年，f i e d l e r 2 8 1 首先研究了 图的代数连通度，给出了图的代数连通度与图的点连通度、边连通度的关系。 自此以后，关于代数连通度的研究日益受到人们的重视，出现了大量的结果， 关于一般图的代数连通度的研究，可见文献 4 】， 2 4 】， 2 8 等；关于树的代数连 通度的研究，可见文献【3 2 ，3 6 ，6 0 】等。对代数连通度及其所对应的特征向量的 研究方面，早期的经典工作是f i e d l e r 在 2 8 】和【2 9 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 向量进行了 进一步的深入研究，见文献f 3 2 】 3 6 】 7 8 】最近，f a u a t 和k i r k l a n d 等通过引入 b o t t l e n e c k 矩阵，对一般图的代数连通度进行了研究，将代数连通度的研究推向 了一个新的层面，见文献【4 1 ，【2 4 ，【2 5 ，【2 6 ，【2 7 ， 6 1 1 ， 6 2 ， 6 3 ，【6 4 等。 关于代数连通度的最新综述文章 7 6 】中，作者总结了g r o n e ，m e r r i s 在 文 3 6 】中按照代数连通度大小对t t 阶树进行排序的一些结论，指出文 3 6 】中 所作的一些工作只是初步的，并提出按照代数连通度的大小给所有n 阶树一个 全序仍是一个公开问题。 树t 的代数连通度a ( t ) 和其p e r r o n 分支的b o t t l e n e c k 矩阵m 之间有一个重 6 第1 章绪论 要的关系，就是 q ( t ) 南， 其o o p ( m ) 表示( 实对称) 矩阵m 的最大特征值。我们给出了上述等式成立情形 的一个完全刻画。 通过将所有礼阶树按照其直径分类讨论，我们确定了满足a ( t ) 2 一、，信的 所有礼( n 1 5 ) 阶树t ；同时按照代数连通度的大小给这些树一个完全排序。这 些结论将3 谳 3 6 1 中按照代数连通度的大小对树进行排序的工作做了一个很大推 进。 下面两节中我们分别介绍图谱理论中的一些基本概念和常用结论。 1 2 基本概念 在本文中，所用到的未加定义的图论和矩阵论中的一些基本定义和术语可 见文献【1 0 】，【1 1 】和【5 7 】。 本文所研究的图都是有限、无向、无环、无重边的简单图。设g 是一个点 集为v ( a ) = 1 ，v 2 ，) ，边集为e ( g ) = e 1 ，e 2 ，e m ) 的简单图。当点v i 和u ，是边e 的端点时，我们记e = 仇口，并称点v i 和叼相邻。记点u 在g 中所有 邻点的集合为n g ( v ) ，点 的度记为d g ( 秒) ，或者分别简记为n ( v ) 和d ( ) 。 若m 是一个礼阶方阵且其特征值全为实数，我们不妨用h ( m ) 表示它的 第k 大的特征值，特别令 p ( m ) = m a x i , k i ( m ) i ：i = l ，2 ，n ， 称为m 的谱半径。图g 的邻接矩阵定义为一个n 佗矩阵a ( g ) = ( a i j ) ，其中 f 1 ， 若陇和相邻； ” 10 ， 否则 若g 是一个简单图，则a ( g ) 是一个实对称( 0 ，1 ) 矩阵且其主对角线上的 元素全为零，从而它的特征值全为实数。不失一般性，可以假设它们按照如下 从大到小的顺序排列为 a l ( g ) 入2 ( g ) 入n ( g ) 且称a 七( g ) 为图g 的第k 大邻接特征值。矩阵a ( g ) 的所有特征值称为g 的 邻接谱，特别地，称a l ( g ) 为图g 的邻接谱半径，记为p ( g ) 。 7 同济大学博士学位论文 记d ( g ) = d i a g ( d ( v 1 ) ，d ( v 2 ) ，d ( ) ) 为图g 的度对角矩阵，图g 的拉普 拉斯矩阵定义为l ( g ) = d ( g ) 一a ( g ) 。对图g 的每一条边，取其一个端点为 始点，另一端点为终点，这一过程称为给图g 一个定向。当图g 取定一定向 时，其定向关联矩阵定义为q = q ( g ) = ( ) ，其中， i1 ，当v i 是边e f 的始点时； = 一1 ，当v i 是边白的终点时； 【o ，其它 则l ( g ) = q ( g ) q ( g ) r ( 其中q ( g ) t 是矩阵q ( g ) 的转置矩阵) 且l ( g ) 与 g 的定向无关( 见 5 2