（应用数学专业论文）图的拉普拉斯谱的一些极值和排序问题.pdf

摘要 摘要 在图论中，为了研究图的性质，人们引进了各种各样的矩阵，诸如图的邻 接矩阵，关联矩阵，距离矩阵，拉普拉斯矩阵等等，这些矩阵与图都有着自然 的联系。代数图论的一个主要问题就是研究图的性质能否以及如何由这些矩阵 的代数性质反映出来，这里所指的矩阵的代数性质，主要指矩阵的特征值。 在上面所提到的矩阵中，最重要的有两个：图的拉普拉斯矩阵和邻接矩 阵。图的拉普拉斯矩阵的特征值和邻接矩阵的特征值都是图的在同构下的不 变量，图的邻接矩阵及其特征值是代数图论的一个基本的研究课题。在过去 的几十年中，人们对图的邻接矩阵的特征值已经进行了大量的研究( 见文献 f 6 ，1 4 ，1 5 1 ) 。和图的邻接矩阵相比，由于在拉普拉斯矩阵中含有图的顶点度的 信息，因此图的拉普拉斯矩阵的特征值与图的很多不变量之间有着更加密切的 联系。正如m o h a r 【8 6 1 所说：图的拉普拉斯矩阵的特征值更能反映它的图论性 质。因此，对图的拉普拉斯矩阵的特征值的研究越来越受到人们的广泛关注。 人们对拉普拉斯矩阵的研究，可以追溯到1 6 0 多年以前。拉普拉斯矩阵最 著名的应用是在1 8 4 7 年k i r c h h o f f 研究电流理论时所发现的如下的矩阵一树定 理： 矩阵一树定理：设g 是一个有n 个顶点的连通图且l ( g ) 是 它的拉普拉斯矩阵，去掉l ( g ) 的第i 行及第j 列得到一个 礼一1 阶的子矩阵，记为l ( i l j ) 。则l ( i l j ) 的行列式的绝对 值等于图g 的生成树的个数。 因此，图的拉普拉斯矩阵有时被称为k i r c h h o f f 矩阵。又因为拉普拉斯矩阵在人 们研究电路网络时有着重要应用，因此，该矩阵也被称为容许矩阵。在数学物 理上，由于拉普拉斯矩阵可以被视为拉普拉斯微分算子的离散情形 8 6 】，故该 矩阵一般被称为拉普拉斯矩阵。图的拉普拉斯矩阵的特征值被称为图的拉普拉 斯特征值。 图的拉普拉斯特征值有很多的应用。例如，在物理和化学的很多问题中， 拉普拉斯特征值起到中心的作用( 见【2 1 ，2 2 ，2 3 ，2 4 ，2 5 1 ) 。因此，拉普拉斯特征 值不仅引起了数学家的关注，而且也引起了不少物理学家和化学家的重视。拉 普拉斯特征值也可以被用来给出图的几何表示( 见【4 2 】p 2 8 4 ) ，而这与图论中近 来最重要的进展之一一图的c o l i nd ev e r d i d r e 数有着密切的关系 6 0 】。 同济大学博士学位论文 本文主要研究图的拉普拉斯特征值，具体分为如下三个方面：一是对图的 第二大拉普拉斯特征值的研究：二是对目的拉昔拉斯谱半径的研究；三是列圈 音勺代数连通度的研究。 在第1 章中，我们介绍了与图和拉普拉斯矩阵有关的基本概念以及矩阵论 中的一些基本定理。 在第2 章中，我们研究了n 阶树的第二大拉普拉斯特征值 z ( t ) 的最大 值和排序问题。关于这一问题，当n 是偶数的情形，张晓东和李炯生在1 0 2 1 中已经解决了最大值的问题。但对n 是奇数情形时的晟大值问题却一直没有 解决。本章中，我们确定了奇数阶树的第二大拉普拉斯特征值的虽丈与次大 值：即阶为2 + 10 4 ) 的树t 的第二大拉普拉斯特征值儿( t ) 的最大值是 妻0 + 1 + 、万干瓦= j ) ，次大值是方程一一( 2 t + 3 ) x 2 + ( t 2 + 3 t + 3 ) x 一( 2 t + 1 ) = 0 的第二大根；且进一步找出了达到最大值的唯一的树丑及达到次大值的唯一的 树正。我们还研究了具有几乎完美匹配的树的第二大拉普拉斯特征值，给出了 几乎完美匹配树的第二大拉普拉斯特征值的一个上界。 对图的拉普拉斯特征值而言，最重要的两个特征值足最大的拉普拉斯特征 值和第二小的拉普拉斯特征值，分别称为图的拉普拉斯谱半径和代数连通度。 最近，人们发现拉普拉斯谱半径在理论化学上有重要的应用见文献f 5 5 ，5 6 1 ：留 的代数连通度还可以被用来研究一些困难的图论问题，例如：图的扩展性质f 1 1 ， 等周数【8 3 ，8 4 卜昂大割问题【8 5 卜以及图的直径 1 1 】等等。在第3 章和第4 章 中，我们将分别讨论圈的这两个拉普拉斯特征值。 在第3 章中我们研究了树的拉普拉斯谱半径。关于这一问题，郁嘉裕， 袁西英跟何常香在1 1 6 1 中对具有完美匹配的树按照拉普拉斯谱半径进行了排 序。但关于几乎完美匹配树的拉普拉斯谱半径，只有郭继明在5 1 1 中，确定了 几乎完美匹配树的拉普拉斯谱半径的最大值，并且给出了相应的极树。我们在 郭继明已确定屉大值的基础上，进一步确定了n 阶几乎完美匹配树的拉普拉斯 谱半径的第二到第六大的值，并且给出了达到这五个值的相应的树。 在第4 章中，我们研究了图的代数连通度。用正k + 1 表示阶为2 女+ 1 的 具有几乎完美匹配的树的集合，o ( t ) 表示树t 的代数连通度。我们确定了 几乎完美匹配树的代数连通度的第一大，第五大及第十二大的具体数值。 在正+ 1 中特别定义了十棵树马，马， ，正- 及两类树t ( 1 ) 和t ( 1 2 ) 。我们 证明了对于任意的树q ，矸t 0 ) 和任意的树q ：，t ( 1 2 ) ，我们有 口( 冠) = 。( 野) n ( 五) 口( t j ) a ( 掣2 ) = 口( 咒) ，其中2 曼i 口口) 。 关键词：图，邻接矩阵，拉普拉斯矩阵，特征多项式，特征向量，拉普拉斯特 征值，拉普拉斯谱半径，代数连通度，树，完美匹配，几乎完美匹配，直径， 上( 下) 界 i i i 同济大学博士学位论文 a b s t r a c t i no r d e rt os t u d yt h ep r o p e r t i e so fg r a p l l s ，p e o p l ei n t r o d u c ev a r i o u sm a t r i - c e si n t og r a p ht h e o r y , s u c ha 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 e d i s t a n c em a t r i xa n dt h el a p l a c i a nm a t r i x ，e t c t h e s em a t r i c e sa r en a t u r a l l ya s - s o c i a t e dw i t hf a p h s 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 s t 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 印h sa r er e f l e c t e di nt h e a 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 h s b o t ht h ee i g e n v a l u e so f t 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 su n d e r i 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 cg r a p h t h e o r y , w h i c hw a s m 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 so ft h e l a p l a c i a nm a t r i x t h er e a d e ri sr e f e r r e dt ot h em o n o g r a p h s 6 ，1 4 ，1 5 h o w e v e r ， 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 xh 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 h i n v a r i a n t s ( s e e 8 6 】a n dt h er e f e r e n c e st h e r e i n ) ，i ti sj u s t 鹪m o h a ri s 6 】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 r i x ”s ot 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 xa r ea t t r a c t i n gm o r ea n dm o r e a t t e n t i o n s t h es t u d yo fl a p l a c i a nm a t r i c e sh a sal o n gh i s t o r y t h em o s tr e n o w n e d a p p l i c a t i o no ft h el a p l a c i a nm a t r i xl ( g ) 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 【6 5 】 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 nnv e r t i c e sa n dl e t l ( i l j ) b et h es u b m a t r i xo fl ( g ) o b t a i n e db yd e l e t i n gi t si t h r o wa n dj 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 t o fl ( il j ) i se q u a lt ot h en u m b e ro fs p a n n i n gt r e e so ft h eg r a p h g s ot h el a p l a c i a nm a t r i xi ss o m e t i m e sc a l l e dt h ek i r c h h o f fm a t r i x a n o t h e rn a m e ， t h em a t r i xo fa d m i t t a n c ec o m e sf r o mt h et h e o r yo fe l e c t r i c a ln e t w o r k s ( a d m i t - t a n c e = c o n d u c t i v i t y ) 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 sad 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 6 s oi ti so f t e nc a l l e d a b s t r a c t t h el a p l a c i a nm a t r i xo fag r a p h 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 fa g r a p ha 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 t h e r ea r em a n ya p p l i c a t i o n sf o rl a p l a c i a ne i g e n v a l u e so fg r a p h s f o re x a m p l e ， t h e r ea r em a n yp r o b l e m si np h y s i c sa n dc h e m i s t r yw h e r et h el a p l a c i a ne i g e n v a l u e s p l a yt h ec e n t r a lr o l e ( s e e 2 1 ，2 2 ，2 3 ，2 4 ，2 5 1 ) s ol a p l a c i a ne i g e n v a l u e sa r en o t o n l vf u l lo fi n t e r e s tt om a t h e m a t i c i a nb u ta l s ot oc h e m i s t sa n dp h y s i c i s t s t h e l a p l a c i a ne i g e n v a l u e sa l s oc a n b eu s e di nan u m b e ro fw a y st op r o v i d ei n t e r e s t i n g g e o m e t r i cr e p r e s e n t a t i o n so fag r a p h ( s e e 4 2 1p 2 8 4 ) t h i si s r e l a t e dt ot h e c o l i nd e v e r d i d r en u m b e ro fag r a p h ，w h i c hi so n eo ft h em o s ti m p o r t a n tr e c e n t d e v e l o p m e n t si ng r a p ht h e o r y 【6 0 i nt h i sp a p e r ，t h r e et o p i c so nl 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 ns t u d - i e d t h ef i r s ti st h es t u d yo nt h es e c o n dl a r g e s tl a p l a c i a ne i g e n v a l u e so fg r a p h s ； t h es e c o n di st h es t u d yo nt h el a p l a c i a ns p e c t r a lr a d i u so fg r a p h s ；t h et h i r di s t h es t u d yo nt h ea l g e b r a i cc o n n e c t i v i t yo fg r a p h s i nc h a p t e r1 。w ei n t r o d u c ee l e m e n t a r yn o t a t i o n sr e l a t e dt oag r a p ha n dl a p l a - c i a nm a t r i xa n dk n o w nt h e o r e m so nm a t r i xt h e o r y i nc h a p t e r2 ，w es t u d yt h es e c o n dl a r g e s tl a p l a c i a ne i g e n v a l u eo fat r e et o fo r d e r 礼w h e n 钆i sa ne v e nn u m b e r ，z h a n gx i a o - d o n ga n dl ij i o n g - s h e n g h a v es e t t l e dt h el a r g e s tv a l u eo f 入2 ( t ) i n 1 0 2 b u tw h e nni sa no d dn u m b e r ， t h ep r o b l e mh a sn o tb e e ns e t t l e d i nt h i sp a p e r ，w es t u d yt h el a r g e s tv a l u e a n dt h es e c o n dl a r g e s tv a l u eo ft h es e c o n dl a p l a c i a ne i g e n v a l u e 入2 口) a m o n ga l l t r e e sto fag i v e no d do r d e r2 t + 1 w es h o wt h a tt h el a r g e s tv a l u eo fa 2 ( t ) a m o n ga l lt r e e st o fo r d e r2 t + 1 ( t 4 ) i s 去( t + 1 + 、t 2 + 2 t 一3 ) ，w h i l et h e s e c o n dl a r g e s tv a l u eo f 入2 ( t ) i st h es e c o n dl a r g e s tr o o to ft h ec u b i ce q u a t i o n z 3 一( 2 t + 3 ) x 2 + ( t 2 + 3 t + 3 ) x 一( 2 亡+ 1 ) = 0 w ea l s od e t e r m i n et h eu n i q u e t r e e7 1o fo r d e r2 t + 1w h o s ea 2 ( 丑) r e a c h e st h i sl a r g e s tv a l u e ，a n dd e t e r m i n e t h eu n i q u et r e et 2o fo r d e r2 t + 1w h o s ex 2 ( t 2 ) r e a c h e st h i ss e c o n dl a r g e s tv a l u e a l s o ，w es t u d yt h es e c o n dl a r g e s tl a p l a c i a ne i g e n v a l u e s o ft r e e sw i t hn e a r l yp e r f e c t m a t c h i n g s w eg i v ea l lu p p e rb o u n do ft h es e c o n dl a r g e s tl a p l a c i a ne i g e n v a l u e s o ft r e e sw i t hn e a r l yp e r f e c tm a t c h i n g s f o rt h el a p l a c i a ne i g e n v a l u e so f l a r g e s tl a p l a c i a ne i g e n v a l u ea n dt h e g r a p h s ，t h em o s ti m p o r t a n tt w oa r et h e t h es e c o n ds m a l l e s tl a p l a c i a ne i g e n v a l u e v w h i c ha r ec a l l e dt h el a p l a c i a ns p e c t r a lr a d i u sa n dt h ea l g e b r a i cc o n n e c t i v i t y , r e s p e c t i v e l y r e c e n t l y , t h el a p l a c i a ns p e c t r a lr a d i u s a p p l i c a t i o n so nt h e o r e t i - c a lc h e m i s t r yh a v eb e e nf o u n d 5 5 ，5 6 】；t h ea l g e b r a i cc o n n e c t i v i t y sa p p l i c a t i o n s t os e v e r a ld i f f i c u l tp r o b l e m si ng r a p ht h e o r yw e r ed i s c o v e r e d ，e g t h ee x p a n d i n g p r o p e r t i e so fg r a p h s 1 】t h ei s o p e r i m e t r i cn u m b e r 【8 3 ，8 4 ，t h em a x i m u m c u tp r o b - l e m 8 5 1 ，a n dt h ed i a m e t e r 【11 】e t c i nt h en e x tt w oc h a p t e r s ，w ew i l li n v e s t i g a t e t h et w ol a p l a c i a ne i g e n v a l u e so fg r 印l l s ，r e s p e c t i v e l y i nc h a p t e r3 ，w 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 io ft r e e s a b o u tt h i s p r o b l e m ，j i a - y us h a o ，x i o y i n gy u a na n dc h a n g - x i a n gh e h a v eo r d e r e dt r e e sw i t h p e r f e c tm a t c h i n g sb yt h e i rl a p l a c i a ns p e c t r a lr a d i ii n 11 6 b u ta b o u tt r e e sw i t h n e a r l yp e r f e c tm a t c h i n g s ，j i - m i n gg u o d e t e r m i n e dt h el a r g e s tl a p l a c i a ns p e c t r a l r a d i io ft r e e sw i t hn e a r l yp e r f e c tm a t c h i n g sa n dg a v et h ec o r r e s p o n d i n gt r e e si n 5 1 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 tl a p l a c i a ns p e c t r a lr a d i ia m o n g a l lt h et r e e sw i t hn e a r l yp e r f e c tm a t c h i n g sa n dg i v et h ec o r r e s p o n d i n gt r e e s c h a p t e r4i sd e v o t e dt ot h ea l g e b r a i cc o n n e c t i v i t yo fg r a p h s l e t 五七+ 1b e t h es e to ft r e e so n2 k + lv e r t i c e sw i t hn e a r l yp e r f e c tm a t c h i n g sa n da ( t ) b e t h ea l g e b r a i cc o n n e c t i v i t yo fat r e et w ed e t e r m i n et h ef i r s tl a r g e s t ，t h ef i f t h 。 l a r g e s ta n dt h et w e l f t hl a r g e s tv a l u e so ft h ea l g e b r a i cc o n n e c t i v i t yo ft h et r e e si n 五七+ 1 s p e c i f i c a l l y , w ei n t r o d u c e1 0t r e e st 2 ，t 3 ，t na n dt w oc l a s s e so ft r e e s t ( 1 ) a n dt ( 1 2 ) i n 正七+ 1 w es h o wi nt h i sp a p e rt h a tf o re a c ht r e e 正，t t ( 1 1 ，7 a n dt 2 ，t ( 1 2 ) a n de a c hi ，歹w i t h2 i q ( 丑) a ( 乃) q ( 砰2 ) = q ( 7 琶) a l s o ，w es h o wt h a tf o re a c ht r e et w i t ht 五七+ 1 ( t o ) u 疋，噩，丑1 ) u t ( 1 2 ) ) ，w eh a v eq ( 墨2 ) q 口) k e y w o r d s ：g 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 ，c h a r a c t e r i s t i cp o l y - n o m i a l ，e i g e n v e c t o r ，l a p l a c i a ne i g e n v a l u e s ，l a p l a c i a ns p e c t r a lr a d i u s ，a l g e b r a i c c o n n e c t i v i t y , t r e e ，p e r f e c tm a t c h i n g s ，n e a r l yp e r f e c tm a t c h i n g s ，d i a m e t e r ，u p p e r ( 1 0 w e r ) b o u n d v i 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定，同意如下 各项内容：按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学 位论文的印刷本和电子版，并采用影印、缩印、扫描、数字化或其它手段保存 论文；学校有权提供目录检索以及提供本学位论文全文或者部分的阅览服务； 学校有权按有关规定向国家有关部门或者机构送交论文的复印件和电子版；在 不以赢利为目的的前提下，学校可以适当复制论文的部分或全部内容用于学术 活动。 学位论文作者签名： 年月 日： 经指导教师同意，本学位论文属于保密，在年解密后适用本授权书。 指导教师签名： 年月日 学位论文作者签名： 年月 日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、己公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 年月 日 第1 章绪论 第1 章绪论 1 1 研究背景与进展 图论是一门既古老叉年轻的学科。说它古老因为它可以追溯到十八世纪的 欧拉。讲图论没有不提到柯尼斯堡七桥问题的，欧拉解决它用到的图的方法确 是非常典型的例子。但它成为一门学科，还是近几十年的事。这与计算机技术 的飞速发展足分不开的。在计算机科学蓬勃发展的刺激下，图论获得一个很大 的发展空问。在计算机的很多领域，它都占有一席之地。随着信息时代的发 展，作为网络技术的理论基础和研究工具的重要部分，图论更日益显现出其在 计算机领域的强大活力。不仅如此，它在物理学、生物学、电子工程、运筹 学，以及社会科学等领域都有着广泛的应用。因次，无论从图论的理论价值， 还是其实际应用的广度和深度来看，图论的研究与发展正处于一个充满活力， 蓬勃发展的新时期。 图谱理论是图论和组合论研究的重要领域之一，图谱在量子化学，统 计力学，通信网络，信息科学等学科中有一系列的重要应用。早在1 9 3 1 年 eh 礼c k e l 等理论化学家就对图谱理论产生了浓厚的兴趣，着手开始进行研 究。尽管他们所采用的符号和术语跟现在大家所使用的不一致，但是他们的研 究对图谱理论的发展有着重要的推动作用。正是因为诸多著名的组合，图论及 代数方面的数学家以及理论化学，物理学家都在这一领域做了很多深入的研究 工作，使得图谱理论在近二十年来成为图论中一个非常活跃的研究领域。 图的谱理论主要涉及图的邻接( 矩阵的) 谱和图的拉普拉斯( 矩阵的) 谱，是图论( 特别是代数图论) 和组合矩阵论共同关注的一个重要课题。其研 究的主要途径是，通过图的矩阵( 邻接矩阵，拉普拉斯矩阵等) 表示建立图的 拓扑结构( 特别是图的各种不变量) 和图的矩阵表示的置换相似不变量之间的 联系，通过矩阵论，特别是非负矩阵理论和对称矩阵理论，和组合矩阵论中的 经典理论用于图的拓扑结构的研究，同时也将图谱理论的经典结论用于非负矩 阵理论和组合矩阵论，以推动后者的理论研究。 对图的邻接矩阵的特征值的研究，最早起源于量子化学领域。1 9 3 1 年 eh 乱c k e l 在f 1 1 3 1 中引进的对非饱和碳氢化台物的一种近似处理产生了对应 分子的图论模型，其中图的特征值被用来表示特定电子的能量级。很多年以 同济大学博士学位论文 后，eh i g z k e t 模型与图谱的数学理论之间的联系在f l 7 】和【13 】中才被认识 到，并且从此被众多的研究者，化学家和数学家广泛开发利用。对图的邻接谱 的研究，目前已形成比较成熟的理论，详见专著6 ，1 4 ，1 5 1 。 图的拉普拉斯谱是图谱理论中的另一研究领域。与图的邻接谱相比，由于 图的拉普拉斯谱不但要比图的邻接谱包含更多的信息，且与图的结构之间有着 更自然的联系，更能反映图的罔论性质( bm o h a r 语8 6 1 ) ，因此对拉普拉斯 矩阵的特征值的研究越来越引起人们的关注。 对拉普拉斯矩阵的研究已有相当长的历史，最早可追溯到1 8 4 7 年k i r c h h o f f 在研究电流理论时所发现的矩阵一树定理。对图的拉普拉斯特征值的研究不仅具 有重要的理论价值，而且还有广泛的应用背景f 8 6 1 。拉普拉斯特征值与拉普拉 斯微分算子，谱几何，网络理论，组合优化等数学分支均密切相关，同时在物 理，理论化学，计算机科学，电子工程学中均有重要的应用。 自二十世纪九十年代以来，关于罔的拉普拉斯特征值的综述性文章很多， 如m e r r i s ，m o h a r 等及时报道了该领域的新进展，新问题，而f rkc h u n g 在1 9 9 4 年世界数学家大会( 瑞士苏黎士) 上的4 5 分钟报告及其专著的问世更将 拉普拉斯矩阵的研究推到了一个新的高度。正如m o h a r 指出，在图g 的拉普 拉斯特征值中，最重要的是极端非平凡特征值：次小拉普拉斯特征值和晟大拉 普拉斯特征值。由于n 阶图g 及其补图酽的拉普拉斯特征值有如下的关系： 对于2 i sn ，a 。= n k 卅因此次小拉普拉斯特征值和最大拉普拉斯特征 值的估计是可以互推的。 研究拉普拉斯特征值的方法主要有如下三种： ( i ) 代数方法：即用矩阵论并结合图论性质来研究拉普拉斯特征值，如文 献f 4 7 1 。 ( 2 ) 几何方法：即研究图的拉普拉斯矩阵l ( g ) = d ( g ) 一a ( g ) 所对应 的二次型并结合图的性质来研究拉普拉斯特征值或将图的规范拉普拉斯矩阵 d ( g ) 一 工( g ) 口( g ) 一 视为r i e m m a n n 流形上的拉普拉斯算子的离散形式，从 而将拉普拉斯算子理论引入到拉普拉斯特征值的研究中，如文献l l ，8 6 1 。 侣) 概率方法：即通过引入随机路的概念，利用概率论的方法研究拉普拉 斯特征值，如文献1 2 1 。 另外，也可以借助于计算机来对拉普拉斯特征值进行研究，如文献9 1 。 在本文中，我们主要利用代数方法和几何方法来对图的拉普拉斯特征值进行研 2 第1 章绪论 究。 利用代数方法和几何方法对拉普拉斯特征值进行研究，主要有以下几个方 面： ( 一) 对拉普拉斯谱半径的研究。主要是利用图的顶点度来给出拉普拉斯谱 半径的可达上界，该方面最早的工作是1 9 8 5 年a n d e r s o n 和m o r l e y 2 】给出的 如下上界： 设g = ( ke ) 是有n 个顶点的图，则 p ( g ) d t - i - d u ：u 口e ) ， 等式成立当且仅当g 是二分正则图或g 是二分准正则图，其中p ( g ) 表示图g 的拉普拉斯谱半径。 1 9 9 7 年，李炯生和张晓东在 7 4 1 中改进了a n d e r s o n - m o r l e y 的上界。自此 以后，有关拉普拉斯谱半径的上界大量涌现，见文献【1 8 ，1 9 ，7 3 ，7 5 ，7 6 ，8 0 ，9 1 ， 9 4 ，1 0 3 】。最近，一个有意义的工作是b r a n k o v , h a n s e n 和s t e v a n o v i c 9 】对已 有的上界进行了研究和比较并利用计算机给出了一些关于拉普拉斯谱半径的上 界的猜想。 另外，在文献( 4 7 1 中，g r o n e 等人考虑了对某些特殊图类进行收缩运算 后，拉普拉斯谱半径的变化情况。 郭继明在 1 0 4 】中给出了图的拉普拉斯谱半径的若干个新的上界，对某些实 例，这些上界要优于己知的结果，同时也给出了一个二分图的拉普拉斯谱半径 的可达下界；他还在【1 0 6 】中研究了在图的几种运算下( 例如：加边运算，嫁接 运算，剖分运算，移边运算等) ，拉普拉斯谱半径的变化情况。 ( 二) 对代数连通度及其所对应的特征向量的研究。该方面早期的经典工作 是f i e d l e r 在【3 5 】和 3 6 】中分别研究了图的代数连通度及其所对应的特征向量， 提出了用代数连通度所对应的特征向量来研究代数连通度的新思路。因此， 代数连通度所对应的特征向量通常被称为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 向量进行了进一步的深入研究，见文 献4 4 ，4 5 ，7 7 1 。f a l l a t 和k i r k l a n d 等通过引入b o t t l e n e c k 矩阵，对一般图的 代数连通度进行了研究，将代数连通度的研究推向了一个新的层面，见文献 3 ，3 0 ，3 1 ，3 2 ，3 3 ，6 6 ，6 7 ，6 8 ，6 9 】。最近，n a i rm a f i a m a i ad ea b r e u 在综述性文 章 1 1 4 1 中对图的代数连通度的新旧结果进行了总结。 ( 三) 对拉普拉斯特征值与图的不变量之间关系的研究。该方面的早期工作 3 同济大学博士学位论文 是f e d l e r 在文献f 3 5 1 中给出了代数连通度与图的连通度，边连通度之间的如 下关系： 设g 是n 阶图，则 ( 1 ) g 连通的充要条件是其代数连通度o ( g ) 0 ； ( 2 ) 设图g 的连通度和边连通度分别为v ( g ) 和e ( g ) ，则有 n ( g ) v ( c ) 茎e ( g ) 进一步的研究发现，可以用拉普拉斯特征值来估计图的诸多不变量，如连 通度【3 8 】，直径 1 1 卜宽带【2 9 1 ，- - 部宽【2 6 卜等周数【8 6 】，最大割【8 5 】，超缩 子和扩充子【l j l ，平均距离【2 卅，边前项指数 2 8 】等等。其中一些重要的不变 量，如图的二部宽，最大割，等周数等除了反映图的一些结构性质外，还有广 泛的应用，然而它们计算的复杂度属于n p h a r d 的，而计算图的拉普拉斯 特征值则可用多项式理论中渐近求根方法加以计算。 ( 四) 对图的其它拉普拉斯特征值的研究。在文献| 4 3 ，4 7 ，7 8 1 中，g r o n e 等 研究了拉普拉斯特征值落在某一区间上的重数；在文献7 2 1 中，李炯生等研 究了图的第二大拉普拉斯特征值，给出了第二大拉普拉斯特征值的一个可达 下界；p a t i 【8 9 】研究了图的第三个晟小的拉普拉斯特征值及其所对应的特征向 量。郭继明在1 0 5 】中通过研究图的拉普拉斯特征多项式，巧妙的将拉普拉斯矩 阵分块，从而得到有关拉普拉斯特征多项式计算的一些基本公式，进一步得到 了树的第二大拉普拉斯特征值的一些可达的上下界和树的第k 大拉普拉斯特征 值的可达上界【1 1 0 】，他还在f 1 0 8 】中利用拉普拉斯特征多项式，研究了具有固 定直径的树的拉普拉斯谱半径。最近郭继明在1 1 1 1 中研究了图的第三大的拉普 拉斯特征值。 在本文中，我们主要做了如下一些工作： ( 一) 对树的第二大拉普拉斯特征值进行了研究。 运用矩阵论的知识及拉普拉斯特征多项式计算的一些基本公式，首先给出 奇数阶树的第二大拉普拉斯特征值的晟大及次大值，并且给出了达到这两个值 的唯一的树( 第- - 章第- - 节) ；其次给出了几乎完美匹配树的第二大拉普拉斯特 征值的一个上界f 第= 章第= 节) 。 ( 二) 对几乎完美匹配树的拉普拉斯半径进行了研究。 邵嘉裕，袁西英跟何常香在1 1 6 1 中对具有完美匹配的树进行了排序。郭继 明在【5 1 】中，确定了几乎完美匹配树的拉普拉斯谱半径的最大值，并且给出了 4 第1 章绪论 相应的极树。我们利用他们的结论及拉普拉斯特征多项式计算的一些基本公式 等对具有几乎完美匹配的树的拉普拉斯半径进行了排序，确定了几乎完美匹配 树的拉普拉斯谱半径的第- - n 第六大的值，并且找出了达到这五个值的相应的 树( 第三章) 。 ( 三) 对几乎完美匹配树的代数连通度进行了研究。 利用k i r k l a n d ，n e w m e m n 和s h a d e r 在f 6 6 1 中关于第1 类树及第1 i 类树的 特征刻画及我们推广的g r o n e 与m e r r i s 在【4 5 】中得到的关于第1 i 类树的代数 连通度在“夺邻”运算下的变化规律等，对几乎完美匹配树按照代数连通度进 行了排序，找出了代数连通度前十二大的值对应的所有树且确定了几乎完美匹 配树的代数连通度的第一大，第五大及第十二大的具体数值( 第四章) 。 1 2 基本概念 设g = ( ve ) 是有n 个顶点的简单连通图( 不含环和多重边) ，其 中v = 1 ，u 2 ，) 表示点集合，e = e l ，e 2 ，e m ) 表示边集合。图g 的邻接矩阵定义为一个n n 矩阵a ( g ) = ( a i f ) ，其中当7 3 i 和相邻时 a i j = 1 ；当仇和u j 不相邻时a t ，= 0 。令d ( v i ) 表示顶点忱的度，哦( g ) 表 示g 的第i 大的度，即有d 1 ( g ) d 2 ( g ) d n ( g ) ，l g i 或i y ( g ) i 表示 图g 的顶点数。图g 的拉普拉斯矩阵定义为l ( g ) = d ( g ) 一a ( g ) ，其中 d = d ( g ) = d i a g ( d ( v 1 ) ，d ( 忱) ，d ( v n ) ) 是图g 的度对角矩阵。对图g 的每 一条边，取其一个端点为始