（基础数学专业论文）图的拉普拉斯特征值.pdf

同济大学博士学位论文 摘要 在图论中，为了研究图的性质，人t 1 引进了各种各样的矩阵，诸如图的邻 接矩阵，关联矩阵，距离矩阵，拉普拉斯矩阵等等。这些矩阵与图都有着自然 的联系。代数图论的一个主要问题就是研究图的性质能否以及如何由这些矩阵 的代数性质反映出来。这里所指的矩阵的代数性质，主要指矩阵的特征值。 在上面所提到的矩阵中，最重要的有两个：图的拉普拉斯矩阵和邻接矩 阵。图的拉普拉斯矩阵的特征值和邻接矩阵的特征值都是图的在同构下的不变 量，图的邻接矩阵及其特征值是代数图论的一个基本的研究课题。对于图的拉 普拉斯矩阵的特征值而言，在过去的几十年中，人们对图的邻接矩阵的特征值 已经进行了大量的研究( 见文献6 ，1 3 ，1 4 1 ) 和图的邻接矩阵相比，由于在拉 普拉斯矩阵中含有图的顶点度的信息，因此图的拉普拉斯矩阵的特征值与图的 很多不变量有着更加密切的联系。正如m o h a 7 9 1 所说：图的拉普拉斯矩阵的 特征值更能反映它的图论性质。所以，对图的拉普拉斯矩阵的特征值的研究越 来越受到人们的广泛关注。 人们对拉普拉斯矩阵的研究，可以追溯到1 6 0 多年以前。拉普拉斯矩阵最 著名的应用是在1 8 4 7 年k i r c h h o f f 研究电流理论时所发现的如下矩阵一树定理 中： 矩阵一树定理：设g 是一个有n 个顶点的连通图且l ( g ) 是 它的拉普拉斯矩阵，去掉l ( g ) 的第i 行及，列得到一个 n 一1 阶的子矩阵，记为l ( i l j ) 。则l ( i l j ) 的行列式的绝对 值等于图g 的生成树的个数。 因此，图的拉普拉斯矩阵有时被称为k i r c h h o f f 矩阵。又因为拉普拉斯矩阵 在人们研究电路网络时有着重要应用，因此，该矩阵也被称为容许矩阵。在数 学物理上，由于拉普拉斯矩阵可以被视为拉普拉斯微分算子的离散情形f 7 9 1 ，故 在数学上，该矩阵一般被称为拉普拉斯矩阵。图的拉普拉斯矩阵的特征值被称 为图的拉普拉斯特征值。 图的拉普拉斯特征值有很多的应用。例如，在物理和化学的很多问题中， 拉普拉斯特征值起到中心的作用( 见f 1 9 ，2 0 ，2 1 ，2 2 ，2 3 1 ) 。拉普拉斯特征值也可 以被用来给出图的几何表示( 见 3 5 1p 2 8 4 ) ，而这与图论中近来最重要的进展之 一一图的c o l i nd ev e r d i d r e 数有着密切的关系【5 3 1 。因此，拉普拉斯特征值不仅 引起了数学家的关注，而且也引起了不少物理学家和化学家的重视。 本文的研究内容主要分如下五个方面：一是对拉普拉斯特征多项式的研 究；二是对拉普拉斯谱半径的研究；三是对代数连通度的研究；四是对树的拉 普拉斯特征值的研究：最后是对图的其它拉普拉斯特征值的研究。 众所周知，图的邻接矩阵的特征多项式在研究邻接矩阵的特征值时有着非 常重要的作用。然而，目前我们对图的挣普 = f ) ：斯矩阵的特征多项式知之甚少。 在第l 章中，我们介绍了与拉普拉斯矩阵有关的基本概念以及矩阵论中的一些 基本定理。更主要的是，在第1 章中，我们对图的拉普拉斯矩阵的特征多项式 进行了研究，得到了一些基本的公式。在后面的几章中，我们将发现图的拉普 i v 摘要 拉斯矩阵的特征多项式在研究图的拉普拉斯特征值的时候将起到非常关键的作 用。 对图的拉普拉斯特征值而言，最重要的两个特征值分别是最大的拉普拉斯 特征值和第二小的拉普拉斯特征值。在第2 章和第3 章中，我们将分别讨论图 的这两个拉普拉斯特征值。 图的拉普拉斯谱半径是指图的拉普拉斯矩阵的最大特征值。最近，人们发 现拉普拉斯谱半径在理论化学上有重要的应用4 8 ，4 9 1 。在第2 章中，我们给出 了拉普拉斯谱半径的可达的上下界；考虑了在各种扰动下( 例如：加边运算，嫁 接运算，剖分运算等等) ，拉普拉斯谱半径的变化情况；研究了拉普拉斯谱半径 的极限点。作为我们所得结果的应用，在本章的最后，我们考察了具有佗个顶点 和k 个悬挂点的单圈图以及双圈图的拉普拉斯谱半径。 图的代数连通度是指图的拉普拉斯矩阵的第- - d , 特征值。最近，人们利用 图的代数连通度来研究一些困难的图论问题，得到了很好的结果，例如图的扩 展性质f 1 】，等周数f 7 6 ，7 7 1 ，最大割问题f 7 8 1 ，以及图的直径1 1 1 等等。在第3 章 中，我们研究了图的代数连通度：考察了对图进行嫁接运算后，图的代数连通 度的变化情况；进一步，利用该结果及我们在第l 章中所发展的图的拉普拉斯 特征多项式理论，我们完全解决了f a u a t 和k i r k l a n d 在1 9 9 8 年提出的关于具有 固定围长的连通图的代数连通度的一个猜想( 见2 4 ，2 5 1 ) 。 作为最简单的连通图，在研究一些困难的图论问题时，树通常起到特殊的 作用。在第4 章中，我们系统地研究了树的拉普拉斯特征值：包括具有固定直 径的树的拉普拉斯谱半径；树的第二大的拉普拉斯特征值以及树的第尼大的拉普 拉斯特征值等等。 在最后一章中，我们考虑了图的其它的拉普拉斯特征值，包括图的第三大 的拉普拉斯特征值以及图的拉普拉斯特征值的重数等等。 关键词：图，拉普拉斯矩阵，邻接矩阵，拉普拉斯特征值，特征多项式，特征 向量，树，拉普拉斯谱半径，代数连通度，极限点，直径，上( 下) 界，单圈 图，双圈图，分布，加边运算，嫁接运算，剖分运算。 v 同济大学博士学位论文 a b s t r a c t 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 ha g 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 xa n dt h el 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 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 e p 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 sa 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 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 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 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 3 ，1 4 1 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 xh a v eac l o s er e l a t i o nt on u m e r o u s g r a p hi n v a r i a n t s ( s e ef 7 9 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 ta sm o h a rf 7 9 1s a i d t 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 e 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 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 ( g ) o fag r a p hgi 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 5 8 1 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 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 w t 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 s o ，t 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 扩m 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 sf 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 f 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 7 9 1 s o i ti so f t e nc a l l e d t h el a p l a c i a nm a t r i xo 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 n m a t r i xo fag 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 ef 1 9 ，2 0 ，2 1 ，2 2 ，2 3 1 ) t h el 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 gg e o m e t r i cr e p r e s e n t a t i o n so fa g r a p h ( s e e 3 5p 2 8 4 ) t h i si sr e l a t e dt ow o r ko nt h ec o l i nd ev e r d i d r en u m b e ro f ag 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 td e v e l o p m e n ti ng r a p ht h e o r y f 5 3 | s o ，l a p l a c i a ne i g e n v a l u e sa r en o to n l yf 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 t a l s ot oc h e m i s t sa n d p h y s i ( i s t s i nt h i sp a p e r ，f i v et o p i c so nl a p l a c i a n e i g e n v a l u e so fg r a p h sh a v e b 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 el a p l a c i a nc h a r a c t e r i s t i cp o l y n o m i a l ；t h es e c o n di s v i a b s t r a c t t 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 s ；t h et h i r di st h es t u d yo nt h ea l g e b r a i c c o n n e c t i v i t y ；t h ef o u r t hi st h es t u d yo nt h el a p l a c i a ne i g e n v a l u e so ft r e e s ；t h e l a s ti st h es t u d yo nt h ed i s t r i b u t i o no fl a p l a c i a ne i g e n v a l u e s i ti sw e l lk n o w nt h a tt h ec h a r a c t e r i s t i cp o l y n o m i a lo fa d j a c e n c ym a t r i xo fa g r a p hp l a y sa ni m p o r t a n tr o l ei ns t u d y i n gt 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 h o w e v e r t h el a p l a c i a nc h a r a c t e r i s t i cp o l y n o m i a lo fag r a p hi sk n o w nv e r yl i t t l e 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 ol a p l a c i a nm a t r i xa n d k n o w nt h e o r e m so nm a t r i xt h e o r y m o r ei m p o r t a n t w b s = i ristematicallyn v e s t i g a t e t h el a p l a c i a nc h a r a c t e r i s t i cp o l y n o m i a l so fg r a p h s i nt h en e x tc h a p t e r s ，w ew i l l s e et h a tt h el a p l a c i a nc h a r a c t e r i s t i cp o l y n o m i a lp l a y sak e yr o l ei ns t u d y i n gt h e l 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 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 ， r e s p e c t i v e l y 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 et h et w ol 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 ，r e s p e c t i v e l y t h el a r g e s te i g e n v a l l u eo ft h el a p l a c i a nm a t r i xo fag r a p hgi sc a l l e dt h e l a p l a c i a ns p e c t r a lr a d i u so fg 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 i l t 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 4 8 ，4 9 ，r e c e n t l y i nc h a p t e r2 ，w eg i v e s h a r pu p p e ra n dl o w e rb o u n d sf o rt h el a p l a c i a ns p e c t r a lt a d i u s ；c o n s i d e rt h ee f f e c t o nt h el a p l a c i a ns p e c t r a lr a d i u su n d e rp e r t u r b a t i o n ；a n ds t u d yt h el i m i tp o i n t s o ft h el a p l a c i a ns p e c t r a lr a d i u s a sa p p l i c a t i o n so fo u rr e s u l t s ，a tt h ee n do f t h i sc h a p t e r ，w ei n v e s t i g a t et h el a p l a c i a ns p e c t r a lr a d i u so fu n i c y c l i ca n db i c y c l i c g r a p h so nnv e r t i c e sa n dkp e n d a n tv e r t i c e s 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 eo fag r a p hgi sc a l l e dt h ea l g e b r a i c c o n n e c t i v i t yo fg r e c e n t l y , 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 st os e v e r a l d 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 gp r o p e r t i e s o 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 【7 6 ，7 7 ，t h em a x i m u mc u tp r o b l e m 7 8 ， a n dt h ed i a m e t e rf1 1e t c c h a p t e r3i 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 f g r a p h s w es t u d yt h ee f f e c to 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 sb yg r a f t i n g a ne d g e ，a n dc o m p l e t e l yp r o v eac o n j e c t u r ep o s e db yf a l l a ta n dk i r k l a n d ( s e e ， 【2 4 ，2 5 ) o nt h ea l g e b r a i cc o n n e c t i v i t yo fc o n n e c t e dg r a p h sw i t hf i x e dg i r t hb y u s i n gt h el a p l a c i a nc h a r a c t e r i s t i cp o l y n o m i a lt h e o r yd e v e l o p e di nc h a p t e ro n e a st h es i m p l e s tc o n n e c t e dg r a p h s ，t r e e su s u a l l yp l a yas p e c i a lr o l ei ns t u d y i n g s o m ed i f f i c u l tp r o b l e m si ng r a p ht h e o r y i nc h a p t e r4 ，w es y s t e m a t i c a l l ys t u d y t h el a p l a c i a ne i g e n v a l u e so ft r e e si n c l u d i n gt h el a p l a c i a ns p e c t r a lr a d i u so ft r e e s w i t hf i x e dd i a m e t e r ；t 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 ft r e e sw i t hap e r f e c t m a t c h i n g ；a n dt h ek t hl a r g e s tl a p l a c i a ne i g e n v a l u eo ft r e e sa n ds oo n i nt h el a s tc h a p t e r w ec o n s i d e ro t h e rl a p l a c i a ne i g e n v a l u e so fg r a p h si n - c l u d i n gt h et h i r dl 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 em u l t i p l i c i t yo 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 k e y w o r d s ：l a p l a c i a nm a t r i x ，a d j a c e n c ym a t r i x ，g r a p h ，l a p l a c i a ne i g e n v a l u e s ， 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 ，t r e e ，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 v i i 同济大学博士学位论文 c o n n e c t i v i t y ，l i m i tp o i n t ，d i a m e t e r ，u p p e r ( 1 0 w e r ) b o u n d ，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 ，d i s t r i b u t i o n ，a d d i n ga ne d g e ，g r a f t i n g ，s u b d i v i s i o n v i i i 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；。学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：鲁p 乡睦目月 20 06 年3 月f 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月日年月日 学位论文独创性声明 本人声明，所呈交的学位论文系在导师指导下本人独立完成的研究成果。 文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法 律意义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申 请的论文或成果。 本人如违反上述声明，愿意承担以下责任和后果： 1 交回学校授予的学位证书； 2 学校可在相关媒体上对作者本人的行为进行通报； 3 本人按照学校规定的方式，对因不当取得学位给学校造成的名誉损害， 进行公开道歉； 4 本人负责囚论文成果不实产生的法律纠纷。 论文作者躲皇p 缱生 吼 第1 章绪论 第1 章绪论 1 1 研究背景与进展 图谱理论主要研究图的邻接矩阵和拉普拉斯矩阵的特征值和特征向量，是 图论研究的一个重要方向。对图的邻接矩阵的特征值的研究，目前已形成比 较成熟的理论，详见专著6 ，1 3 ，1 4 】。与图的邻接矩阵的特征值相比，由于拉 普拉斯矩阵的特征值与图的结构之间有着更自然的联系，更能反映图的图论性 质【7 9 】，因此对拉普拉斯矩阵的特征值的研究正越来越引起人们的关注，是当前 图论研究中的一个热点问题。 对拉普拉斯矩阵的研究已有相当长的历史，最早可追溯到1 8 4 7 年k i r c h h o f f 在研究电流理论时所发现的矩阵一树定理。对图的拉普拉斯特征值的研究不仅 具有重要的理论价值，而且还有广泛的应用背景 7 9 】。拉普拉斯特征值与拉普 拉斯微分算子，谱几何，网络理论，组合优化等数学分支均密切相关，同时在 物理，理论化学，计算机科学，电子工程学中均有重要的应用。 研究拉普拉斯特征值的方法主要有如下三种： ( 1 ) 代数方法：即用矩阵论并结合图的图论性质来研究拉普拉斯特征值， 如文献【4 0 】。 ( 2 ) 几何方法：即研究图的拉普拉斯矩阵l ( g ) = d ( g ) 一a ( g ) 所对应的 二次型并结合图的图论性质来研究拉普拉斯特征值或将图的规范拉普拉斯矩阵 d ( g ) 一i 1l ( g ) d ( g ) 一视为r i e m m a n n 流形上的拉普拉斯算子的离散形式，从 而将拉普拉斯算子理论引入到拉普拉斯特征值的研究中，如文献【1 1 ，7 9 】。 ( 3 ) 概率方法：即通过引入随机路的概念，利用概率论的方法研究拉普拉 斯特征值，如文献1 2 1 。 另外，也可以借助于计算机来对拉普拉斯特征值进行研究，如文献f 9 】。 在本文中，我们主要利用代数方法和几何方法来对图的拉普拉斯特征值进行研 究。 在图的拉普拉斯特征值中，最重要的有两个：图的最大拉普拉斯特征值( 即 拉普拉斯谱半径) 和图的第- 4 , 的拉普拉斯特征值( 即代数连通度) 。利用代数 方法和几何方法对拉普拉斯特征值进行研究，主要有以下几个方面的工作： ( 一) 对拉普拉斯谱半径的研究。主要是利用图的顶点度来给出拉普拉斯谱 半径的可达上界，该方面最早的工作是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 v ：u v e ) ， 等式成立当且仅当g 是二分正则图或g 是二分准正则图，其中u ( g ) 表示图g 的拉普拉斯谱半径。 1 9 9 7 年，李炯生和张晓东6 7 1 改进了a n d e r s o n m o r l e y 的上界，自此以后， 有关拉普拉斯谱半径的上界大量涌现，见文献 1 6 ，1 7 ，6 6 ，6 8 ，6 9 ，7 3 ，8 4 ，8 7 ，9 6 】。 同济大学博士学位论文 最近，一个有意义的工作是b r a n k o v ，h a n s e n 和s t e v a n o v i cf 9 1 对已有的上界进 行了研究和比较并利用计算机给出了一些关于拉普拉斯谱半径的上界的猜想。 另外，在文献【4 0 】中，g r o n e 等人考虑了对某些特殊图类进行收缩运算 后，拉普拉斯谱半径的变化情况。 ( 二) 对代数连通度及其所对应的特征向量的研究。该方面早期的经典工作 是f i e d l e r 在 2 9 】和【3 0 】中分别研究了图的代数连通度及其所对应的特征向量， 提出了用代数连通度所对应的特征向量来研究代数连通度的新思路，因此，代 数连通度所对应的特征向量通常被称为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 7 ，3 8 ，7 0 】；最近，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 ，2 4 ，2 5 ，2 6 ，2 7 ，5 9 ，6 0 ，6 1 ，6 2 】。 ( 三) 对拉普拉斯特征值与图的不变量之间的关系的研究。该方面的早期工 作是f i e d l e r 在文献 2 9 1 中给出了代数连通度与图的连通度，边连通度之间的 如下关系： 设g 是n 阶图，则 ( 1 ) g 连通的充要条件是其代数连通度a ( g ) 0 ； ( 2 ) 设图g 的连通度和边连通度分别为v ( a ) 和e ( g ) ，则有a ( g ) v ( a ) e ( g ) 。 进一步的研究发现，可以用拉普拉斯特征值来估计图的诸多不变量，如直 径【1 1 】，等周数 7 6 ，7 7 】，最大害m j 7 8 】，扩充子 1 】等等，有些图的不变量的计算 是n p - h a r d 问题，而拉普拉斯特征值则可用多项式理论中渐近求根方法加以计 算。 ( 四) 对图的其它拉普拉斯特征值的研究。在文献3 6 ，4 0 ，7 1 1 中，g r o n e 等 研究了拉普拉斯特征值落在某一区间上的重数；在文献f 6 5 1 中，李炯生等研 究了图的第二大拉普拉斯特征值，给出了第二大拉普拉斯特征值的一个可达 下界；p a t if 8 2 】研究了图的第三个最小的拉普拉斯特征值及其所对应的特征向 且 。 里。 在本文中，我们主要做了如下一些工作： ( 一) 给出了图的拉普拉斯谱半径的若干个新的上界，对某些实例，我们的 上界要优于已知的结果，同时也给出了一个二分图的拉普拉斯谱半径的可达下 界( 第2 章第1 节) ；研究了在图的各种运算下( 例如：加边运算，嫁接运算，剖 分运算，移边运算等) ，拉普拉斯谱半径的变化情况( 第2 章2 5 节) ，利用所得 结果，得到了具有礼个顶点和七个悬挂点的单圈图以及双圈图的拉普拉斯谱半 径的可达上界和全部极图( 第2 章第6 节) 。 ( 二) 通过研究图的拉普拉斯特征多项式，巧妙的将拉普拉斯矩阵分块，从 而得到有关拉普拉斯特征多项式计算的一些基本公式( 第1 章第4 节) ，进一步 得到了树的第二大拉普拉斯特征值的一些可达的上下界( 第4 章第3 节) 和树的 第k 大拉普拉斯特征值的呵达一卜界( 第4 章第4 节) 。 ( 三) 通过研究具有悬挂路的图的f i e d l e r 向量的性质，得到了在嫁接运算 下代数连通度的变化规律( 第3 章第1 节) ，把该结果与图的拉普拉斯特征多项 2 第1 章绪论 式相结合，成功的解决了1 9 9 8 年f a l l a t ，k i r k l a n d 2 4 ，2 5 1 提出的关于具有固定 围长的连通图的代数连通度的一个猜想( 第3 章第2 节) 。 ( 四) 利用拉普拉斯特征多项式，研究了具有固定直径的树的拉普拉斯谱 半径( 第4 章第l 节) 且给出了具有最大拉普拉斯谱半径的前十三个树( 第4 章 第2 节) ：研究了拉普拉斯谱半径的极限点( 第2 章第7 节) ；对拉普拉斯特征值 的重数也进行了一些研究( 第5 章1 2 节) ：给出了图的第三大拉普拉斯特征值 的一个可达下界( 第5 章第3 节) 。 1 2 基本概念 在本文中，所用到的未加定义的图论和矩阵论中的一些基本定义和术语可 见文献( 【7 ，8 和 5 5 】) 。设g = ( ke ) 是有n 个顶点的简单连通图( 不含环和多 重边) ，其中v = v 1 ，v 2 ，) 表示点集合、e 是边集合。图g 的邻接矩阵 定义为一个n 礼矩阵a ( g ) = ( a i ，) ，其中当v i 和相邻时a t f = 1 ；当v i 和 不相邻时a t f = 0 。假如g 是一个简单图，则a ( g ) 是一个实对称的( o ，1 ) 矩 阵且它的主对角线上的元素全为零。从而它的特征值全为实数。不失一般性， 可以假设它们按照如下从大到小的顺序排列为： a 1 ( g ) a 2 ( a ) a n ( g ) 且称入七( g ) 为图g 的第k 大的特征值。特别地，称入1 ( g ) 为图g 的谱半径。 假如m 是一个钆阶方阵且其特征值全为实数，我们不妨用入k ( m ) 表示它的第 k 大的特征值。特别令p ( m ) = m a x i , k ( m ) i ：i = 1 ，2 ，n 】- ，称为m 的谱半 径。 令d ( 仇) 表示顶点v i 的度，d i ( g ) 表示g 的第i 大的度，即有d 1 ( g ) d 2 ( g ) 厶( g ) ，i 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 的每一条边，取其一个端点为始点，另一端点 为终点，这一过程称为给图g 一个定向。当图g 取定一定向时，其定向关联 矩阵定义为q = q ( g ) = ( 依，) ，其中， f1 ，当v i 是边e i 的始点时； 哦f = c - 1 ，当仇是边e f 的终点时； 。 【0 ，其它 。 则l ( g ) = q ( g ) q ( g ) t ( 其中q ( g ) t 是矩阵q ( g ) 的转置矩阵) 且l ( a ) 与 g 的定向无关( 见 3 5 】p 1 6 8 ) 。容易证明l ( g ) 是一个半正定的、对称的实矩阵 且它的每一行的行和为零，因此，l ( g ) 又是奇异的。从而，我们可以假设它的 特征值按照从大n d , 的顺序排列为： 肛1 ( g ) u 2 ( g ) p n ( g ) = 0 且称胀( g ) 为图g 的第k 大的拉普拉斯特征值。特别地，称肛1 ( g ) 为图g 的拉普拉斯谱半径，记为肛( g ) 。矩阵l ( g ) 的谱称为g 的拉普拉斯谱，记作 s p e c ( g ) ，即s p e c ( g ) = p l ( g ) ，r e ( c ) ，如( g ) ) 。 设x 是图g 的相应于p ( g ) 的一个特征向量，自然地，x 中的分量可以 与图g 的顶点之间建立个一对应关系，称为给g 一个点赋值f 7 4 1 。我们常 3 同济大学博士学位论文 将对应于点忱的x 中的分量记为x ( v i ) 或z 们或戤。特别地，假如x 是相应 于“( g ) 的单位特征向量，则我们有 1 广rr ，几、弋厂 肛( g ) = x t l ( g ) x =n ( x ( 忱) 一x ( 吻) ) 2 = y m r 卟a x 。) 警 毗吩d 对x 的每个分量取绝对值，得到一个新的向量，记作i x i 。 在文献 2 9 】中，f i e d l e r i 正明：图g 是连通的当且仅当g 的第二个最小的拉 普拉斯特征值一1 ( g ) 0 。因此，一1 ( g ) 被f i e d l e r 称为图g 的代数连通 度，记为a ( g ) 。人们把对应于q ( g ) 的特征向量称为f i e d l e r 向量。假如x 是 一个单位f i e d l e r 向量，则有 q ( g ) = x t l ( g ) x =( x ( 仇) 一x ( ) ) 卜y 娥。) 警， v v j e e y t e n ；o 。 其中e n 是钆维的全1 列向量。 如果图g 中的两条边没有公共点，则称它们为独立的。g 中两两独立的边 的集合称为g 的一个匹配。图g 的所有匹配中，含有边数最多的匹配称为g 的一个最大匹配。g 的一个最大匹配所含边数称为g 的匹配数，记作f l ( a ) 。 如果g 的顶点数等于2 f l ( a ) ，则称g 的最大匹配为一个完美匹配或称g 含有 一个完美匹配。 图g = ( ve ) 的线图记作粤( g ) ，它是由g 通过如下方式而得到：以g 的 边集合e 作为e ( c ) 的点集合，e 中任意两个元素在e ( c ) 中是邻接的当且仅当 它们在g 中有公共点。 对于图的拉普拉斯矩阵，还可以从另外一个角度来研究它，即k ( g ) = q ( g ) t q ( g ) 。f o r s m a n 3 2 】和g u t m a n 【4 6 】研究了l ( g ) 和k ( g ) 之间的联 系。一方面，与l ( g ) 不同的是，k ( g ) 要依赖于g 的定向：另一方面，当