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

摘要 摘要 设g 是即阶简单连通图，日是图g 的线图，d 和4 分别为g 的顶点度对角矩 阵和邻接矩阵，现和四分别为日的度对角矩阵和邻接矩阵，泸d i a g 凶：“v 耳g ) ) 是一对角矩阵。则工= d 4 称为g 的拉普拉斯( l a p i a c e ) 矩阵，而墨三d 十d 称为拟拉 普拉斯矩阵。研究图的l a p l a c e 矩阵的特征值有着重要的图论意义和实际意义，因 为它与图的许多不变量有着密切联系。在许多应用中，往往需要l 叩1 a c e 矩阵最大 特征值a l ( g ) 的好的上界估计值。本文针对五1 ( 6 ) 的上界估计问题做了以下工作： 1 综述了近年来有关五l ( g ) 的上界估计的主要结果，并作了全面比较分析。 2 将非负矩阵理论应用到相似变换矩阵d i 肋i ，d 孑肋；和，。丑u i 并结 合图论性质获得了旯l ( g ) 的几个用顶点度数和顶点平均二次度表示的新的紧的上 界。并确定了等式成立的全部极图。同时几个例子用于说明这些新的结果是不可 比较的，并在一定意义上改进了现有的大多数结果。 3 将特征值与特征向量的关系应用到线图的邻接矩阵丑并利用不等式方缩技 巧和图的性质获得了丑( g ) 的一个用图的度序列，边数表示的紧的上界估计式，并 确定了相应的极图，同时举例说明在一定情况下该估计值在同类结果中最优。 4 利用矩阵分拆技巧将三分拆为两个矩阵和的形式并利用著名的w e y l 定理 给出了一类具有割点、割边图的l a p i a c e 谱半径的几个上界估计式。这些估计式将 高阶图类的l 印1 a c e 谱半径用较低阶的子图的l a p l a c e 谱半径来表示。图例表明这 类结果在某些图的l a p l a c e 谱半径的估计上获到了比较好的效果。 关键词：图的拉普拉斯矩阵，最大特征值，矩阵相似变换，矩阵分拆 a b s 羊r a c e t g b e as i 戳p l e 鞠巷强e 娃醴g 撂癜w i 氇栉v 搬i e e s 鞠d 霉b o 她l 纽o g 穗叠o f g ， d e n o t e da 1 1 d 4 b en l e d i a g o n a l m a t r i x o f v e r t e x d e g r e e sa 1 1 d t l l ea d j a c e n c y m a t r i xo fg ， 蛐i l e 丑甜髓d 嚣b e 也e 出韪g o 羲a 圭融毡越xo fv e 蹴xd o 豁s 嬲dt 量捃a 氆勰e n e y 搬搬蠢xo f 援 r e s p e c t i v e l y l e t 胪d i a g 慨巩：“v e ( g ) ) b ead i a g o n a lm a t r i x t h e nt h em a t r i x 工印“ 黼d 转喇主sc a l l e dt kl a p l i a n 瑚瓣i x 强dt h eq u s i l 帮l i 越磁越d xo fg 8 e p a r a t e l y t h el 印i a c i a ne i g e n v a l u e so fag r 印ha r ei m p o r t 趾ti nt h e 科a p ht 1 1 e o 以 b e e a u s e 论e yh a v 尊ad o s ef e l a t i o nt on u m e 糖u sg r a 烛i 蚪a r i 嬲括。l nm a n y 婶瘿i c 8 t i o 觳s ， g o o du p p e rb o l l l l d sf o r 名i ( 回，t 1 1 el a 增e s tl a p l a c i a l le i g e n v a l u eo f ag r a p hg ，a r en e e d e d 王n 搬i sp a p 娃瓣南l i o 谢n gr e s u l 招a o b 掘i n e 出 1 t h em a i nu p p e rb o u n d sf o r 五i ( g ) a r es u n l m a r i z e da n dc o m p a r e di nd e t a i l 2 ，s e v e r a ln g wa n ds h a 翠u p p c r b o u n d 8f o r 旯l ( g ) i n 锄撇so ft h ev e n e xd e g r e ga n d 铂ea v e r a g e2 一d e g r e ea r eo b t a i n e db y 印p l y i n gn o n n e g a t i v em a t r i xt h e o r yt om es i m i 】a r i n a t r i x 鼢一置d 5 ，d 孑丑口嚣a n d ，一5 丑u ，r e s p e c t i v e l y m o r e o v e r 、ed e t e r m i n ea l l e x t r e m 越g r a p h sw h i c ha c h i e v et h e s eu p p e rb o u n d s a n dt h e ns o m ee x a m p l e st o i 1 1 u s t r a t et 1 1 a to u rr e s u l t sa r eb e t t e rt 1 1 a nt 1 1 ee a r l i e ra n dr e c e n to n e s 协8 0 m es e n s e 。 3 a no m e rt y p eo f u p p e r b o u n df o r 五l ( g ) i nt e 蛐so f 蜘ed e g r e es e q u e n c ea n 蠢t h e e ( 培en u m b e ro fg a r eo b t a i n e db yu t i l i z i n gm ei n e q u a l i t yt e c h n i q u e sa n d 协er c l 撕o no f t h em a 蕊x 雪w i 像i 括e i g e n v a l u e s ，a n dw e 稿s od e t e r m i n et 圭l oe x t r c m a lg r a p h s 4 i nc h a p t e rt h r e e ，s o m eu p p 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 lm d i u so fag r a p h w i 像e u tv e r t i c e so re mo d g e sa 揩沓v e nb ys 。p a r a t i n g 氆el a p a l g i 张m 乱f i x 证t ot w o m a 倒c e sa n du s i n g 胁o u sw e y lt h e o r e m n e s eu p p e rb o u 丑d sa r ep r e s e n t e db yt h e 毛a p 】a e i a ns p e e 亡r a lf a d i u so f 蠡es u b g f a p h so fg w 魏l e l lw i 饿l a r g e 豫f u n h e 黝o r c ，s o 黼e 蹴a m p l e ss h o wn l a t 也e s eu p p e fb o u n d sa r eg o o di ns o m ec a s e s 1 ( e y w o r d ：t h el 神l a c i a nm 越一xo f g r a p l l s ，t h e1 a 疆e s te i g e 删a l u e ，t 1 1 es i m i l 甜1 n 基t r k ， m a t r i xp a n i t i o n i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： i 王盘：已日期：d f 年月箩日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：江丞：彦 导师签名：救氛也 日期：z 叩莎年月乡日 第一章引言 1 1 预备知识 第一章引言 设g 爿k 司为具有即个顶点m 条边的简单图，其顶点集为矿( g ) = 嘞，“z ，”。) ， 边集e ( g ) = 确，e ：，g 。) 。d ( 啦) 为顶点嘶的度，简记为讲，它表示和它关联的边 的数目。本文总假定d ( ”。) d ( 甜：) d ( “。) ，并称其为图g 的度序列。与顶点 “相邻点的集合记为帆，而与“相邻点的度数的平均值记为m 。，即 肌砷i v 喵v 川g ) ) ，阮= 去蚤“ 其中v “表示顶点v 和“在图g 中相邻。图g 的度对角矩阵和邻接矩阵分别 记为d ( g ) = 威昭( 凶，d ：，d 。) 和4 ( g ) = ( 口。，) ，其中当顶点“和v 相邻的时候 口。，= 1 ，当“和v 不相邻的时候口。= 0 。显然一个简单图的邻接矩阵是一个实对 称的( 0 ，1 ) 矩阵，它的对角线元素全为o ，其顶点“所在行的元素总和为顶点“的度 巩。图g 的l a p l a c e ( 拉普拉斯) 矩阵定义为工( g ) = d ( g ) 一爿( g ) = ( f 。，) ，其中 当”和v 相邻的时候，。，= 一1 ，当“= v 的时候f 。，= 巩，否则，。，= o 。若给图g 一个 定向，即对每条边取其一端点为正端点，另一端点为负端点，则其边与顶点的”所 阶定向关联矩阵q ( g ) = ( g 。) ，其中当“是p 的正端点时g 。= 1 ，当“是8 的负端点 时g 。= 一1 ，否则g 。= o 。于是图g 的l 印i a c e 矩阵和q ( g ) 满足上( g ) = q ( g ) q ( g ) 7 。 图g 的l a p l a c e 矩阵所对应的二次型为皿( g ) z 7 = ( x 。一x ，) 2 ，其中z 是”维 实向量。易知工( g ) 为实对称、半正定、奇异m 矩阵，所以其全部特征值为非负实 数。又正( g ) 的行和均为o ，故o 是其最小特征值，相应特征向量为全l 向量。因 此可假定工( g ) 的特征值为 ( g ) 也( g ) 。( g ) = o 。以下简称图g 的l a p l a c e 矩阵的特征值为l a p l a c e 特征值。设风g ) = d ( g ) 十4 ( g ) ，称为g 的拟拉普拉斯矩阵。 熟知当g 是连通图时，厨g ) 是非负、实对称的不可约矩阵。 所谓偶图是指图g 的顶点集有一个划分净( 以固，使得g 的每条边的两个端 点分别在u 和s 中，而u 或s 中任何两个点都不相邻。熟知一个图为偶图的充要 条件是它不含奇圈。而正则图是指图中每个顶点的度都相同。特别一个图如果是 电子科技大学硕士学位论文 偶图且膏正则，则称为i 正则偶图。若u 中点的度均为i ，而s 中点的度均为， 则称这样的偶图为( 屯0 半正则偶图。已知| j 正则偶图的最大l a p l a c e 特征值为2 乜 而( 毛_ ) 半正则偶图的最大l 印l a c e 特征值为斛，。在研究图g 的l a p l a c e 特征值的 时候还经常会遇到一些特别的图类，如完全图蜀，圈c ，星图芷1 。和路r 。 图g 的线图日是指将g 中边看作点，即唧) = 厨g ) 。若两条边在图g 中相邻， 则在线图中作为点相邻。显然若g 是连通的，则其线图也是连通的。线图的邻接 矩阵丑也是实对称的非负矩阵，且当g 是连通图的时候，四是不可约的。 实矩阵的谱是指矩阵的特征值连同特征值的重数组成的集合。若矩阵 厶。的 不同特征值为丑 如 厶，其相应的重数为m ( 丑) ，则其谱记为 勋耐m ) ： 以 ， 。、。 l 珑( ) m ( 丑) i 这里 ，a ：， ；互不相同，且二m ( 五) = 玎。特别一个矩阵的最大特征值也 称为该矩阵的谱半径，记为p ( m ) 。本文中其它未定义的术语和符号参见 1 ，2 ，3 。 研究图的l 印l a c e 特征值有着重要的图论意义，我们可以利用它来估计图的许 多不变量，比如连通度、等周数、直径、带宽、最大割、平均最小割、扩充子等； 同时l 印l a c e 特征值还有着重要的实际意义，它在物理、化学、生物和计算机网络 中有着广泛的应用，因而越来越受到人们关注 4 ，5 ，e7 ，8 1 。 图的l 印1 a c e 特征值和邻接矩阵的特征值都是图的同构不变量。但是邻接矩阵 的特征值理论研究已经非常成熟并且已经有大量的成果，而l a p l a c e 特征值的研究 相对来说少一点，同时由于l a p l a c e 矩阵的定义中引入了度对角矩阵，所以l a p l a c e 特征值不仅与图的邻接矩阵密切相关，而且更能反映图的图论性质，所以近年来 关于l a p l a c e 特征值的研究非常活跃。特别是在一些具体应用中，最大l a p l a c e 特 征值起着很重要的作用。因此针对最大l a p l a c e 特征值的研究更为重要，这其中最 关键的一点就是寻找最佳的上界估计值。 对于一些特殊图类，我们可以直接计算其l a p l a c e 谱如下： r。n 订阶完全图茁。：印p c ( 工( k 。) ) = i ，“，：1 ； n 阶圈c 。： ：4 s i n2 里，扣o ，1 ，即一1 聍 胛阶路只，：丑= 4 s i n2 昙，f = o ，1 ，n 一1 z 聆 2 第一章引言 玎阶星“删眠“) ) - ：行1 20 。 但是对于一般的高阶图，求上( 回的特征值意味着解高阶代数方程，然而当阶 数大于4 的时候，一般代数方程无通用解法，通常只能通过图的一些不变量，比 如边数、顶点数和顶点度等的一些简单关系反映出特征值的估计值。 1 2 拉普拉斯特征值研究的起源 l a d l a c e 矩阵最早出现在基尔霍夫研究电流理论时发现的矩阵树定理中【9 】。 定理1 1 ( 矩阵树定理) 即阶图g 的复杂度颤g ) ，即生成树的数目等于其l 印l a c e 矩阵三( g ) 的任何一个n 一1 阶子式。特别有 1 女( g ) = 二 ( g ) 九一l ( g ) 。 n 矩阵树定理在不同研究领域有多种推广形式。至于最早用l a p l a c e 特征值来研 究图的不变量的工作则出现在1 9 7 3 年f i e d l e r 的文章中【1 0 】，他给出了图的次小 l a 口l a c e 特征值与图的连通度的关系。 定理1 2 ( f i e d l e r ) 设g 是 阶图，则g 连通当且仅当 一，( 回 o 。设图g 的连通 度和边连通度分别为“g ) 和p ( 回，则有 。( g ) v ( g ) 8 ( g ) 。 因此f i e d l e r 也把次小特征值厶，( g ) 称为图g 的代数连通度。本文侧重于研究 图的最大l a p l a c e 特征值。 1 3 研究拉普拉斯特征值的基本方法 研究图的l a p l a c e 特征值的方法和一般研究矩阵特征值的方法相似。但由于 l a p l a c e 矩阵的特殊性和它与图的密切关系，它和一般研究矩阵特征值的方法又有 所区别。从作用对象来说可直接以上( g ) 为研究对象，也可针对线图的邻接矩阵刀。 事实上，文 1 1 已经证明i q ( g ) 7 q ( g ) l = 2 l ，+ 四，这里俐表示将矩阵p 的每个元 素取绝对值，而厶，为删阶单位矩阵( 月? 为图g 的线图的顶点个数) 。因q ( g ) 7 q ( g ) 和上( g ) = q ( g ) q ( g ) 7 具有相同的非0 特征值，所以可以用丑的特征值度量三( g ) 的特征值。从所用工具上看有以下几类常见方法： 电子科技大学硕士学位论文 1 利用特征值和特征向量的关系 设硪，”h g ) ) 7 是工( g ) 的最大特征值九l ( q 所对应的特征向量，则 ( g ) x = 上( g ) x ，从而 ( g ) z 。= 。，。，x ，。利用不等式性质进行放缩再结合 图的特点进行变形这是处理特征值和特征向量关系的常见方法。 2 圆盘定理和b r a u e r 定理的应用 我们都知道圆盘定理和b r a l l e r 定理是矩阵特征值研究中的经典理论，它分别 用一系列的行( 列) 格尔圆盘，卵形域把矩阵的特征值覆盖在其中。其中这些圆 盘或卵形域的边界都是由矩阵的行( 列) 的元素( 对角元除外) 的绝对值之和确 定。而对图的矩阵来说，这些元素可由图中点的相邻关系确定，因此运用这些理 论往往会收到较好效果。 3 利用非负矩阵理论 众所周知，非负矩阵中有很多关于矩阵特征值估计的结论和方法。如f m b e i l i u s 定理等。而图论中的矩阵如拟阵顾回、线图的邻接矩阵丑本身是非负的，所以将 非负矩阵的一些理论方法应用到这里将是非常有必要的。 4 利用图的分解技巧 比如在图中通过添加或删除一些边或顶点再利用c a u c h y 内插定理来寻找特征 值的估计也是一种重要手段。 5 。矩阵相似变换的应用 由于相似矩阵具有相同的特征值，所以通过相似变换将三( g ) ，丑变成其它矩 阵，再通过对变换后的矩阵进行特征值估计往往会得到很好的效果。常见的相似 变换有：d 。置d ，d 占肋。，d 一豆d ，d 手肋；。其中d 为图g 的度对角矩阵， 而d 。为g 的线图的度对角矩阵。当然还可以构造出一些新的相似变换。 以上方法可以统称为代数方法，也就是将图论性质和矩阵理论结合起来处理 l a p l a c e 矩阵。在具体应用中，这些方法并不是单一的，完全独立的，往往会共同 使用，比如相似变换和非负矩阵理论就常常一起使用。 除了上述代数方法之外，还有几何方法。即研究l a p l a c e 矩阵相应的二次型， 或者将转移l a p l a c e 矩阵c ( g ) = d ( g ) 一上( g ) d ( g ) 一视为r i e 咖1 1 a n 流形上l a p 】a c e 箅予的离散形式，从而将l a p l a c e 算子理论引入l a p l a c e 矩阵特征值的研究中。另 外还有概率方法等【9 ，l 。 。 本文主要采用代数方法，特别侧重于矩阵相似变换和非负矩阵理论的应用。 4 第二章图的最大拉普拉斯特征值 第二章图的最大拉普拉斯特征值 2 1 目前关于最大拉普拉斯特征值上界估计的情况 自8 0 年代初以来，关于l a p l a c e 特征值问题的研究发展迅速，在短短的一二 十年内国内外取得了大量的非常有价值的成果。这些成果主要集中在图的最大、 次大、次小及第_ j 特征值方面，就是用图的不变量来表示这些特征值【9 。另外，研 究图的l a p l a c e 特征值在一定范围内的数量也是常见问题之一。 本节主要简略介绍利用图的边数、顶点数、顶点度和平均二次度来估计最大 l a p l a c e 特征值的一些重要结果。首先是a n d e r s o n 和m o r l e y 在1 9 8 5 年给出了五l ( g ) 的一个上界。 定理2 1 【13 】设g = ( 旧是n 阶图，则 ( g ) m a x d 。+ d ，：o e ( g ) ，( 2 1 ) 其中等式成立当且仅当g 是正则或半正则偶图。 在1 9 9 7 年李炯生和张晓东利用度序列改进了这个结果，他们首先给出了图的 线图的最大特征值的估计式。 定理2 2 设矾d ：d 。是”阶图g 的度序列，丑为图g 的线图的邻 接矩阵，提丑的最大特征值，则有 ( d 1 + d 2 2 ) ( 凶+ 以一2 ) ， 其中等式成立当且仅当g 是正则图，或具有3 或4 个顶点的路。 然后他们在此基础上得到最大l a p l a c e 特征值的如下上界 定理2 3 设d l d 2 2 d 。是 阶图g 的度序列，则有 ( g ) 2 + ( d 1 + d 2 2 ) ( d 1 + d 3 2 ) ，( 2 - 2 ) 其中等式成立当且仅当g 是正则偶图，或星图，或具有3 或4 个顶点的路。 记，= m a x 矾+ d ，：“v e ( g ) ) ，设z ，y 矿( g ) 满足叫e ( g ) 且d ，+ d 。= ，。 电子辩授大学联士学经论文 另记s = m a x 矾+ 以：”v 层( g ) 一 瑚) 。照然r 是图g 的边的两个端点度数之和 静最大僮，蒜s 是袅捧边矽e ( g ) 后裁余逑的孬个端点度数之窥瀚最大穰。荦幂 r j 夺和张又在上述基础上将结果改进为 定瑾2 4 阳对 除圉g ，有 五 磊，澍 丑( g ) 蔓懋妇。十厄j 而j 丽 ( 2 - 2 2 ) 其中等式成立当髓仅当g 是正则或半正则偶图。 涯鞠：记膨= 蚤。j 国一磊露，瘸英元素( f ，) 为 电子科技大学硕士学位论文 m # 2 d t d n d 矗 o i = j ；， 其它 则有弗( 肘) = 画一磊+ 孚= 哦一玩+ 珊，于怒 ，f “f 碍( m ) = 坍f o ( 柳 忙j = 一磊) ( 蕊一磊+ 溉) + 孚( 力一磊+ 秘) ，一“l = ( 或一磊) 2 + ( 蕊一磊) 撤t + 击莠匆( 喝) + 妄丢谤+ 南毪) 由芦( 槲) = p c d 。皿) 一以= p ( 置) 一巩墨靶野趣( 幻及引理2 2 2 即得( 2 - 2 2 ) 。 湿然嬲楚菲受不可约豹，禳搭弓| 瑾2 2 3 和注记l 当盥仅当嬲是行蕞刚鹣对 候f 2 ，2 2 ) 中等式成立。即对任意的f ，d 一肌i - 蟊都相等，也就是d 卜州，对任意的f 相等。 又由萼| 理2 2 2 翔g 怒谲图，予是檄据潘文f 2 8 】中定理2 。4 懿证羁可知往2 2 ) 中等式 成立当且仅当g 是派则或半正则偶网。 霾铡2 1 ：在魏我们逶过襄下两个强瓯翻国亲滋臻掰上雾g 。2 0 ) ，2 之1 ) ，( 2 。2 2 ) 在某烂情况下优于文中提及的部分经典估计值。部分上界估计值如下表2 4 ； 蹦2 - 3 上爨( 2 2 0 ) ，( 2 2 1 ) ，0 2 2 ) 秘部分魏鹰各上赛辩毙强铡 萋 蜀( g ，( 2 4 )( 2 - d( 2 堪)( 2 一1 0 )0 之疆- 2 1 )( 2 2 2 ) i g 。 5 2 6 25 576 6 3 36 4 4 96 5 8 26 3 8 55 4 4 4 国 5 7 3 2 77 7 毒8 37 。毒6 46 3 5 87 毒0 36 。4 7 7 | 第二章图的最大拉普拉斯特征值 从表2 4 可以看出在一些情况下( 2 2 0 ) ，( 2 - 2 1 ) ，( 2 - 2 2 ) 比其它上界要好，但并 不是始终具有优越性。相对来说( 2 2 2 ) 效果最好，但计算比较复杂。 2 2 2 矩阵相似变换在最大拉普拉斯特征值研究中的应用 在这一部分我们将考虑把非负矩阵理论应用到简单连通图的拟l a p l a c e 矩阵置 和线图的邻接矩阵丑这两个非负不可约矩阵的相似变换矩阵上，然后利用c a u c h y 不等式获得若干新的紧的上界，并着重确定等式成立时相应的极图。这些上界将 在很大程度上改进现有的结果。 引理2 28 【3 川( f r o b e l l i u s ) 设肘。( 矾7 ) 为n 阶的非负不可约矩阵，p ( 肘) 为膨 的谱半径，记冠( 脚) 为第f 行的行和，也就是冠c m ) = 蜀；。m f 。则 m i n 且，( f ) 1 1 f 开 p ( 肘) m a x r ，( f ) 1 1 s f h ， ( 2 - 2 3 ) 而且( 2 2 3 ) 中等式成立当且仅当所有行和相等。 对定义在复数集上的行玎矩阵a = ( 嘶) ，给定如下记号 r ，= i 口fi ，j = l 疗：s = u s p ，其中 j f j 巩，故有r 。( m ) 矾+ d ，m 。于是根据引理2 2 2 和引理2 2 8 有 丑( g ) p ( 厨) = p ( 肘) m a ) 【忸。( 肘) ：“矿( g ) m a x 协+ 瓜：“矿( g ) ， 从而( 2 1 0 ) 成立。 第二章图的最大拉普拉斯特征值 假定( 2 1 0 ) 中等式成立，则以上不等式均为等式，且由引理2 2 8 知埘的所有 行和相等且对任意“坎o ，有风( = d 。+ d 。m 。，即( 2 2 4 ) 中等式都成立。由 ( g ) =