（计算数学专业论文）图的最大和次小拉普拉斯特征值.pdf

摘要 摘要 设g 是n 阶简单连通图，d 和彳分别为图g 的度对角矩阵和邻接矩阵， l ( 6 ) = d a 称为图g 的拉普拉斯( 1 a p l a e i a n ) 矩阵。研究图的拉普拉斯矩阵的特 征值有着重要的图论意义和实际意义，因为它与图的许多不变量有着密切的联系。 在许多应用中，往往需要知道图的拉普拉斯矩阵的最大特征值“( g ) 的上界和次小 特征值以一。( g ) 的上下界。本文针对“( g ) 的上界和以一，( g ) 的上下界的估计问题做 了以下几个方面的工作： 1 综述了近年来有关“( g ) 的上界估计的主要结果，并作了全面的比较分析。 2 利用非负矩阵行和与它的谱半径之间的关系以及p e r r o n f r o b e n i u s 定理等 方法并结合图论性质获得了图的拉普拉斯谱半径的一些上界，并附带得到了关于 有向图的谱半径估计的一些上下界。同时，对其中的一些估计式，用例子说明了 其准确性和易于( 编程) 实现性。 3 利用矩阵理论和树的一些性质，研究了b e t h e 树的拉普拉斯谱半径的估计 问题，得到了其具体特征多项式和它的谱集。 4 图的拉普拉斯次小特征值与图的代数连通度有关系，利用矩阵分拆技巧通 过将三( g ) 分拆为两个矩阵和的形式再利用著名的w e y l 定理，给出了一类具有割 点、割边图的拉普拉斯次小特征值的上下界估计式。这些估计式具有递推特征， 即估计式将高阶图类的拉普拉斯次小特征值用低阶图的拉普拉斯次小特征值来表 示。 关键词：拉普拉斯矩阵，最大特征值，b e t h e 树，线图，割点 a b s t r a c t l e tgb eas i m p l ea n dc o n n e c t e dg r a p hw i t h 以v e r t i c e s t h e d i a g o n a lm a t r i xo f v 酣e xd e 酉e e s a n dt h e a d j a c e n t m a m xo fg r a p hg a r er e s p e c t i v e l yd e l l o t e d b y d a 三( g ) ：d a i sc a l l e da st h el a p l a c i a nm a t r i xo fg r a p h g t or e s e a r c h e i g e n 、，a l u e so ft h el a p l a c i a nm a t r i xo fg r a p h i si m p o r t a n ti ng r a p ht h e o r ya n dr e a l l 够， b e c a u s ea1 0 to fi n v a r i a n t sa let i g h t l yc o n n e c t e dw i t ht h e m b o u n d s o ft h el a r g e s t e i g e n v a l u e 孤dt h es e c o n ds m a l l e s te i g e n v a l u ea r ea l w a y s u t i l i z e di nm a n ya p p l l c a t l 吡 1 1 1 eb e l o wp r o b l e m sw e r es o l v e di nr e g a r dt ob o u n d so f l ( g ) a n d 以一l ( g ) ： 1 t h em a i nr e c e n tr e s u l t sa b o u tu p p e rb o u n d so f a l ( g ) w a sr e p o r t e da n d c o m p a r e dw i t he a c ho t h e r 2 t h eu p p e rb o u n d so fs p e c t r a lr a d i u so ft h el a p l a c i a nm a t r i c e so ng r a p h sw l m a c c e s s o r yt h e o r ya b o u tb o u n d so fs p e c t r a lr a d i u so fa d j a c e n tm a t r i xo nd i g r a p h sw 盯e o b t a i n e db yu t i l i z i n gt h er e l a t i o n sb e t w e e nt h er o w s u m so fn o n n e g a t i v em a t r i c e s 觚d1 t s s p e c t r a lr a d i u sa i l dp e n o n f r o b e n i u st h e o r ya n ds oo n m e a n w h i l ef o r m u l a sa b o u t t h e u p p e rb o u n d so fs p e c t r a lr a d i u sw e r ei l l u s t r a t e da c c o r d i n g t os e v e r a le x a m p l e st oj u d g e w h i c hw a s 也eb e s ta c c u r a c ya n dm o s te a s i l yr e a l i z e db yp r o g r a m m ea m o n g t h e m 3 t h eu p p e rb o u n d so fs p e c t r a lr a d i u so fl a p l a c i a nm a t r i c e s o nb e t h et r e e s , a s p e c i a lg r a p h ，w e r ea l s or e s e a r c h e db y u sb e s i d e st h e mo nc o m m o ns i m p l e 孕a p n s l n e e s t i m a t i o nf o 咖u l a so ft h eu p p e rb o u n d sw e r eo b t a i n e db ym e a n so f c h a r a c t e r sb e t w e e l l m a t r i xt h e o r i e sa n dt r e e s 4 t h es e c o n ds m a l l e s te i g e n v a l u eo fl a p l a c i a nm a t r i c e so ng r a p hh a sr e l a t i o n s w i t ht h ea l g e b r ac o n n e c t i v i t yo fg r a p h w ea l s oo b t a i n e dt h ee s t i m a t i o nf o r m u l a so f b o u n d si nr e g a r dt os o m eg r a p h sw i t hc u tp o i n t so rc u te d g e sb y d e t a c h i n gl ( g ) m a t r i x i n t ot w om a t r i c e so fl o ws t e p sa n du t i l i z i n gt h e f a m o u sw e y s lt h e o r y t h es e c o n d s m a l l e s te i g e n v a l u eo fl a p l a c i a nm a t r i xo fg r a p hw i t hl a r g e 以 w a sd e n o t e db yt h e mo f g r a p h w i t h s m a l ln k e y w o r d s ：l a p l a c i a nm a t r i x ，t h el a r g e s te i g e n v a l u e ，b e t h et r e e ，l i n eg r a p h ，c u tp o i n i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：夏盏茎日期：z 暗年；月2 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：互当童导师签名：ik 塾岂 日期：川年3 月堵曰 第一章绪论 1 1 预备知识 第一章绪论 设g 是一个顶点集为矿，其边数为m ，边集为e 的万阶简单图( 本文若无特 别指明，所指的图均为简单图) 。对于甜v ，z 。或4 表示顶点的度，t 。= y 吐，表示 顶点“的2 一度，其中“ 表示顶点”，1 ，邻接。图g 的最大度，最小度分别记为，万。 记d = d i a g ( d ，d 2 ，以) ，称为图g 的度对角矩阵。令彳为图g 的邻接矩阵。易知， 彳是非负矩阵，在矩阵论中，非负矩阵彳的最大特征值被称为彳的谱半径。而图g 的邻接矩阵么的特征值和谱半径分别被定义图g 的特征值和谱半径。用s ，( 么) 表 示矩阵彳对应顶点1 ，的行和。 令( g ) = d a ，三( g ) 被称之为图g 的拉普拉斯矩阵。根据l ( g ) 和m 矩阵的 定义，容易判断三( g ) 为实对称、半正定、奇异m 矩阵，它的行和均为0 。以下我们 不妨把l ( g ) 的特征值记为“( g ) 1 t 2 ( g ) 鸬( g ) 以( g ) ，记l ( g ) 的谱半径 ( 即l ( g ) 的最大特征值) 为m ( g ) 。其中从一。( g ) 为图g 的次小拉普拉斯特征值，它 与图的代数连通度有关。由矩阵性质可以知道l ( g ) 的最小特征值为零。 令q ( g ) = d + 彳，我们把q ( g ) 谱半径记为4 q ) 。 与以上类似，有向图g 的邻接矩阵记为么，它的谱半径记为p ( 彳f ) ，p ( a ) 也为 图g 的谱半径。根据有向图的邻接矩阵性质我们可以得到有向图的邻接矩阵是非 负矩阵。用s ( 么慵) 表示矩阵礓对应顶点1 ，的行和。v a 所谓偶图是指若图g 的顶点集能有一个划分v = ( u ，s ) ，使得g 的每条边的两 个端点分别在u 和s 中，这等价于u 或s 中任何两个点都不相邻。熟知一个图为 偶图的充要条件是它不含有奇圈。而正则图是指图中每个顶点的度都是相同的。 特别地，一个图如果是偶图且k 正则，则称为k 正则偶图。图g 的线图是指将图g 中 边看作点，若两条边在图g 中相邻，则在线图中作为点也相邻。显然若图g 是连 通的，则其线图也是连通的。线图的邻接矩阵也是实对称的非负矩阵，且当图g 是 连通图的时候，是不可约的。令厶为g 的线图，其彳，b 分别为g 和厶的邻接矩阵， 且记p ( 厶) 为线图的邻接矩阵曰的谱半径。 另外，实矩阵的谱是指矩阵的特征值连同特征值的重数组成的集合。本文中 其它未定义的术语和符号参见 1 ，2 ，3 。 电子科技大学硕士学位论文 1 2 研究背景 拉普拉斯矩阵一词最早出现在1 8 4 7 年，k i r c h h o f f 研究电流理论时所发现的矩 阵树定理。 定理1 2 1 【q ( 矩阵树定理)咒阶图g 的复杂度彭( g ) ( 即其生成树的数目) 等于 拉普拉斯矩阵( g ) 的任何一个n 一1 阶子式，则有 1 誓( g ) = 二“( g ) 以一l ( g ) 玎 矩阵树定理在不同研究领域有种种推广形式，见 5 ，6 ，7 , 8 ，9 ，1 0 等。对图的拉普拉 斯矩阵进行研究之所以很重要，最直接的原因是可以用拉普拉斯特征值来估计图 的许多不变量，如图的连通度，直径，宽带，二部宽，等周数，最大割，超缩子 和扩充子，平均距离，边前项指数等等。其中一些重要的不变量，如图的二部宽， 最大割，等周数等，除了反映图的一些结构性质外，而且还有广泛的应用，然而 他们计算的复杂度属于n p h a r d 的，而计算图g 的拉普拉斯特征值仅涉及线性方 程组求解。研究拉普拉斯特征值与图不变量间的联系的早期经典工作在1 9 7 3 年 f i e d l e r 的文章 11 中被提出。在此文章中他给出了次小拉普拉斯特征值与图的连通 度，边连通度之间的关系。 定理1 2 2 【l l 】设g = ( v e ) 是，l 阶图，则图g 连通当且仅当以一。( g ) 0 。设g 的 点连通度和边连通度分别为1 ，( g ) 和e ( g ) ，则有以一。( g ) v ( g ) s e ( g ) 。 因此f i e d l e r 也把次小特征值熊一。( g ) 称之为图g 的代数连通度。本文侧重于研 究图的拉普拉斯矩阵的最大特征值和次小特征值。 1 3 研究图的拉普拉斯特征值的基本方法 研究图的拉普拉斯谱半径的方法与研究矩阵特征值的方法相似。但是由于拉 普拉斯矩阵的特殊性和它与图的密切关系，它和一般研究矩阵谱半径的方法又有 所区别。从作用对象来说可以直接以拉普拉斯矩阵为研究对象也可以对图的邻接 矩阵进行研究，再进行转化。从所用工具上来看，有以下几种方法： 1 利用特征值和特征向量之间的关系。 设图g 的拉普拉斯矩阵( 乞( g ) = d a ) 的最大特征值和相应的特征向量分别为 。( g ) 和x ，并有“( g ) x = l ( g ) x 。利用不等式的性质进行放缩再结合图的特点进 2 第一章绪论 行变形，这是处理特征值和特征向量关系的常用方法。 2 圆盘定理和b r a u s e r 定理的应用 圆盘定理和b r a u s e r 定理是矩阵特征值研究中的经典理论，它分别用一系列的 行( 列) 格尔圆盘形域把矩阵的特征值覆盖在其中。其中这些圆盘，卵形域的边 界都是由矩阵的行( 列) 的元素( 对角元除外) 的绝对值之和确定。而对图的矩 阵来说，这些元素可由图中点的相邻关系确定，因此合理运用这些理论会收到较 好效果。 3 利用非负矩阵理论 非负矩阵中有很多关于矩阵特征值估计的结论和方法。如f r o b e n i u s 定理等。 而图论中的矩阵如拟阵k ( g ) ，线图的邻接矩阵么本身是非负的，所以将非负矩阵 的一些理论方法应用到这里是非常有效的。 4 矩阵相似变换的应用 由于相似矩阵具有相同的特征值，所以通过相似变换将( g ) ，a 变成其它矩 阵，再通过对变换后的矩阵进行特征值估计往往会得到很好的效果。常见的相似 变换有：d a d ，d a g ，d2 a d 2 ，d h 2 a d 三。其中d 为图g 的度对角矩阵， 而d 为其线图的度对角矩阵。当然还可以构造出一些新的相似变换。 电子科技大学硕士学位论文 第二章图的拉普拉斯谱半径 2 1 简单图的拉普拉斯谱半径上界估计的情况 自二十世纪八十年代以来，关于图的拉普拉斯特征值研究的论文很多，如 m e r r i s 1 2 1 ，m o h a r 1 3 - 1 5 1 等及时报道了该领域的新进展，新问题，而f r kc h u n g 在 1 9 9 4 年世界数学家大会( 瑞士苏黎士) 上的4 5 分钟【1 6 1 报告及其专著【1 7 】的问世更将拉 普拉斯矩阵的研究推到了一个新的高度。这些成果主要集中在图的最大、次大特 征值等方面。 本节主要简要介绍利用图的项点度，边数，平均二次度或公共邻点数来估计 图的拉普拉斯谱半径的一些重要结果。研究图的拉普拉斯矩阵特征值最早的工作 是从1 9 8 5 年a n d e r s o n 和m o r l e y 1 8 】给出的上界开始的。 定理2 1 1 ( a n d e r s o n 和m o r l e y 1 8 】) 设g = ( k d 是，z 阶图，则有 i ( g ) m a x d 。+ 以i u v e ) ( 2 - 1 ) 其中等式成立当且仅当g 是半正则二部图时成立。 在1 9 9 7 年李炯生和张晓东利用顶点度和平均二次度改进了这个结果，他们首 先给出了图的的拉普拉斯谱半径的估计式。 定理2 1 2 ( l ij i o n g s h e n g 和z h a n gx i a o d o n g ) t 1 9 】设d i d 2 以是，z 阶图 g 的度序列，则有 h ( g ) 2 + ( 盔+ d 2 2 ) ( d i + 以一2 ) ( 2 - 2 ) 其中等式成立当且仅当图g 是正则偶图，或星图，或长度为3 或4 的路时等式成 立。 令，= m a x d + d 。：u v e ( g ) ) ，设x , y v ( g ) 满足x y e ( g ) 且以+ d y = ，。再 令j = m a x d , + d v ：u v e ( g ) 一 砂) 。从而可以得到r 是图g 的边的两个端点度数 之和最大值，而s 是去掉边x y e ( g ) 后剩余边的两个端点度数之和的最大值。利 用r ，s 李和张又在上述基础上将结果改进。 定理2 1 3 【1 9 1 对n 阶图g ，则有 h ( g ) 2 + ( ，一2 ) ( ，+ 2 ) ( 2 - 3 ) 4 第二章图的拉普拉斯谱半径 其中等式成立当且仅当图g 是正则偶图或半正则偶图，或具有4 个点的路。 1 9 9 8 年，m e r r i s 引入了二次度的概念。设图g = ( v ，e ) 是，z 阶图，1 ，v 的度 和图g 中所有与，相邻点的度的平均值m 。的乘积z ，他，称为1 ，的二次度，显然 d m v 是图g 中所有与v 相邻的所有顶点的度的和。m e r r i s 利用二次度和特征值的 圆盘定理重新得到了最大拉普拉斯特征值的上界如下。 定理2 1 4 【2 0 】对以阶图g = ( y ，e ) ，则有 “( g ) m a x d + m uu y ( g ) ) ( 2 4 ) 其中等式成立当且仅当图g 是正则偶图或半正则偶图。 在此基础上，李和张在m e n i s 的这一基础上进一步得到了如下更好的上界。 定理2 1 5 【2 i 】对以阶图g = ( y ，e ) ，则有 鸬( g ) m a x 垒竿粤丛1w e ( g ) ) ( 2 - 5 ) d ”+ d ” 其中等式成立当且仅当图g 是正则偶图或半正则偶图 上界( 2 - 5 ) 实际上是吃+ 和以+ 聊，的加权平均值，加权系数分别为吃和以， 因此( 2 5 ) 估计值比( 2 - 4 ) 较好。现在给出如下两图以示说明。 g ig 2 图2 - 1 “( g ) 的估计值大于图的阶数的图例 事实上，对以上各估计式，其上界值在有些情况下大于图的阶数n ，如图2 1 ， 以上部分估计值如下表2 1 。 表2 - 1 a 1 ( g ) 的估计值大于图的阶数的图例 图阶数 ( 2 - 1 ) ( 2 3 ) ( 2 4 ) ( 2 - 5 ) g l 4 6 0 0 05 4 6 45 3 3 35 3 3 3 g 2 68 0 0 08 0 0 07 6 0 07 2 5 0 但事实上应该是一( g ) ，l ，于是智利学者r o j o 等人利用变换 m ( g ) = 三( g ) + ，其中，为全1 矩阵，将l ( a ) 转化为非负矩阵。然后利用非负矩 电子科技大学硕士学位论文 阵的特征值的次大模的已知上界用于m ( g ) ，得到t ( g ) n 的如下一个上界。 定理2 1 6 吲设图g 为n 阶简单连通图，则有 l ( g ) m a x d 。+ 巩 n m l l “，v 矿( g ) ，且“1 ，) ( 2 - 6 ) 其中l mn m l 是“和，的公共邻点数。g o j o 等人证明了该上界不超过刀。 2 0 0 3 年k c d a s 获得了该上界的改进公式。 定理2 1 7 【2 3 】设图g 为n 阶简单连通图，则有 , u l ( g ) m a x d 。+ d v l mn 玑i | u f e ( g ) ) ( 2 - 7 ) 当且仅当图g 是正则偶图或半正则偶图或包含一个完全偶图作为其生成子图的图 类等式成立。显然( 2 7 ) 比( 2 1 ) 和( 2 6 ) 都好，而且满足不超过图的阶数咒。但是( 2 - 6 ) 和( 2 7 ) 只能给出整数上界，它能给出的最大拉普拉斯特征值的上界范围比较粗略， 往往不能满足要求。 随后，李和潘利用矩阵特征值和其相对应的特征向量之间的关系，柯西不等 式以及平均二次度的概念给出了“( g ) 新的上界，并且在一定的条件下优于前面的 各上界。 定理2 1 8 t 2 4 】对n 阶连通图g = ( v ，e ) ，则有 p l ( g ) m a x x 2 d 。( 以+ m ，) i “y ( g ) ) ( 2 8 ) 其中等式成立当且仅当图g 是正则偶图。 在文 2 5 ，2 6 ，2 7 中作者分别给出了一个相对更优的上界如下。 定理2 1 9 对n 阶连通图g = ( 矿，e ) ，则有 小g ) m a x 尘尘业搴坦叫g ) ) ( 2 - 9 ) 当且仅当图g 是正则偶图或半正则偶图时等式成立。 2 0 0 4 年张在文 2 8 1 中利用特征值与特向量之间的关系以及将非负矩阵理论应 用到线图的邻接矩阵上，从而分别获得了以下两个结果。而且张指出( 2 1 0 ) 优于 ( 2 8 ) 。 定理2 1 1 0 【2 研设图g 是n 阶简单连通图，则有 “( g ) m a x d + d 。m 。l “矿( g ) ( 2 - 1 0 ) 当且仅当图g 为正则偶图时等式成立。 6 第二章图的拉普拉斯谱半径 定理2 1 1 1 r 2 81 设图g 是，z 阶简单连通图，则有 “l ( g ) m a x 2 + 4 2 0o = 1 ，2 ，甩，k = 1 ，2 ，胛) ，则有 唧n 怒篙纠删峄怒筹 证明根据p e r r o n - f r o b e n i u s 定理【3 6 】，非负矩阵彳的最大特征值就是a 的谱半 径p ( a ) ，1 f 1 p ( a ) 有i - - 个正特征向量x ，其对应的特征值为p ( p ( 彳) ) ，根据定理2 2 4 可得证。口 利用定理2 2 5 的结论可以得到下面结果。 推论2 2 6 设g 为n 阶简单连通图，a 为其邻接矩阵，q = d + 彳，则 有 中筹纠郇峄嚣 且有 耶) 峄器 ( 2 - 1 9 ) 证明s v ( q ) 表示矩阵对应顶点v 的行和，再利用定理2 2 5 和引理2 2 1 可 直接得证。 口 推论2 2 7 设g 为咒阶简单连通图，a 为其邻接矩阵，则有 叩糟s v 纠那峄籍 i 即。) 一7 s ，似。) 证明s ( a ) 表示矩阵彳对应顶点y 的行和，再利用定理2 2 5 可直接得证。口 利用定理2 2 5 ，我们给出了简单图的拉普拉斯谱半径上界估计的情况中的定 理2 1 5 刚另外的一种证明方法。并给出了若图g 是偶图，有如下不等式成立。 m i n 型苎轷l “v e ( g ) ) s ( g ) m a x 皇主警l “v e ( g ) ) 证明设图g 的线图岛的邻接矩阵为b ，对任意g = 圳e ( g ) ，有e v ( z o ) 电子科技大学硕士学位论文 吒( 。) = d u + 吨一2 。 图g 中与e 关联的边如图2 - 3 所示 u l u 2 图2 - 3 假设材l = _ ，u t = v t ，为顶点甜与，( z 0 ) 的z 个公共邻点，s = 以- 1 ， f = 玑- 1 ，在g 中t u = 吃。+ 或，t ，= 或，+ 吮，已( 曰) = 吐( 。) = 吃+ 或一2 j = 1 j = l 因为 所以 st & ( 君2 ) = 屯( ，) = ( 吃+ 叱一2 ) + ( 或+ d _ 一2 ) f e i = 1j = l = 以( 吃一1 ) + d x - d v - 2 ( a 一1 ) + 嘭一吮一2 ( 盛- 1 ) z ，v 由定理2 2 5 可知 再由引理2 2 2 【3 5 1 可得到如下不等式 当g 为偶图时 = 刃+ 彩一4 ( 吮+ 或- 2 ) + t 。+ t ，- 4 & ( ( b + 2 i ) 2 ) = + 彩+ t 。+ t ， 墨! ! 垒三! ! ：! 一重重! 。! ： s e + 2 i )吃+ 反 m i n 兰糌p c k ，+ 2 m a x 兰糟 t ( g ) p ( l o ) + 2 ( g ) m a x 垡肇掣i 圳e ( g ) ) d u + d ， 1 2 第二章图的拉普拉斯谱半径 ( g ) = p ( k ) + 2 所以 m i n 垒掣i 洲e ( g ) ) ( g ) m 觚 生掣1w e ( g ) ) 口 d 。+ d ，d 。+ d ， 2 3 图的拉普拉斯谱半径的上界估计式的比较 上节利用对非负矩阵最大特征值的估计，得到了关于简单图的邻接矩阵谱半 径的上下界( 推论2 2 7 ) 叩筹s v 酬郇峄篱 t ( 么2 ) 一7 j 。( 彳) 以及简单图的拉普拉斯矩阵谱半径的上界： 郎) 峄器 ( 2 - 1 9 ) 为了与( 2 5 ) ，( 2 - l o ) ，( 2 1 1 ) ，( 2 1 3 ) ，( 2 1 6 ) ，( 2 1 7 ) ，( 2 - 1 8 ) 这几个公式容易 比较，我们仍然用图2 - 2 来分析说明 表2 - 4 现有各上晃数据对比三 图“( g ) ( 2 5 )( 2 一l o )( 2 - 1 1 ) ( 2 - 1 3 )( 2 1 6 )( 2 - 1 7 )( 2 1 8 ) g 3 5 1 9 55 8 5 76 8 2 86 1 2 36 0 0 06 4 2 46 6 9 07 0 7 1 倪 4 3 4 34 8 0 05 4 4 94 8 2 84 7 2 05 7 0 2 5 4 6 45 6 2 0 ( 2 - 1 9 )( 2 1 9 )( 2 - 1 9 )( 2 - 1 9 )( 2 1 9 )( 2 1 9 ) 图“( g ) k = 1k = 2k = 3k = 4k = 5k = 6 g 3 5 1 9 56 0 0 05 8 0 0 05 7 5 8 65 6 8 8 65 6 4 8 45 6 2 6 7 g 4 4 3 4 35 0 0 04 8 0 0 04 7 5 0 04 7 3 6 84 7 3 3 04 7 3 2 4 表2 - 4 ，2 - 5 可以看出公式( 2 - 1 9 ) 的结果更好一些，而且公式( 2 1 9 ) 的算法更好 寻找，更易于在电脑上操作。另外，从上面的推论2 2 7 的结论，我们很自然想到 能否把它推到简单连通有向图的谱半径估计问题上面来。从而我们附带的引出了 有向图的谱半径估计问题。 电子科技大学硕士学位论文 2 4 有向图的谱半径 本文仅考虑没有环和重弧的简单有向图。设图g 是有向图g 的基础图，为令 矿= m ，哆，k ) 为有向图g 的顶点集，则矿也是图g 的顶点集。记b = ( 勿，) 为有向 图g 的邻接矩阵，其中玩是有向图g 中尾为，头为y ，的弧数。对简单有向图中 的邻接矩阵来b = ( 匆，) 说，= o 或1 。 在2 0 0 2 年，李炯生和张晓东给出了有向图的谱半径估计。 定理2 4 1 【3 7 】设g 是n 阶连通有向图，则有 疵，z 咒) p c g ，m ；驮 ，1 i ，l j 其中任一等式成立当且仅当g 是平均2 次外正则或平均2 次半正则的。记d ，代表 - 页ai 的出度，t ，= 吐表示顶点的2 一度。另记= t ，a ；，1 f ，l t i ，乞，厶 相等时，称g 是平蚓2 次外正则的，当乞，乙恰有两个不同的值时，称g 是平 均2 次外半正则的。 定理2 4 2 3 8 1 ( 方坤夫，束金龙，2 0 0 4 ) 设n 阶有向图g 的出度序列为 甜= = l ( 1 f n 一1 ) 令+ = d i ，a “= ，则有 剐) 生生坐之生业 等式成立当且仅当g 与一个简单有向图h 。同构。 以上有向图邻接矩阵的谱半径估计都是利用顶点度，顶点平均二次度或公共 邻点数的上界来估计谱半径，当图变得复杂时或阶数变得较高时以上的公式不实 用。我们利用非负矩阵的性质得出有向图的谱半径的估计式。 定理2 4 3 设g 为n 阶简单连通有向图，彳是g 的邻接矩阵， 则有 乎器纠a - ) 峄器 证明s v ( 彳慷) 表示矩阵彳礓对应顶点1 ，的行和，利用定理2 2 5 可以得证。口 现在我们给出图2 4 ，用表2 4 来说明我们给出的公式的易操作性。 1 4 第二章图的拉普拉斯谱半径 图2 4 表2 _ 4 图2 _ 4 邻接矩阵谱半径的估计 k = l1 p ( a ) 2 k = 21 p ( 彳) 2 k = 51 p ( a 。) 1 8 0 0 0 k = 61 2 1 4 3 p ( a ) 1 8 0 0 0 k = 71 2 1 4 3 p ( a ) 1 8 0 0 0 k = 81 2 1 4 3 p ( a ) 1 6 0 8 7 1 5 电子科技大学硕士学位论文 第三章树的拉普拉斯谱半径 3 1b e t h e 树与广义b e t h e 树的基本概念 无向树是一个无圈的连通图。当树有k 层并在每一层的各个顶点有相同的度 时，称这种树为无权值的k 层树，记作组。对于这类型树2 【，我们把树烈分层， 树叶看作树的最后一层，不妨记作k ，与树叶直接相连接的所有点看作树的第k 一1 层，剩下的依次类推。对于j = 1 ，2 ，3 ，k 用体，+ 。和以一，分别表示位于第，层的顶 点数以及顶点的度数。玩表示在第一层的顶点个数，当n k = 1 时这种树2 【简称之为 根树，并且根树的第一层这个点称之为根。强代表第k 层的顶点数。 图3 - 1 给出了这种树瓤的一个例子，并且每个顶点也被标上了数字( , r l = 2 4 和 n k = 2 ) 1234 56 。7891 01 11 2 1 31 4 1 5 1 6 1 71 8 1 92 0 2 12 22 32 4 图3 - i 早期，j a s o nj m o l i t i e m o 【3 9 】给出了树的代数连通度的一个上下界。事实上，对 于这种特殊的树戮，它的度序列呈规律性的排列。因此不仅它的代数连通度有一 定的特殊性，而且它的拉普拉斯特征值整体有相当j 凉人的规律性可供挖掘。因此 最近几年关于树的拉普拉斯矩阵最大特征值的研究越来越深入。 在2 0 0 6 年，o s c a rp o j o 给出了树烈的拉普拉斯矩阵的特征值新的计算公式。 定理3 1 1 4 设图g 是树甄，且它的第一层顶点n 。= 2 ，巍的拉普拉斯矩阵 为( g ) ，则有 ( a ) 虿的最大特征值等于l ( g ) 的最大特征值。 ( b ) 巧的最小特征值可以表示图g 的代数连通度。 1 6 第三章树的拉普拉斯谱半径 其中虿表示如下尼阶矩阵 硭= 扣了d ：扛了 扫了d ， 扣：了 d t + 1 实际上，像这种特殊的树，早在1 9 7 2 年o j h e i l m a n ，e ，h “e b 两位作者在 文【4 1 提到的b e t h e 树就具有上述特点。树图模型近年来已经引起物理学、概率论 及信息论的广泛兴趣。现在我们给出b e t h e 树的具体定义。如果一个无权值的k 层 根树甄并且同时满足如下两个条件： ( 1 ) 根点有d 度，且与根点相邻接的点有d + 1 度。 ( 2 ) 第k 层的每个顶点的度数均为1 ( 被称为树叶) 。 我们则称这种根树2 【为b e t h e 树，记作召，例如图3 2 的b e t h e 树b 图3 2 在2 0 0 6 年8 月，o s c a rr o j o 推广了b e t h e 树【4 1 1 的概念：广义b e t h e 树是指同一 层的顶点其度数都相同的根树，记最为广义后层b e t h e 树( 如下图3 - 3 ，树段) 。 图3 - 3 o s c a rr o j o 在上面研究的基础上，最近又继续深入的提出了广义b e t h e 树的并 1 7 留历 电子科技大学硕士学位论文 集的问题，广义b e t h e 树反的并集是指r 份反树的合并，纬表示，_ 个根形成的圈， 并记作磁”。例如，图3 - 4 表示了( 磁3 和矽，) 。 图3 4 在上图图3 4 中，可以观察出顶点总计有4 层： 在第一层，3 个顶点构成一个圈鼽，它们每个顶点度数均为4 。 在第二层，有6 个顶点，它们每个顶点度数均为4 。 在第三层，有1 8 个顶点，它们每个顶点度数均为3 。 在第四层，有3 6 个下垂点。 定理3 1 2 4 2 】设图g 是图磁”，且己( 磁) 是图b 的拉普拉斯矩阵，= 2 s + 1 或，= 2 s ，则有 ( a ) 矩阵疋。的最大特征值等于三( 磁n ) 的谱半径。 ( b ) 矩阵瓦。的最小特征值可以表示磁一的代数连通度。 其中正，表示如下k 阶矩阵 第三章树的拉普拉斯谱半径 瓦，= 1 畋一l 师d 2 抠j 属j以 a g a - = _ , - 1 而d k 一。托j 以id k - 2 c o s 一2 ；r l ，= 0 ，l ，2 ，s 在2 0 0 6 年1 1 月，o s c a rr o j o 又在上面的基础上给出了带有权值的b e t h e 树的 拉普拉斯矩阵最大特征值的新结果。 定理3 1 3 【4 3 】 设图g 是带有权值的尼层b e t h e 树，三( g ) 是图g 的拉普拉斯矩 阵，则有 ( c ) 瓦的谱半径是l ( g ) 的谱半径。 ( d ) 设s = m a x j ：q ) 。( = 1 ，2 ，k - l ，q = n j n j + i ) ，那么z 的 最小特征值是图g 的代数连通度，并且z 的谱半径是l ( g ) 的次大特征值。 其中乃表示如下尼阶矩阵，第歹层和第j + l 层相连结的每条边的权值为吒一， t = ( 乃一1 ) 巧一。+ 巧。 乃= 4 厢晶 岛 再 从上面的综述可以发现，以o s c a rr o j o 为代表的学者们对特殊性质的b e t h e 树的研究不断深入，每次都把问题推进一步，这种发现问题思考问题的方法也启 发了我们，使我们很自然的想到了对带有权值w 的广义的b e t h e 树吃的并磁7 的研 究。 3 2 带有权值的广义b e t h e 树的拉普拉斯特征值 为方便起见，我们把带有权值w 的广义树色的并集简记为b ：w ，现在分别 给出图b ：，的拉普拉斯矩阵和邻接矩阵的定义。 1 9 吁厢 吁 电子科技大学硕士学位论文 图b ：。的拉普拉斯矩阵的定义为 i _ ，且f 与，相连 i - ，且f 句不相连 ，i = j 图b7 k , w 的邻接矩阵的定义为 = f 辫 下面我们给出了一个带有权值的图b 七r ，的例子b4 3 ，w ( 如图3 - 5 所示) 。 l2 34 567 891 01 1 1 2 图3 5 我们发现在上图中共有四层，在每一层，其顶点的度分别为 吐= 1 ，吐= 3 ，以= 4 ，以= 4 和边的权值为 w = 4 ，w 2 = 3 ，w 3 = 2 ，w 4 = 2 n k 小。表示在第层的顶点数 2 0 ， 办 以 似，腩 一 o 一 ，、l 一一 正b 第三章树的拉普拉斯谱半径 n k 一，= ( 矾一，+ i 一1 ) n k 一，+ l ，2 k 一1 一l = ( 畋一2 ) n t 为了后面计算推导等的方便，我们引入了下面的定义。 定义1 设 磊= 哆= ( 乃一1 ) 一。+ ，j = 2 ，3 ，k 一1 瓯= ( 以一2 ) w k l + 2 对上例，由定义1 可以得到如下各式。 磊= w = 4 嘎= ( d 2 1 ) w l + w 2 = 1 1 色= ( 以一1 ) w 2 + w 3 = 1 1 哦= ( d 4 2 ) w 3 + 2 w 4 = 8 我们先介绍以下标记： 0 代表所有元素是0 的矩阵。 i 。表示m 阶的单位矩阵。 表示所有元素都为l 的m 维列向量。 巳表示对角块矩阵且阶为n jx n j + 。 c j2 在例子b3 。w 中，我们有 和 e n j n j + l p n j 勺“ 。0 0 p 。 + 1 i i3 6 ，= 1 8 ，n 3 = 6 ，n 4 i i3 2 l ( 3 1 ) 电子科技大学硕士学位论文 n l o = z ， 他 ，z ，一 2 = j ， 吃 塑：2 心 对于在( 3 1 ) 中被表示的矩阵；h t 所示 q = d i a g e 2 e 2e 2e 2e 2e 2e 2 乞e 2e 2 e 2e 2 吃e 2e 2e 2e 2e 2 c 2 = d i a g e 3 e 3e 3e 3e 3e 3 c 3 = 批g 乞e 2e 2 ) 由以上可以推出三( b ；。) 和彳( g ) 矩阵分别如下： 和 其中 l4 1 3 6 _ 4 c l 三( b ；，。) = i 一。一13 l i c l ；s - 13 1 i c 。2 2 c 3 i_ 2 8 1 3 - 2 e 3 ( o ) a ( b ；。) = 0 4 c l 4 c t0 3 c 2 3 z 0 2 c 3 2 42 e - - , ，( o ) 1 i v ， e ， ) = 1o o 0 o1 l 引理3 2 1 【4 2 】 如果，= 2 s ，那么矩阵e ， ) 的行列为 d e t e r ( 加( 棚) ( 口_ 2 ) n ( 州c o s 等) 2 如果厂= 2 s + 1 ，那么e ，0 ) 的行列为 d e te r ( 加( ) 血( 棚c 。s 孚) 2 一般情况下，如图磷。采用以上标号可以得到如下块三对角矩阵 第三章树的拉普拉斯谱半径 和 三( b ：。) = 4 1 月l w lc l w 1 0 吒i 也 一心c 2 彳( s r ) = 一w 2 弓 。 0 w 0 c 1 0 艺 引理3 2 2 设m 是块三对角矩阵 令届= 瓯 和 m = 蟛弓 盈i 。， w 2 弓 瓯一2 i 一w k 一2 q 一2 一一：c 0 ： 瓯一。i -