《图laplace谱》由会员分享，可在线阅读，更多相关《图laplace谱（56页珍藏版）》请在金锄头文库上搜索。
1、中国科学技术大学博士学位论文图的Laplace谱姓名：潘永亮申请学位级别：博士专业：应用数学指导教师：李炯生2001.5.1摘要本文主要研究代数坠中的一个重要课题：图的! ! ! 丝! 熟 ，熙它是鳌生童重垄上的揎萱塑逝簋壬在图上的塞墼I 至蓝L a p a l c e 矩阵在物理，化学，生物和计算机通信网络研究等学科中有着广 泛应用体文得到以下几个结果：I 利用实对称矩阵和其主子矩阵的特征值相交错的事实和对 图的顶点进行均匀分拆的技巧，用图的次大度给出了其次大L a p l a c e 特征值的一个下界2 刻划了达到图的度平方和的d eC a e n 上界的极图，并利用其给出了图的L a p
2、 l a c e 特征值的仅与图的顶点数和边数有关的上 界同时给出了另外几种形式的上界，并刻划了达到那些上界的极图利用二部宽的已有结果给出了图的最大L a p l a c e 特征 值的仅用图的点数和边数表示的下界3 引进了图的一个新参数u ( G ) ，并应用u ( G ) 给出了图的第三 小L a p l a c e 特征值的下界还利用上述1 中得到的图的次大L a p l a c e 特征值不小于图的次大度的结果，建立了u ( G ) 与图的最大度和次小度的联系4 给出了图的L a p l a c e 特征值的几个已知上界的新证明，完成了 对相应极图的刻划进而给出了一个新上界，并刻划了达
3、到上 界的极图最后给出了图的L a p l a c e 特征值其它两个类型的上 界，并刻划了相应的极图) - - ) 一一A B S T R A C TT h eL a p l a c em a t r i xi sa na c t i v ea n di m p o r t a n ts u b j e c ti nA l g e b r aG r a p hT h e o r y I ti sad i s c r e t ef o r mo ft h eL a p l a c eo p e r a t o ro nt h ec o m p a c tR i m a n n i a nm a
4、 n i f o l da c t i n go nt h eg r a p h s I th a sb e e nw i d e l yu s e di nm a n yf i e l d ss u c ha sP h y s i c s 、C h e m i s t r y 、B i o l o g y 、C o m p u t e rn e ts c i e n c ea n dI n f o r m a t i o nt h e o r y ，e t c S o m er e s u l t so nt h eL a p l a c em a t r i xw i l lb eg i
5、v e ni nt h i st h e s i s ：1 A p p l y i n gt h ee i g e n v a l u ei n t e r l a c i n gt h e o r e ma n dt h es k i l lo fe q u i t a b l ep a r t i t i o no ft h ev e r t e xs e to fag r a p h ，w eo b t a i nal o w 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 ee i g e n v a l u e 2 (
6、G ) i nt e r m so ft h es e c o n dl a r g e s td e g r e ed 2 ( G ) o fag r a p h M o r e o v e r ，t w on e c e s s a r yc o n d i t i o n so fA 2 ( G ) =d 2 ( G ) a r ep r o v e da n dm a n yg r a p h sw h i c hs a t i s f yA 2 ( G ) = d 2 ( G ) a r ep r e s e n t e d 2 E x t r e m a lg r a p h sw
7、 h o s es u mo ft h es q u a r e so ft h ed e g r e e sr e a c ht h ed eC a e n Su p p e rb o u n da r ed e t e r m i n e d U s i n gd eC a e n Si n e q u a l i t y ，w eo b t a i na nu p p e rb o u n do ft h eL a p l w c ee i g e n v a l u e so n l yi nt e r m so ft h en u m b e r so fv e r t i c e
8、sa n de d g e so fag r a p h M o r e o v e r ，w ep r e s e n ts o m eo t h e rt y p e so fu p p e rb o u n d so ft h eL a p l a c ee i g e n v a l u e so fag r a p h A p p l y i n gt h er e s u l t so nb i p a r t i t i o nw i d t h ，w eo b t a i nal o w e rb o u n do ft h el a r g e s tL a p l a c
9、ee i g e n v a l u ei nt e r m so ft h en u m b e r so fv e r t i c e sa n de d g e so f8g r a p h 3 An e wp a r a m e t e ro fag r a p hi sd e f i n e da n dar e l a t i o nb e t w e e nt h en e wp a r a m e t e ra n dt h et h i r ds m a l l e s tL a p l a c ee i g e n v a l u eo fag r a p hi se s
10、t a b l i s h e d I na d d i t i o n ，w er e l a t et h en e wp a r a m e t e rt ot h el a r g e s td e g r e ea n dt h es e c o n ds m a l l e s td e g r e eo ft h eg r a p h 4 A p p l y i n gt h em e t h o di nn o n n e g a t i v em a t r i xt h e o r ya n dt h er e l a t i o nb e t w e e nt h eL
11、a p l a c em a t r i xo fag r a p hGa n dt h ea d j a c e n c ym a t r i xo ft h el i n eg r a p ho fG ，w eg i v eo u tn e wp r o o f so ft h ek n o w nu p p e rb o u n d sw h i c hw e r eg i v e nb yM e r r i s ，L ia n dZ h a n g M o r e o v e rw ec h a r a c t e r i z ee x t r e m a lg r a p h si
12、nt h et h e o r e m so fM e r r i s ，L ia n dZ h a n g W ea l s op r e s e n tan e wu p p e rb o u n do ft h eL a p l a c ee i g e n v a l u e so f8g r a p h a n dc h a r a c t e r i z ee x t r e m a lg r a p h s 第一章引言1 1 基本概念设G = ( KE ) 是n 阶简单图，其顶点集和边集分别记为V = v ( a ) = 1 3 2 ，”。) 和E = E ( a ) = C 2
13、 ，e m ) 如果顶点嘶是边q 的一个端 点，则称q 与e ，关联，与仉关联的边的数目称为y i 的度，记作d ( v i ) = d ；本文涉及到的图论和矩阵的术语都是标准的，可以见B o n d y 1 0 和B i g g s 1 1 称 n 阶方阵A ( a ) = ( a 。) 为图G 的邻接矩阵，其中A ( G ) 的行与列表示图G 的 顶点，且ll ，当u 和”相邻时， 10 ，否则易见丸= n 。是顶点“的度图G 的度对角矩阵记为D ( a ) = d i a g d 。： u y ( G ) u 矿( G ) ) 则矩阵L ( G ) = D ( G ) 一A ( G )
14、称为图G 的L a p l a c e 矩阵对图G 的每一边e k = 似，屿) ，选择其中一个顶点为其正端点，另一个为负端点这 一过程称为给图G 一个定向对图G 的一个定向，其定向关联矩阵( o r i e n t e di n c i d e n c em a t r i x ) c ( a ) = ( c 。) 如下ll ，如果u 是e 的正端点，1 ，如果”是e 的负端点，0 ，如果”和e 不相关联易见L ( G ) = D ( G ) 一A ( a ) = e ( G ) G ( G ) 7 ，其中e ( G ) 7 表示C ( a ) 的转置 图G 的L a p l a c e 矩
15、阵L ( G ) 与其定向无关，且是半正定对称奇异M 一矩阵，其每个特征值是非负的，记作A l ( G ) A 2 ( G ) 2h l ( G ) A 。( G ) = 0 由图G 的L a p a c e 矩阵三( q ，可以确定列向量空闫，2 ( y ( q ) 中的一个二次型如下：z L ( G ) z = ( z ，L ( G ) z ) = ( c 7 z ，C T x ) = ( z 。一z 。) 2其中“”表示顶点u 和”相邻中罾科学技术大学博士学位论文21 1 2L a p l a c e 特征值与图的组合性质1 图的复杂度图的L a p l a c e 矩阵研究已有很长的历
16、史，K i r c h h o f f 6 2 在研究电网络时 f 1 8 4 7 年) 证明了图G 的生成树数目等于它的L a p l a c e 矩阵的任何一个n 一1 阶予式的值从而将图的生成树的计数问题转化成了纯代数的计算问题 定理1 2 1 ( 矩阵树定理) n 阶图G 的复杂度K ( G ) ( 即其生成树的数 目) 等于其L a p l a c e 矩阵L ( C ) 的任何一个n 一1 阶子式特别有一( G ) =A l ( G ) t A 。一l ( G ) 由于有了现代高速计算机的普遍使用，K i r c h h o f f 矩阵树定理为计算图的生成树数目提供了有效的手段矩阵树定理有种种推广，见 6 J 、 1 7 】、 1 8 、 5 6 、 6 1 、 6 3 、 8 8 】等B i g g s 11 用图的
