（计算数学专业论文）图的特征值与laplace特征值的研究.pdf

， 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 拉经 日期：洌秒年 月矽日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 盘堡 导师签名： 7 茛纣匝 日期：汐矽年，月矽日 ， 摘要 摘要 图的邻接矩阵的特征值称为图的特征值，研究图的特征值和l a p l a c e 特征值是 近年来兴起而且发展迅速的一个活跃的研究方向，它也是属于组合矩阵论的一部 分，应用十分广泛。对大量的图g 来说，直接求出它们的特征值十分困难，于是 对图的特征值的估计便成为组合矩阵论中相当活跃的课题。 本文首先概述了图的特征值和图的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 特征值 a bs t r a c t w ec a l lt h ee i g e n v a l u e si nt h ea d j a c e n c ym a t r i xo fa g r a p ha st h ee i g e n v a l u e so ft h e g r a p h i nr e c e n ty e a r s ，s t u d yo fe i g e n v a l u eo fag r a p hi sa na c t i v er e s e a r c ht o p i c i ti sa p a r to fc o m b i n a t i o no fm a t r i x t h e o r y i th a sav e r yw i d er a n g eo fa p p l i c a t i o n s s o m e t i m e sw ec a nn o td i r e c t l yc a l c u l a t et h ev a l u e so ft h ec h a r a c t e r i s t i c sa b o u ta l a r g e n u m b e ro f g r a p h sn a m e dgs o ，e s t i m a t i n gt h eb o u n do ft h ee i g e n v a l u e so ft h eg r a p hh a s b e c o m ea na c t i v et o p i c t h i sa r t i c l em a i n l yd i s c u s s d et 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 xa n d l a p l a c e m a t r i xo ft h eg r a p h f i r s to f a l l ，w em a i n l ys u m m a r i z e dt h et h e o r ya n d p r o g r e s so fg r a p h s ，t h ee i g e n v a l u e s o ft h ea d j a c e n c ym a t r i xa n d l a p l a c em a t r i xo ft h eg r a p h s e c o n d l y , w ei n t r o d u c e dt h eb o u n do ft h ee i g e n v a l u e si nt h ea d j a c e n c ym a t r i xo ft h e g r a p h a n dt h ec h a p t e rg a v eas p e c i a lc l a s so fa d j a c e n c ym a t r i xe i g e n v a l u e so fa nu p p e r b o u n d b yt h es i m i l a r i t ym a t r i x w er e s e a r c h e dt h eb o u n do ft h ee i g e n v a l u e si nl a p l a c e m a t r i xo ft h eg r a p hn e x t a n dw e g a v ean e wu p p e rb o u n do ft h ee i g e n v a l u e si nl a d l a c e m a t r i xo ft h eg r a p h t h e nw eg a v es o m ee x a m p l e st o e x p l a i no u rr e s u l t sa r em o r e p r e c i s et h a nf o r m e r l yr e s u l t s f i n a l l y , w eg a v eal o w e rb o u n do ft h es q u a r es u mo ft h ed e g r e es e q u e n c eo fa g r a p h i t r e f l e c t e dt h ec o n t a c tb e t w e e n l a p l a c ee i g e n v a l u e sa n dt h e s eq u a n t i t i e s k e yw o r d s ：g r a p h ，e i g e n v a l u e ，l a p l a c ee i g e n v a l u e i i j1fffj】lffi jjffjjlffjjlffjjl|fjff 目录 目录 第一章引言1 1 1 研究背景1 1 2 基本概念及符号3 1 3 本文的主要内容7 第二章图邻接矩阵特征值的界，8 2 1 图的邻接矩阵特征值的上界的研究进展8 2 2 一类特殊图邻接矩阵特征值的界1 0 第三章图的l a p l a c e 特征值的界1 8 3 1 图的l a p l a c e 矩阵的上界的研究进展1 8 3 2 图的l a p l a c e 矩阵特征值的一个新上界2 1 第四章图的几个量之间的关系2 6 4 1 图的l a p l a c e 特征值与度的关系2 6 第五章主要结论3 0 致谢3 l 参考文献3 2 攻硕期间研究成果3 5 i 第一章引言 第一章引言弟一早ji 甬 本章分三个部分，首先介绍图谱理论研究的历史背景，接着介绍相关的图论 及矩阵理论的基本概念和术语，最后简单说明本文的主要内容。 1 1 研究背景 图论是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点 及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定 关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论属是一门充满生机的学科。随着现代科学的发展，图论及其在物理、化 学、计算机科学、运筹学、电子学、信息论、系统论、网络理论等方面的应用研 究都取得了迅速的发展。图论在以信息为特征的知识经济时代有着广泛的实用背 景。 研究图的谱分布与图的结构之间的对应关系，以及与之对应的图的标号问题， 是近年来兴起而且发展迅速的一个活跃的研究课题，是属于组合矩阵论的一部分。 对大量的图g 来说，我们还不能直接求出它们的谱，于是，对图的特征值的估计 是组合矩阵论中相当活跃的课题。近3 0 年来已有大量的相关文献和结果。对这种 问题的研究不仅在理论上能加深对离散结构的内在关系的刻画，在应用方面，比 如在网络优化与设计，集成电路设计及运筹学方面也有深远的实际应用背景。从 上世纪8 0 年代开始，国内外已有千余篇文献研究此类问题，其中有( ( s p e c t a ro f g r a p h y ) ) 等。图谱研究的重要性主要表现在以下三个方面： ( 1 ) 在量子化学中某些不饱和碳氢化合物的结构是用图来表示的。事实上，在 这样的分子里电子的能量级别就是对应图的特征值。分子的稳定性和其他化学上 的相关事实都与图谱和对应的特征向量都有紧密联系。 ( 2 ) 在图谱的证明中有很多图论和组合的定理，虽然定理的陈述中并没有明确 地提及到谱。但实际上，图谱已作为一个重要的工具应用在谱科技中。 ( 3 ) 最后一个是计算机方面的原因。图谱含有很多图的信息，对某些问题的研 究甚至可以用图谱来代替图，而谱就是一组不变数的有限序列，有限数序列很容 易放入计算机中。这样，我们就能较容易地用计算机来研究图论问题。 电子科技大学硕士学位论文 图谱理论所研究的对象主要包括图的邻接谱，l a p l a c e 谱，o 一谱，c 一谱，s 一谱， 其中对邻接谱，l a p l a c e 谱的研究最为普遍。 图谱理论既呈现出丰富多彩的形式， 而且各种不同定义的谱之间又有着相互联系。 图谱理论中研究的热门课题之一是图的邻接矩阵的特征值，也称为图的邻接 谱，研究图的邻接谱的意义在于它促使和丰富了图论和组合数学本身的研究，邻 接谱技巧已经成为图论和组合数学研究中一个重要的工具。著名数学家 n a s h w i l l i a m s 在论及图谱时称：“有某些特征上是纯组合的主要结果有这样奇妙的 特征，即如果不借助图的邻接矩阵的特征根的代数方法，是不可能得到现在所知 的结论的。”明确提出研究图的邻接谱最早是在1 9 6 9 年。十年后，几乎所有的涉及 到图的邻接谱的结论都被收集到( ( s p e c t r ao fg r a p h s ) ) 一书中，它的参考文献包含 了1 9 6 0 年到1 9 7 8 年之间5 6 4 篇文章。作为该书的一个补充，( ( r e c e n tr e s u l t si nt h e t h e o r yo fg r a p hs p e c t r a 一书于1 9 8 8 年出版，这本书回顾了1 9 7 8 1 9 8 4 年之间关于 图的邻接谱的结论，提供了超过7 0 篇的来自于数学和化学的文献。同时，该书还 收录了来自其他领域的文献。尽管有的文章包含微小的结论，有的是对已知结论 的再发现，如此之多的文献说明了图的邻接谱理论之丰富。图的邻接谱理论最近 的发展在1 9 9 5 年出版的专著 s p e c t r ao fg r a p h s ) ) 的第三版附录中有详尽的叙述。 1 9 9 7 年出版的( ( e i g e n s p a c e so fg r a p h s ) ) 一书中重点的阐述图的邻接谱理论中特征 空间的重要作用。在( ( a l g e b r a i cg r a p ht h e r o y ) ) 以及( ( a l g e b r a i cc o m b i n a t o r i c s ) ) 中 对图的邻接谱也做了详尽的叙述。 图谱理论中研究的另一热门课题是图的l a p l a c e 矩阵、l a p l a c e 特征值。对图的 l a p l a c e 矩阵和l l a p l a c e 特征值的讨论对于图论之所以重要，是因为可以用l a p l a c e 特征值来估计图的诸多不变量，如连通度，直径，带宽，二部宽，等周数，最大 割，扩充子，平均距离，边前项指数等等其中一些重要的不变量，如图的二部宽， 最大割，等周数等，除了反映图的一些结构性质外，还有广泛的应用，然而它们 的计算的复杂度属于n p h a r d 的，而l a p l a c e 特征值则可用多项式理论中渐进求根方 法来加以计算。研究l a p l a c e 特征值与图不变量间的联系的早期经典工作在1 9 7 3 年 f i e d l e r 的文章中被提出。有关研究l a p l a c e 特征值的综述文章时有发表，j t h m e r r i s ， m o h a r 等。这些文章即时报导了研究发展动向，同时也提出新问题和猜想。 图的谱理论研究的主要途径是通过图的矩阵表示( 邻接矩阵，l a p l a c e 矩阵等) 建立图的拓扑结构并给予研究。图谱理论的很多经典结论都可用于非负矩阵，因而 对它们的研究也推动了组合矩阵论的发展。 对图的特征值的研究研究方法主要有如下三种： 2 第一章引言 ( 1 ) 代数方法：即用矩阵论并结合图的图论性质来研究l a p l a c e 特征值。 ( 2 ) 几何方法：即研究图的拉普拉斯矩阵l ( g ) - - d ( g ) - a ( g ) 所对应的二次型 并结合图的图论性质来研究拉普拉斯特征值或将图的规范拉普拉斯矩阵 d ( g ) 一i 工( g ) d ( g ) 一i 视为r i e m m a n n 流形上的拉普拉斯算子的离散形式，从而将 拉普拉斯算子理论引入到拉普拉斯特征值的研究中。这方面的代表人物，前者有 m o h a r 等人，后者有f r k c h u n g 等。 ( 3 ) 概率方法：即通过引入随机路的概念，利用概率论的方法研究l a p l a c e 特 征值。 图的研究，尤其是图谱理论的研究实现了数形结合的思想，图的直观性和数 上的严密性，再加上图的研究方法的多样化，使得对图的研究越来越具有意义和 价值。 1 2 基本概念及符号 一个图g 是一个二元组，记为g = 矿( g ) ，e ( g ) ) ，其中y ( g ) = v 。，v ：，v 。) 称为图g 的顶点集；e ( g ) = e ，e ：，e 。) 称为图g 的边集。图g 的顶点个数称 为图的阶。 在图g 中，若顶点“，v v 且u 和v 是边e 的两个端点，记为e = “，v ) 或者e = u v ， 称u 与v 相邻接，同时称u ( v ) 与e 关联，与v 相关联的次数称为v 的度数，记为d ( v ) 。 在图g = ( v ，e ) 中，u v 的邻域记为n ( u ) ，它表示顶点u 在图g 中的所有邻 接点所组成的集合。 g = y ( g ) ，e ( g ) ) 为一个胛阶图，d 。表示顶点“的度数，m 。表示与顶点u 相邻 的顶点的度的平均值，n z , d 。m 。称为顶点u 的二次度。 图g 的邻接矩阵，我们通常记为爿( g ) = ( 口盯) 。，它是一个，z 阶方阵，这个方阵 的定义如下： f 1 ，如果f 与歹相邻接 口f 21 0 ，其它 显然，口f ，= 0 ，以f = 口，故而么( g ) 是一个实对称矩阵。我们称d e t ( 甜一彳) 为图 g 的特征多项式，用p ，( g ) ，( 净1 , 2 ，z ) 标记图g 的邻接矩阵的特征值。不妨将其 由大到小排列为p 。( g ) p 2 ( g ) p n - 1 ( g ) p 。( g ) 。图g 的邻接矩阵的最大特征 电子科技大学硕士学位论文 值称为图g 的邻接谱半径由彳( g ) = ( 口口) 。的定义，容易推知p ，( g ) = 0 ， p i 2 ( g ) = 2 m ，这些特征不以顶点标号顺序的不同而改变，我们记 s p e c g = 肛( g ) ，, 0 2 ( g ) ，只( g ) ) 为图g 的邻接谱，或记为 蹄c g = k 僦n ) ) 这里尸，( g ) 岛( g ) 只( g ) ，m ( p ，) 为肛的重数。显然，垅( 肛) = 甩，例 如完全图e 的邻接谱可表示为 扛1 厂 一1 1 、 s p e c k 一2 【1 川j 主对角线元素为图g 的度，其余元素为0 的矩阵称为图g 的度对角矩阵，通 常记g 的度对角矩阵为d ( g ) = d i a g d ( v ，) ，d ( v ：) ，d ( v 。) ) ，而l ( g ) = d ( g ) 一彳( g ) 称为图g 的l a p l a c e 矩阵。l ( g ) 的特征值称为图g 的l a p l a c e 特征值。显然l ( g ) 是 一个实对称的半正定矩阵。我们由盖尔圆盘定理知，l ( g ) 的所有特征值为非负实 数。记g 的l a p l a c e 特征值为以( g ) g = 1 , 2 ，甩) ，且设丑( g ) 如( g ) a 。( g ) ， 众所周知，旯。( g ) = 0 ，而且零作为l ( g ) 的特征值的代数重复度等于图g 的连通分 支的数量。图g 的最大l a p l a c e 特征值称为图g 的l a p l a c e 谱半径。l ( g ) 的次小 特征值允川( g ) = 0 的充要条件是g 不连通，因此g 的次小特征值与g 的连通度有 关，称之为图的代数连通度，记为口( g ) 。图g 的补图为g 。= ( 矿，e 。) 其中 e 。= f ，j ) ff ，j v ， f ，办仨e ) 。由于咒阶图g 及其补图g 。的l a p l a c e 特征值间存在 如下关系：对于2 i 刀，五，( g ) = 1 1 一五川( g 。) 。因此，图的代数连通度和最大特 征值的估计是可以互推的。 如果g ，= ( k ，e 。) 和g ：= ( ，e ：) 分别为m 和n 个顶点的图，无公共点，称 g 1 + g 2 = ( ku ，e ，ue 2 ) 为g 。和g 2 的和，称g 1vg 2 = ( g ? + g ；) 。为图g 1 和图g 2 的联图，g 。v g ：就是在图g l + g ：中添加由图g 。中每个顶点到图g ：中每个顶点的 边所得的图。 顶点集为矿( 尸，) = y 。，1 ，：，1 ，。) ，边集e ( 只) = y 1 v ：，v n - i v 。) 的图称为路只， 或者称为路 v ，v ：，v 。) ，又或路y ，一v 。，其中n - 1 是路只的长度。若图g 中的每 一对顶点之间有一条路，则称g 为连通图。分支数大于1 的图称为分离图。 4 第一章引言 任意两个不同顶点之间都有一条边相连的简单图称为完全图。顶点个数为，z 的 完全图记为k 。没有任何边的图称为空图，只有一个顶点的图称为平凡图。如果 一个图的每个顶点的度都相同，则称该图为正则图。 只与一个顶点相关联的边称为环。( e ，) = ( e ：) ，则称e ，和e ：是重边。无环 无重边的图称为简单图。允许有重边和环的图称为一般图。 设g = ( v ，e ) 为简单图，设彳矿，且x ，以x 为顶点，以两端点均在x 中 的边的全体为边集所组成的子图，称为g 的由x 导出的子图，记为g x 1 。设 y 互e ，且y 矽，以y 为边集，以】，中的边全部顶点为顶点组成的子集称为边导出子 集，记为g y 。 如果e 为图g 的一条边，用g e 记g 删去边p 后所得的图。更一般地，用 g 一 e ie 2 ，e 女 己图g 删去边e l , e 2 ，e 后所得到的图。设e v v ，用g + e 记 g 添加边e 所得到的简单( 或一般) 图，更一般地，用g + e 。，e ：，e 。) 表示图g 添加 边e ，e ，e 。所得到的简单( 或一般) 图。 如果g 为连通图，设x 量v ，若g x 不连通，则称z 为图g 的顶点割或点割， 含有k 个顶点的点割称为k 点割图g 中点数最少的点割称为g 的最小点割，称g 的最小点割中所含的顶点数为图g 的点连通度。设，e ，若g f 不连通，则称 ，为图g 的边割集或边割，图g 中基数最少的边割称为g 的最小边割，称g 的最 小边割中所含的边数称为图g 的边连通度。设s 是g 的一个最小点割集，则g s 不连通，称g s 的连通分支，c l ，c 。，m 2 。为g 在s 的连通分支。 v ( o ) = xuy ，xf - iy = 矽，且x 中任意二顶点不相邻，y 中任意二顶点不相邻， 则称g 为二部图；若z 中每个顶点都与】，中一切顶点相邻，则称g 为完全二部图， 记为k 删，其中m = ixi ，行= lyi ，y ( g ) = uv ，0 = 1 , 2 ，) ，f ly ，= 矽，f j ： 当且仅当两个项点不在同一个中时( f = 1 , 2 ，厂) ，此二顶相邻，则称图g 为完 全厂部图，记为k 。一扣棚，其中1 _ i = m f ，汪1 , 2 ，：若m l = m 2 = = m ，= m ， 则记为k 幽、。 凡舢，z f r o b e n i u s 定理若g 是一个至少有两个顶点的连通图。则 ( 1 ) 它的最大特征值p ( p 0 ) 是一个单根。 ( 2 ) 对应于特征值p ，其特征向量x 是正特征向量( 即所有分量都是正数) 。 ( 3 ) 若兄是g 的任一一个其它特征值，则一p 旯p 。 ( 4 ) g 的任一边被删去，最大特征值都将减小。 电子科技大学硕士学位论文 这个p 通常称为图g 的谱半径。 设a = ( a 。) c 雕“，我们称s ，= z c ：iz a 。| 0 ，且r ( a ) 为彳的单重特征值。 ( 2 ) 对应于r ( a ) 的特征向量为正向量。 ( 3 ) 对于a 的任一异于r ( a ) 的特征值旯均满足i 旯l 0 。 ( 2 ) r ( a ) 为么的特征值。 ( 3 ) 存在正向量x ，使得a x = r ( a ) x 。 ( 4 ) r ( a ) 是爿的代数( 因而为几何) 单重特征值。 6 第一章引言 代数方法是研究图谱和印肠c 口矩阵的主要方法之一，即应用矩阵理论并结合 图论性质来处理图谱和l 印肠c e 矩阵。本文中主要用代数方法作为研究手段。本文 所研究的图均为无环、无重边、有限无向的简单图。 “+ 二： 1 3 本文的主要内容 这一节将简单介绍本文的主要内容，本文主要分为三个部分对图谱进行讨论。 第二章主要讨论图邻接矩阵的特征值的界，首先是对前人对于该界研究进展的综 述，接下来是利用相似矩阵的性质对一类特殊图的邻接矩阵的特征值的上界进行 估计并得到如下结果： 我们假设g 为胛阶简单连通图，kc 矿( g ) ，q 是由点集k 导出的点诱导 子图，然后我们令日2 = g w k ，a l = m a x d g ( “) l “k ) ，2 = m a x d g ( “) k ) ， j = m a x d 日 ) l “k ) ，t = m a x d 川( “) l “哆) ，那么有 邸) 尘竺尘堕；垡! 坠型 等号成立当且仅当g 兰h l 岛，其中日l 为i 一1 阶s 正则图，飓为以一i + 1 阶( a 2 一t ) 正则图。 接下来，在第三章中利用拟拉普拉斯矩阵和相似矩阵的性质对图的l a p l a c e 矩 阵的特征值的上界进行估计，并得出一个新的上界如下： 假设图h 是一个有n 顶点和m 条边的简单连通图，那么 删) m 腿 尘监堕) 等式成立当且仅当图为正则偶图。 最后在第四章中，我们利用矩阵的性质讨论图量间的关系，得出图的度平方 和的界及其极值条件如下： 图g 是一个有，z 个顶点和m 条边的简单图，图g 有k 个连通分支，则 喜玲篝砌 等式成立当且仅当图g 的非零l a p l a c e 特征值相同。 电子科技大学硕士学位论文 第二章图邻接矩阵特征值的界 图的特征值也叫图的谱，图的特征值的分析即图谱分析是近几年来图论研究 的热点问题。本章主要是讨论图的邻接矩阵的特征值的上界。本章将首先介绍邻 接矩阵的特征值的上界的研究进展，然后定义一类特殊图，并给出它的上界。 2 1 图的邻接矩阵特征值的上界的研究进展 图的邻接矩阵的界的研究一直是图谱研究的主要问题之一，对它的研究已经 有以下的一些前人的研究成果，下面将分别一一介绍。 我们知道问题的研究总是从特殊到一般，对图特征值的研究也是一样，图邻 接矩阵特征值的上界的研究也是从特殊的图开始的。j h e i l m a n n 和h l i e b 最早给 出了树邻接矩阵特征值关于最大度的的上界。 定理2 1 1 【1 1 若图t 为，z 阶树，则p ( r ) 2 一1 。( 2 1 ) 这是关于树的邻接矩阵特征值的界，是比较粗糙的估计。 随后，r a b r u a l d i 和a j h o f f m a n 共同给出了图邻接矩阵特征值的一个界。 定理2 1 2 【2 1 假设图g 具有n 个顶点和m 条边，若m = 尼( 尼一1 ) 2 ，则 p ( g ) k 一1 ( 2 2 ) 等式成立当且仅当g 同构于g 兰k 。u ( 胛一i c ) x i 。 这是关于用图的边数表达的图的最大特征值的一个上界。 接着，s t a n l e y 改进了用边数表达的上界，得出一个新上界。 定理2 1 3 4 1 设图g 为咒阶简单连通图，其边数为m ，则 p ( g ) ( 一1 + 1 + 8 聊) 2 ( 2 3 ) 等式成立当且仅当g 兰k 。u ( ，z k ) k 。 之后，h m i n c 给出了关于顶点数、边数、最大度及最小度的图邻接矩阵特征 值的上、下界。 厂二一二 阵特征值的界 点m 条边的连通图，则 万2 m n p ( g ) ( 2 - 4 ) 等式成立当且仅当g 为正则图。 这里不仅给出了上界，同时也给出了下界，直观的表明了邻接矩阵特征值界 于图的最小度和最大度之间。 不久，洪渊给出了邻接矩阵特征值的另一个上界。 定理2 1 5 【5 】设图g 为具有r 1 个顶点m 条边的连通图，则 p ( g ) 2 ，钾一，l + 1( 2 5 ) 等式成立当且仅当g 同构与下列两种图：星图k h 一，和完全图k 。 这个上界还是关于用顶点数和边数表达的。 为了更加精确，洪渊、束金龙和方坤夫又一起改i t ( 2 5 ) 。 定理2 1 6 吲设图g 为具有n 个顶点m 条边的连通图，则 邸) 塑型坠粤塑 ( 2 - 6 ) 等式成立当且仅当g 为一个正则图，或者顶点度为万或，z 一1 的二度图。 2 0 0 1 年，a b r a h a mb e r m a n 和x i a o d o n gz h a n g 给出了一个图邻接矩阵特征值 关于度序列的上界。 定理2 1 7 7 1 若g 为咒阶连通图，g 的度序列为d l d 2 d 。，则 p ( g ) 器鹜g ) 崛( 2 - 7 ) l v n l u l 等式成立当且仅当g 为正则图或者半正则偶图。 用顶点度数估计图邻接矩阵特征值的上界一直成为研究的热点，于是束金龙， 吴雅蓉又进一步改进图邻接矩阵特征值的上界。 定理2 1 8 【8 1 若g 为玎阶连通图，g 的度序列为d l d 2 d 。，则 那，d,-1+血4(d,萼+1)2+砸4(i-1)(d,-d,) 陋8 ， 9 电子科技大学硕士学位论文 其中1 f n 。进一步，当i = 1 时，等式成立当且仅当图g 是一个正则图。当 2 f ，z 时，等式成立当且仅当图g 为正则图，或者图g 为满足：d ，= d ，= = d h = 玎一1 且d ，= = d 。= 万的二度图。 对图的邻接矩阵特征值的上界的估计的总都是寻求其与图不变量的关系，如 图的顶点，边，度等。 接下来举一个例子来看看上面得到的界的优劣程度。如图2 1 所示的两个图g ， 和g ，我们将比较的结果列表，即表2 1 。 g l 图2 1 图g ，葙g ： g 2 表2 1 图阶数 ( 2 - 2 )( 2 - 3 )( 2 4 )( 2 5 )( 2 6 )( 2 7 )( 2 - 8 ) g 1 42 7 0 22 7 0 232 6 4 62 5 6 22 4 4 9 2 3 0 3 g 2 63 7 7 23 7 7 253 6 0 63 7 7 23 8 7 33 6 4 6 从计算结果表2 1 我们可以看出，用( 2 - 2 ) 和( 2 3 ) 几乎没有改进，由( 2 4 ) 和( 2 7 ) 得出的界过于粗糙，但是计算方便简单，( 2 8 ) 得出的界的估计最为优越。由计算 结果我们可以看出，界的优越性并不是绝对的，它是相对的。 2 2 一类特殊图邻接矩阵特征值的界 上节中讨论了图的邻接矩阵特征值的上界的研究进展并对其结果进行了优越 性的比较，得出界的优越性是相对的。对图邻接矩阵特征值的界的研究已经日趋 完备，在本节中我们将讨论一类特殊图的邻接矩阵特征值的界的问题。 首先在本节开始之前，我们先定义一类图：g = g l g 2 ，其中g 1 ，g 2 分别为 k l 正则图和k 2 正则图。令坎g ) = 以g 1 ) uv ( g 2 ) ，以g ) 屯( g 1 ) u e ( g 2 ) u ，其中 1 0 第二苹图邻接矩阵特征值的界 f 2 甜f “iu i ev ( g o ，“v ( g 2 ) ) ，使得对所有的“f v ( g 1 ) ，d g u f ) = p ；对所有 甜v ( g 2 ) ，d g ( “，) 2q 。 在我们引入这类图的邻接矩阵特征值的上界之前，我们先给出一个引理。 引理2 2 1 【2 1 1 若b 为一个非负不可约的扎阶方阵，它的最大特征值为p ，矩 阵的行和分别为r l ，尺2 皿3 ，尺。1 皿。，那么 m i n r 。p m a x r i l i n l 1 ，所以有 r ，! l + ( 1 一三) j ， 1 ，i 一1 r i 2 + ( x 1 ) t ， f 尼n 显然 m a ) 【 r l ，r 2 ，r 。) m a x ! ，+ ( 1 一! ) s ，2 + ( x 一1 ) f ) 令 ! 。+ ( 1 一三) j ：2 + ( x 一1 ) f 这是一个关于x 的方程，解方程得到 s + 歹一2 + ( s + f 一2 ) 2 + 4 t ( a 1 一s ) 一一 2 因此 、，1 、2 + s f + ( s + f 一2 ) 2 + 4 t ( a i s ) p ( g ) a 2 + ( x 一1 ) = 二兰二= 竺二 为使等式成立，显然以上所讨论的所有不等式的等号均要成立。特别地，当 1 2 第二苹图邻接矩阵特征值的界 ，= 1 ，2 ，f 一1 时，d ，= a 1 ；对所有的“v ( h 1 ) 有d 日( u ) = j 。当k = f ，f + 1 ，胛时， 有d 。= a 2 ；x c n n 的u v ( h 2 ) 有d ，( “) = s 。n i gh 1 = g k 】为i - 1 阶j i e 贝j j f n ， h ，：g 圪 为聆一f + 1 阶( 2 一t ) 正则图。也就说，若定理中的等式成立，则g 兰h i 飓，那么d h ，( “，) = a l s 对所有的甜，k 成立，d 乩 ) = t 对所有的“成 寺。 反过来，由上面的证明很容易看出，g 兰h 1 飓时，定理中等式成立。 证毕。 通过定理2 2 2 ，对于我们去计算型如g = g 1 n g 2 这一类型图的邻接矩阵特征 值的上界将变得很容易。根据定理2 2 2 我们还可以得到下面的推论。 推论2 2 3 如果g - g l g 2 ，其中g l ，g 2 分别为k l 正则图和赶正则图。令 坎g ) = 坎g 1 ) uv ( g 2 ) ，耳g ) 司( g 1 ) u e ( g 2 ) u e + ，其中矿= “f “im f 坎g 1 ) ，“ v ( g 2 ) ，使得，对所有的聊v ( g i ) ，d ：( “f ) = p ；对所有u j ( ev ( g 2 ) ，d 川( “，) = q ， 那么 那) ：生坐型婴丝丝塑 ( 2 - 1 0 ) 证明：我们观察一下要证明的结论与定理2 2 2 的结论，发现我们只要令 a 1 = m 1 + p ，2 = m 2 + q ，s = m 1 ，q = t ，于是有 即) ：生尘竺丝等型! 型 即)：m2+q+m1_剑q+x(巫m1+q孚_(m2巫+q)2巫+4q(m1+p_m1) 胁m1+m州2+4(粤mi_m2)2+4pq 证毕。 下面，举例说明如何求此类图的界，求图2 - 2 图h 的邻接矩阵特征值的界。 ad 图2 2 图日 1 3 电子科技大学硕士学位论文 方法一：用传统的邻接矩阵方法求。因为图已经具体的给出，我们可以先把 它的邻接矩阵写出来，然后利用矩阵理论中求特征值的方法把它的特征值求出来， 自然就知道特征值的界了。 第一步，图日的邻接矩阵为： a = a ( h 、= o1 1o 01 1o 11 0 o 01 lo 0l 1o 0 o 1l 1o l0 01 o1 o o o o 于是a 的特征值为： = 一2 0 0 0 0 ，1 2 4 = 0 ， 如= 一1 4 1 4 2 ，以= 1 4 1 4 2 ， , 2 3 = 一0 7 3 2 1 ，兄6 = 2 7 3 2 1 ， 所以图h 的邻接矩阵特征值的界为p ( h ) 五。 方法二：利用已有的关于图邻接矩阵特征值的上界公式( 2 7 ) 和( 2 8 ) 。 在图中，顶点数，z = 6 ，边数m = 8 ，顶点的度分别为：d 。= d 。= d 。= d 。= 3 ， d 。= d ，= 2 。于是我们先利用( 2 - 6 ) ，可得 朋) 型型堕生掣幽：3 再利用( 2 7 ) p ( h 垮( 叶凛聋g ) , d , a ，2 3 t 咋，v ，丘t uj 1 4 o o o o o 旯 ，ll o a 0 o o o 旯o o1l1l o o 允o o 叫 o a o o o o 五o o o 1 o f | 得 纠 可 一 ， ， 叽 旭 = l i 州叫 一舾 令步 二 第 观察发现，可以将图的顶点集划分为两个部分h 。和日：， 令v ( h 。) = 缸，b ，c ，d ) ，v ( h 2 ) = e ，f ) ，显然有h = h 1 飓。于是 a 1 = m a x d g ( u ) l u h 1 ) 2 3 ， a 2 = m a x d g ( “) l “h 2 ) 2 2 ， s = m a x d ，( “) lu 巧) 2 2 ， t = m a x d 玩( “) l “) 2 2 ， 可以得到p ( h ) = 1 + 4 3 2 7 3 2 1 。 接下来将三种计算方法的结果用图表表示出来。 表2 - 2 图方法一方法二方法三 ( 2 6 )( 2 7 )( 2 8 )( 2 1 0 ) h 2 7 3 2 1 3 332 7 3 2 1 观察表2 2 我们用三种方法求出的上界，第一种方法是直接把特征值求出来， 但是这种方法有局限性，当对阶数很大的图或抽象图求它们特征值的时候，选用 这种方法显然很复杂。而方法二和方法三都用图的不变量去估计特征值的上界， 计算相对要简单很多。通过比较方法二和方法三求出的上界，我们还发现选用方 法- - n 用( 2 1 0 ) 求出的上界要优于方法二。也就是说利用( 2 1 0 ) 得出的上界要优于 ( 2 6 ) ，( 2 7 ) 和( 2 8 ) 得出的上界。 当求形如g = g l g 2 这类图的邻接矩阵特征值的界的时候可以利用推论2 2 3 。 特别地，在g = g l g 2 这类图中，假如e = “f “l “f 坎g j ) ，“坎g 2 ) ) = 矽的时候， p ( g ) = m a x p ( 6 1 ) ，p ( 6 2 ) ) 。 电子科技大学硕士学位论文 下面来看看对于熟知的一些图如何运用推论2 2 3 。 如果图g 为半正则偶图，那么如何求g 谱半径呢? 在前面的已有结论中，由定理2 1 7 我们知道，p ( g ) ( h 嚣警g ) d ，d ，等号 成立当且仅当g 为正则图或者半正则偶图。所以我们在本题中直接可以得到半正 则偶图g 的谱半径p ( g ) = m a x d ，d ，= 4 d 。d ：，其中图g 中的任意一个顶点“， “，v ) ( g ) o o a ( u ) = d l 或d 2 。 下面利用推论2 2 3 来计算，图g 为半正则偶图，因此符合g = g 1 g 2 这类型 图，令y ( g ) = v ( g 1 ) uv ( g 2 ) ，对图g 有，d ( u ) = d l ，“g l ，d ( u ) = d 2 , u g 2 。于 是 l = m a x d g ( “) l “g 1 ) = d l ， 2 = m a x d g ( “) j “g 2 ) = d 2 ， s = m a ) 【p g ( “) l “巧) 2 0 ， ，= m a x dg l ( “) fu ) 2d 2 ， 用推论2 2 3 的公式( 2 1 0 ) ， 耶) ：型! 竺坦尝盟! ：堕型 ，、d 2 + 0 一d 2 + 4 ( o + d 2 一d 2 ) 2 + 4 d 2 ( d 1 0 ) p ( g ) = 二l t l 竺 = d l d 2 从计算结果可以得出，利用推论2 2 3 的公式( 2 1 0 ) 计算与我们用定理2 1 7 的 结论是一样的。 假设图日为半正则二部图，我们用推论2 2 3 来求其补图h 的邻接矩阵特征值 的上界。 对图h 的顶点集y 我们设为：v = ku 砭，其中v = ku ，l _ i = n ，1 l = n ：， 图h 的顶点的度为根据补图的定义我们可以得到h = k l k v ，图日的顶点的度 为对vu 巧，d ( “) = d 1 ，对v “圪，d ( “) = d 2 ，利用推论2 2 3 ， s = 吖_ 1 ，t = n l d 2 ，l = n l + n z d 1 1 ，2 = m + 2 一d 2 1 ，i ii 1 6 第二章图邻接矩阵特征值的界 则 衙a2+s-t+x罨(s+t-面a2)a+4t(a1-s) 廨n,+n2-2+巫x(n,雩-n2)2亚+4(n面,-d2)(n2-d,) 1 7 电子科技大学硕士学位论文 第三章图的ia pia c e 特征值的界 对图的特征值的研究除了邻接矩阵的特征值之外，图l a p l a c e 矩阵特征值的研 究也是现在图论研究的热点之一，这一章中我们对图l a p l a c e 矩阵特征值的上界进 行研究讨论。 3 1 图的l a p la o e 矩阵的上界的研究进展 最早研究图l a p l a c e 矩阵的是a n d e r s o n 和m o r l e y ，他们给出图的l a p l a c e 矩 阵特征值的上界。 定理3 1 1 【9 1 设g = ( k e ) 是n 阶图，则 五( g ) m a x d 。+ d ，：u v e ) 其中等式成立当且仅当g 是半正则二部图。 在不久后，李炯生和张晓东改进了a n d e r s o n 和m o r l e y 的定理3 1 1 。 定理3 1 2 对，z 阶图g ，有 2 ( g ) 2 + 4 (