（应用数学专业论文）图的谱理论(1).pdf

2 0 0 1 年l o 月 中国科学技术大学博士学位论文( 范益政 摘要 图的谱理论是图论与组合矩阵论的一个重要研究领域本文主要研究图的 邻接矩阵的谱和图的l a p l a c i a n 矩阵的谱，简称为图的邻接谱和图的l a p l a c l a n 谱 本文第一章首先介绍图谱理论的历史背景，其次介绍常用的概念和术语， 最后，介绍所要研究的问题，它们的进展，以及本文所取得的主要结果 第二章讨论有向简单图( 定向图) 一二部竞赛图的邻接谱给出了二部竞赛 图零特征值的代数重数集同时也给出了二部竞赛图具有最少个数的不同特 征值的充要条件最后，给出了一类具有完全不同特征值的二部竞赛图 第三章讨论简单图的l a p l a c i a n 谱若干问题，包括图的代数连通度极端性 质的刻画，图的l a p l a c i a n 谱与图的匹配数的关系，以及恰有一个或二个大于 2 的l a p l a c i a n 特征值的图的刻画在3 1 节，给出了图的代数连通度等于其点 连通度或边连通度的充要条件在3 2 节，证明了如下结论，对于不含完美匹 配的树来说，其匹配数是其小于2 的非零l a p l a c i a n 特征值个数的一个下界 的充要条件在4 2 节，证明了图在添加一条边后其l a p l a c i a n 谱发生整性变 化仅有以下二情形t 其一，有一处发生l a p l a c i a n 整性变化；其二，有两处发 生l a p l a c i a n 整性变化对于第一种情形，给出等价条件对于第二种情形， 给出一类图，使得其在添加一条边后图的l a p l a c i a n 谱恰有两处整性变化由 此，通过添加边，可以从已知的l a p l a c i a n 整性图构造新的l a p l a c i a n 整性图 此外，也给出了图在添加一个环后其l a p l a z i a n 谱发生整性变化的等价条件) 。， 2 0 0 1 年l o 月中国科学技术大学博士学位论文( 范益政 a b s t r a c t t i l es p e c t r a lt h e o r 3 ，o fg r a p h si sa l l i m p o r t a n tt o p i ci ng r a p ht h e o r 3 ra n dc o i n b i n a t o r i a li u a t r i xt h e o r y t h et h e s i sm a i n b d e a lw i t ht h es p e c tr ao ft h ea d j a c e n e 、 l l l a t l - i xa i l dl a p l a e i a nm a t r i xo fa g r a p h s i m p l yc a l l e dt h ea d j a c e n c ys p c e t i t l d ia n d l a p l a c i a ns p e c t r u mo fag r a p h i nc h a p t e r1 b e s i d e si n t r o d u c i u gab a c k g r o u n do ft h e s p e c t r a lt h e o r y o fg r a p h s a n ds o m ec o n c e p t sa n dn o t a t i o n s ，w em a i n l yd i s c u s st h et h er e s e a r c hp r o b l e m sa n d t h e i rd e v e l o p m e n t s ，a n dl i s tt h er e s u l t so b t a i n e di nt h ef o l l o w i n gc h a p t e r s i nc h a p t e r 2 ，w em a i n l yd i s c u s st h ea d j a c e n c ys p e c t r u m s o fb i p a ，t i l et o l t l 、1 1 1 e d t 8 t i l es e to fa l g e b r a i cm u l t i p l i c i t i e so fz e r oa sa ue i g e n v a l u eo fa b i p a r t i t et o u r m e n t i n a t r i xi so b t m n e d w ea l s oc h a r a c t e r i z eb i p a r t i t et o u r m e n tm a t r i c e sf o rw h i c ht i l e n u u l b e ro fd i s t i n c te i g e n v a l u e si ss m a l l e s s 1 1 1a d d i t i o n ，ac l a s so fb i p a r t i t et o u l n l e n t m a t r i c e sw i t ha l ld i s t i n c te i g e n v m u e si so b t a i n e d i l l c h a p t e r3 ，w ed i s c u s ss o m ep r o b l e m so nl a p l a c i a l ls p e c t r u mo fas i m p l e g m p h ，i n c l u d i n gt h ee x t r e m ep r o p e r t i e so ft h ea l g e b r a i cc o n n e c t i v i t y o fa g r a p h ， t h er e l a t i o nb e t w e e nt i l el a p l a c i a ns p e c t r u l na n dt i l e m a t c h i n gn u n l b e ro fag r a p h ， a n dt i l ec h a r a c t e r i z a t i o no fag r a p hw i t he x a c t l yo n eo rt w ol a p l a c i a ae i g e n v a l u e s g r e a t e rt h a nt w o i l l s e c t i o n3 1 w e g i v ee q u i v n e n tc o n d i t i o n sf o x t h ea l g e b r a i c c o n n e c t i v i t yo fag r a p he q u a lt o i t sv e r t e xc o n n e c t i v i t yo re d g ec o n n e c t i v i t 3 ，i n s e c t i o n3 2 ，w ep r o v et i l e f o l l o w i n gr e s u l t ：f o x a t r e ew i t h o u tp e r f e c t m a t c h i n g s ， t i l e m a t h c h i n gn u m b e ri s al o w e rb o u n df o rt h en u m b e ro fi t sn o n z e r ol a p l a c i a n e i g e n v a l u e ss m a l l e rt h a n 2 i ns e c t i o n3 3 ，w ec o m p l e t e l yd e t e r n f i n et i l eg r a p h sw i t h e x a c t l yo n eo rt w ol a p l a c i a ne i g e n v m u e sg r e a t e rt h a n2 i nc h a p t e r4 ，w ed i s c u s st h ep e r t u r b a t i o n so fa d j a c e n c ys p e c t r u ma 1 1 dl a p l a c i a n s p e c t r u mo fag e n e r a lg r a p ha f t e ra d d i n ga l le d g eo r al o o p w ei n t r o d u c ean e w c o u c e p t s p e c t r a li n t e g r a lv a r i a t i o n s i us e c t i o n4 1 e q u i v a l e n tc o n d i t i o n sf o x t i l e a d j a c e n c ys p e c t r u mo fag r a p h w i t hm i n i m a l i n t e g r a lv a r i a t i o n so c c u r i n g a f t e ra d d i n g a ne d g eo ral o o pa r ee s t a b l i s h e d i ns e c t i o n4 2 w es t u d ya l lt i l ec a s e s0 1 1l a p l a c i a n s p e c t r a li n t e g r a l v a r i a t i o n so fag r a p ha f t e ra d d i n ga l le d g e t h e r ea r eo n l yt w o c a s e sh a p p e n e da sf o l l o w s ：t i l el a p l a c i a ns p e c t r a li n t e g r a lv a r i a t i o n so c c u ro l n yi n 2 0 0 1 年l o 月中国科学技术大学博士学位论文( 范益政) o l l e p l a c e ：t h el a p l a c i a ns p e c t r a li n t e g r a lv a r i a t i o n so c c u ri n t w op l a c e s f o rt h e f ir s tc a s e ，w eg i v ea l le q u i x ，a l e n tc o n d i t i o n ；a n df o rt i l es e c o n dc a s e ，w eg i v eac l a s s o f g r a p h ss u c ht h a t i t s l a p l a c i a ns p e c t r a li n t e g r a l v a r i a t i o n so c c u ri nt w op l a c e s a f t e ra d d i n gc e r t a i ne d g e f r o l no u rr e s u l t s an e wl a p l a c i a ni n t e g r a l g r a p hc a l l b ec o n s t r u c t e df r o mk n o w nl a p l a c l a ni n t e g r a lg r a p l l sa f t e ra d d i n gc e r t a i ne d g e i l l a d d i t i o n w ea l s og i x ，ea l l e q u i x a l e n tc o n d i t i o nf o rag r a l ) 1 1w i t hl a p l a c i a ns p e c t r a l i n t e g r a lv a r i a t i o n so c c u r r i n ga f t e ra d d i n gal o o p 2 0 0 1 年1 0 月 中国科学技术大学博士学位论文( 范益政) 第一章绪论 本章首先简要介绍图谱理论的背景其次介绍有关概念和术语最后，介 绍所研究的问题，它们的进展，以及本文所取得的主要结果 1 1图谱理论的简要背景 图的谱理论主要涉及图的邻接( 矩阵的) 谱和图的l a p l a c i a u ( 矩阵) 的谱， 是图论( 特别是代数图论) 和组合矩阵论共同关注的一个重要课题其研究的 主要途径是，通过圈的矩阵( 邻接矩阵或l a p l a c i a n 矩阵) 表示，建立图的拓 扑结构( 特别是图的各种不变量) 和图的矩阵表示的置换相似不变量之间的联 系，通过矩阵论，特别是非负矩阵理论和对称矩阵理论，和组合矩阵论中的经 典结论用于图的拓扑结构的研究，同时也将图论的经典结论用于非负矩阵理 论和组合矩阵论，以推动后者的理论研究 图的邻接谱的研究最早源于量子化学研究领域由e h i i c k e lf 5 2 ( 1 9 3 1 年) 引进的对非饱和碳氢化合物的一种近似处理产生了对应分子的图论模型，其 中图的特征值被用来表示特定电子的能量级很多年以后，h f i c k e l 模型与图 谱的数学理论之间的联系在 4 2 和 1 9 中才被认识到，并且从此被众多的研 究者，化学家和数学家广泛的开发利用而最早明确提出研究图的邻接谱的 是h s a c h s 7 7 和a j h o f f m a n 4 9 ( 1 9 6 9 年) ，尽管它已经在l c o l l a t z 和u s i n o g o w i t z 2 0 ( 1 9 5 7 年) 的一篇更早的论文就已提及到了1 9 7 1 年，d c v e t k m + i d 15 在他的博士论文中引用了8 3 篇1 9 7 0 年以前的文献这些文献都是涉及到 图的邻接矩阵的特征值十年后，几乎所有的涉及到图的邻接谱的结论都被收 集到d c v e t k o v i d ，m d o o b 和h s a c h s 合著的s p e c t r a o fg r a p h s 1 7 1 它的 参考文献包含了1 9 6 0 年到1 9 7 8 年之间5 6 4 篇文章作为该书的一个补充，另一 本由d c v e t k o v i d ，m d o o b ，i g u t m a n 和a t o r g a g e vf 1 6 】合著r e c e n tr e s u l t s i 1 1t h et 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 0 篇的来自于数学和化学的 文献同时，该书还收录了来自其他领域，例如，物理，机械工程，地理，社 会科学等方面的文献尽管有的文章包含微小的结论，有的是对已知结论的 再发现，但是如此之多的文献说明了图的邻接谱理论之迅速成长关于图的 邻接谱理论最近的发展，1 9 9 5 年出版的专著s p e c t r a o fg r a p h s 的第三版 的附录有详尽的叙述1 9 9 7 年，d c v e t k o v i d ，p r o w l i n s o n 和s s i m i d 的合 2 0 0 1 年1 0 月第一章绪论 2 著e i g e n s p a c e so fg r a p h s 1 8 重点阐述图的邻接谱理论中特征空间的重要 作用此外，n b i g g s 的a l g e b r a i cg l a p ht h e r o y 【8 以及( d g o d s i l 的 a l g e b r a i cc o r a b i l _ l a t o r i e s 3 6 对图的邻接谱也作了详尽的叙述 图的l a p l a c i a - 、谱是图谱理论中的另一研究领域与图的邻接谱的研究相 比，尽管早在1 8 4 7 年g k i r c h h o f f 已将图的l a p l a c i a n 谱用于电流网络的研究 并给出了著名的矩阵一树定理 5 6 图的l a p l a c i a n 谱的研究受到人们普遍关 注则是近几十年的事情在七十年代初期，通过图的l a p l a c i a n 矩阵在一些文 献 1 ，2 9 中的出现，人们才逐渐地认识到它但是，从某种意义上说，图的 l a p l a c i a n 谱不但比图的邻接谱包含的信息多，且更加自然和重要( b m o h a r 语 _ l 】) 综述文章r m e r r i s 6 s ，bm o h a r 7 1 ，7 2 ，以及专著f a l lr k c h u n g 1 4 详尽叙述了l a p l a c i a n 谱研究中的若干专题以及应用 定理1 1 1 ( 矩阵一树定理) 设为n 阶简单图g 的l a p l a c i a n 矩阵， l ( i l j ) 为l 删除第i 行和第j 列后的子矩阵则对任意的f ，j = l ，2 ，1 1 ， ( 一1 ) md e t l ( i l j ) 等于g 的生成树数 故l a p l a c i a n 矩阵又称为i ( i r c h h o f f 矩阵或传导( a d n l i t t a n c e = c o n d u c t i x i t 3 ，) 矩阵根据它在其它文献中的独立发现，l a p l a c i a n 矩阵又被称为信息( i l f f o r m a t i o n ) 矩阵 1 3 】，z i m l n 矩阵 3 2 ，r o u s e z i i m n 矩阵 8 1 ，连通性( c o n n e c t n i t ) r ) 矩阵 2 2 ，点- 点( v e r t e x v e r t e x ) 关联矩阵 8 2 在这些名词中，”l a p l a c i a n 矩 阵”或许是理由最充分的 考虑下面的偏微分方程； 笔+ 笔+ a 。：o ， ( 0 2 2 。p 2 。 、1 1 ( 或：+ a ：= o ；a = 筘+ 貉即为l a p l a c l a n 算子) ，其中，未知函数：= ：( ) 满足边界条件，：( t ，y ) = 0 ，) r ，f 为。一平面上的一条简单封闭曲线 方程( 1 1 1 ) 只有对a 所取的无穷可数序列a 。a 。a 。茎才有解 a 所取得这些值称为方程( 1 11 ) 的特征值该特征值序列称为方程( 1 1 1 ) 的 谱，而对每个特征值，都对应方程( 1 1 1 ) 的一个解，称为它的特征函数 在求：的近似解中，一般只考虑。一平面上的一个离散的点集它们构 成一个正则的网格( 正方形，三角形，六边形) 在正方形网格( 图1 1 1 ) 的情形 下，设；l = z ( x + h ，y ) ，：2 = z ( x h ，) ，；3 = ：( 。，+ h ) ，知= ：( 。，一h ) 通过取 微分的近似值，l a p l a c l a n 算子在点( 。，y ) 的值为 去( ：l + ：_ 2 + ：3 十铂一4 ：) ； 2 0 0 1 年l o 月第一章绪论3 而方程( 1 1 1 ) 化为 1 9 6 6 年，mk a c 5 3 提出这样一个问题：如果一个对应膜振动的偏微分 方程( 1 1 1 ) 的谱已经知道，如何去决定膜的形状( 即曲线r ) mk a c 赋予该文 章的名称为tc a n eh 6 a r 7 et h a p eo y “d7 7 因为鼓膜所产生的音调的频 率完全与方程( 1 1 1 ) 的特征值相关，故听膜振动的声音，其实就是听“谱” m e f i s h e rf 3 1 考虑i ( a c 问题的离散的模拟情形在他的模型里，膜是由原子 的集合构成在平衡状态下，所有原子都位于平面上的一个正则的网格图的顶 点上每个原子通过弹力作用于相邻的原子假设所有原子的质量相等，相邻 两原子之间的弹力也相等由此，膜对应平面网格图1 1 1 的一部分 f i s h e r 也考虑了人能否听出鼓的形状的问题自然地，这个问题可以简化为图的谱是 否能唯一地决定图的结构的问题，即同谱图问题 图1 1 1 如果去掉假设“膜是对应平面网格图的一部分”，一个纯粹意义上的鼓的 “组合膜”就是一个图g = ( k e ) ，v 中每个顶点的“质量”以及e 每条边的 “长度，都是1 由此，上述微分方程即化为如下矩阵形式 针 ( 勺咱) = ( a 一纰。+ 勺= o ，i = 1 ，2 其中，d 。为顶点的度利用图g 的度对角矩阵d 和邻接矩阵a 上式可化 2 0 0 1 年1 0 月第一章绪论 为矩阵形式 a ：一口：+ 4 z = a ：一：= 0 其中，矩阵l = d a 即为图g 的l a p l a c i a n 矩阵它是l a p l a c i a l l 算子的 在离散情形下的矩阵模拟 因此，偏微分方程( 1 1 1 ) 的近似解问题，特别是膜振动问题，实际上就 是l c o l l a t z 和u s i n o g o w i t z 的文章 2 0 的出发点而振动的有限膜问题的考 虑，可以真正的说明整个图谱理论的一个从实际出发，有着实际目的出发点 在图论研究中，图同构问题很早就被提出来，并且一直困扰着众多研究 者在研究它时，人们试图寻找图的全系不变量( 图的某些不变量的集合曲称 为图的一个全系不变量，如果对任意二图g ，h ，西( g ) = 咖( h ) 当且仅当g 和 h 同构，换言之，图的全系不变量在同构意义下唯一决定图) 早期，研究者 从图的邻接矩阵入手，并猜想；图的邻接谱是图的一个全系不变量显然，两 个图同构当且仅当它们的邻接矩阵置换相似因此，图的邻接谱是图的一个不 变量如果对上述猜想的回答是肯定的，那么将有一种多项式算法来区分两个 图是否同构，因而就解决了图同构问题事实上，在【2 0 中，l c o l l a t z 和u s i n o g o w i t z 就已经给出两个具有不同度序列的八个顶点的同谱树一个最富有 戏剧性的结论就是a j s c h w e n k 的“几乎所有得树都是同谱的” 7 8 图的 l a p l a c i a n 谱也不是图的一个全系不变量图的l a p l a c i a n 同谱问题也有了较深 入的研究( 参见 6 5 ) r m e r r i s 6 6 构造了两个具有不同度序列的1 1 个顶点 的l a p l a c i a n 同谱图 正如大家所共知，图同构问题到目前依然没有解决，且它的算法的复杂度 也是未知的图的谱不能唯一决定图，即不能构成图的全系不变量虽然全系 不变量确实存在 1 8 ，s e c t i o n1 4 i 但到目前为止，已知的一些寻找全系不变量 的算法都是指数的( 参考 7 6 3 ) 能够以多项式次数计算的全系不变量没有被 发现关于这个问题的悲观思想已经在文献中表述了 7 6 】尽管如此，我们仍 然希望藉以图的一些代数不变量( 图的邻接谱与图的l a p l a c i a , n 谱) ，利用特征 值技巧，来刻画图的结构性质特征值的方法在图论和组合论上的应用，已经 有很长的历史例如，在二十世纪六十年代末期，以特征值来表示着色数的界 就由h s w i l f 8 3 和a j h o f f m a n 4 8 】给出关于特征值一个重要的应用是 l l o v g s z 在1 9 7 9 年引进的口函数 6 0 ，利用该函数，他解决了存在已久的关 于5 一圈的s h a n n o n 容量问题0 函数提供了仅有的已知方法，以多项式次数 来计算完美图的着色数另一个重要的结论是n a l o n 和v d m i l m a n 【2 在 1 9 8 5 年利用特征值来构造超浓缩图和扩展图他们的工作激发了随机正则图 2 0 0 1 年1 0 月第一章绪论 特征值的研究图的等周性质和特征值在m a r k o ：t 链的快速收敛，有效的近似 算法，随机化和非随机化的算法，建立有效的通讯网络和并行计算网络等方面 发挥了重要的作用 7 1 此外，图的一些重要的不变量，如图的二部宽( b i p a r t i t ew i d t h ) ，最大割 ( 1 ，1 a x c u t ) ，等周数等，除了反映图的一些结构性质外，而且还有广泛的应用然 而，它们计算的复杂度属于n p h a r d 3 5 ，p2 1 ， 7 3 图的( 邻接矩阵或l a p l a c i a n 矩阵) 特征值是可以通过多项式渐进球根理论求得，而该理论也已比较成熟和 完善因而，建立图的代数不变量( 图的谱) 与图本身的不变量之间的联系， 很有必要 除了上述介绍图谱理论的重要作用，在量子化学中，给定的非饱和碳氢化 合物的结构是用图来表示分子中电子的能量级实际上就是对应图的邻接矩 阵的特征值：分子的稳定性以及相关的化学性质与图的谱和对应的特征向量 有着紧密的联系最近i g u n m a n 等人 4 3 ，4 4 ，4 5 发现饱和的碳氢化合物( 即 烷烃) 的光电子谱与潜在的分子图的l a p l a c i a n 特征值也存在着联系而在数 学物理中，l a p l a c i a n 微分算子是一个基本的微分算子涉及此算子的d i r i c h l e t 问题的离散化即产生了图的l a p l a c i a n 矩阵和图的l a p l a c i a n 谱( 见前面讨论) 另外，图论和组合论的许多定理的证明中，图的谱也经常出现，尽管在定理的 表述中并不明确地提到图的谱因此，图的谱在此成为一个重要的工具，以致 它的使用被称为谱技巧以上这些事实，以及一些其他事实，刺激了图谱与图 结构性质的研究 在图谱理论的研究中，矩阵论，线性代数以及置换群理论被用来分析图 的邻接谱代数方法在处理正则图( 特别是强正则图) 和无向图时是非常有力 的工具作为一个例子，图的l a p l a c i a n 谱中的次小特征值被称为图的叶数 连通度”关于图谱理论代数方面，已经有大量的的文献它们被引用在一些 综述和专著中，如： nb i g g s ( 8 ，d c v e t k o v i d ，m d o o b 和h s a c h s 【1 7 ，d ( 、r e t k o v i d p r o w l i n s o n 和s s i m i d 1 8 在过去的十年里，许多关于图的谱理论的研究常常含有几何的特色例 如，扩展图的显性构造( l u b o t z k y p h i l i p s s a r n a k 【6 1 和m a r g u l i s 【6 2 ) ，即是以 图的特征值和等周性质为基础c h e e g e r 不等式 1 2 的离散情形下的模拟已 经被广泛地应用到随机步与快速混和m a r k o v 链的研究上 7 9 图的特征值的 研究实现了它和数学的其他领域的不断丰富的联系一个很重要的进展就是 谱图论与微分几何的相互作用谱流形几何与谱图论之间存在一个有趣的模 拟谱几何的概念及方法给图的特征值的研究提供了有用的工具和重要的视 2 0 0 1 年1 0 月第一章绪论 6 角，反过来，图的特征值的研究也给谱几何提供了新的方向和结论f a - 。r i i c h u n g 【t 4 详尽叙述了图谱几何方面的理论 1 2 概念与记号 集合s 称为重集，如果s 中的元素允许相同记m s ( e ) 为元素e s 的重 数若e s 的重数为m ，记为e ( m ) s 若e s ，用 z s ( e ) = 0 或e ( o s 来表 示简记( 1 ) s 为ees 集合s 的基数，记为，即为s 中所有元素的重数 之和；也称s 为蚓元重集定义s lcs z ，若对任意的e ( m - s l ，则必存在整数 d 1 2 1 1 ，使得e ( m 2 ) s 2 s lu s 2 = e ( m ) ：m = 竹t s 】( e ) + m 岛( e ) o ) ，s ln s 2 = c l ： ，= m i n ( m s i ( e ) ，7 7 z s 2 ( e ) ) o ) ，s 5 l = e ( 叫：m = m s ( e ) 一m s l ( e ) o ) 易见，通常意义下的集合，是重集的特殊情形它的每个元素的重数都是1 设g = ( k e ) 为n 阶一般( 无向) 图，其顶点集为v = v ( g ) = r l ，一。) 其边集e = e ( c ) 为y 的二元重集构成的重集为区别起见，称e 中元素似u ) 为g 的环；而称e 中元素 ”川) ( u ) 为g 的边因此，g 允许有重环和重 边如果g 无环但允许有重边，则称g 为重图如果g 无环且无重边，则称 “为简单图 类似地，可定义一般有向图d = ( ke ) ( 此时弧集e 为1r 7 的元素的有序对 构成的重集) ，以及重( 简单) 有向图f 中的元素称为环或弧( 当然环不必考 虑其方向) 因此，一个简单有向图是指无环和无重弧的有向图给简单图每 一条边赋予任意的一个方向，得到定向图，即无对称弧的一类简单有向图 设g = ( e e ) 为一般图 。ev 的邻域定义为重集n a ( ”) = “：”) e e ) 若n g ( v ) 除了可能包含”之外，不含其它顶点，则称为u 为g 的孤立点 r 的度d c ( ) 是指g 中与”关联边( 包括环) 数g 的最大度与最小度分别记 为g 和如在不相混淆的情形下，上述分别简记为n ( v ) ，d ( ”) ，6 图g 称 为正则的，如果它所有顶点的度都相同设g 为n 阶简单图，其度序列是指 g 的所有顶点的度构成的序列，约定其排列为d t ( g ) d 2 ( g ) d 。( g ) g 称为门槛( 或度极大) 图，如果它的度序列在优超下是极大的 下面介绍有关简单图的一些基本定义和记号，其余见 6 或【9 】 k ，g ，b 和r 分别是r 个顶点的完全图，圈，路，和有r 个孤立点的 简单图对于路p ，用形式只，= u 1 v 2 弭表示只的边为 u 1 ，) ， n ) ， ， ，l ，蜥) 2 0 0 1 年t 0 月第一章绪论 设g = ( 1 i e ) 为简单图g 的补图记为g c 记t ( g ) 为g 的生成树数g 中由不相邻边构成的任一个集合称为g 的一个匹配g 的匹配数是指g 的 所有匹配的最大基数，记为肛( g ) 如果g 的一个匹配的基数为，。( g ) ，则称该 匹配为g 的一个极大匹配，记为m ( g ) g 的一个极大匹配称为完美的，如果 该匹配里的边关联g 的所有顶点g 的某两点u ”的距离是指连接“与u 的 最短路的长度 g 的直径即为g 的所有两点间的最长距离顶点r 1 称为 ( ? 的悬挂点，如果d o ( g ) = 1 若顶点“1 ，与一个悬挂点相邻，则称c ，为( ? 的准悬挂点记p ( g ) ，q ( g ) 分别为g 的悬挂点与准悬挂点的个数设uci 记g u 为由u 诱导的子图如果e 是g 的一条边，用g e 记g 删去边e 后 所得到的图更一般地，用g 一 e 1 ，e i ) 记g 删去边e l ，e 后所得到的 图设e v v ，用g 十e 来记g 添加e 后所得到的简单( 或一般) 图( e 也可 属于g ) 类似地，用g + eh e k ) 记g 添加e 。e 后所得到的简单( 或 一般) 图本文中，该记号也用于一般图g 设u v ( g ) ，g 一”记图g 删去顶 点r 以及所有与”关联的边后所得到的图更一般的，设u 1 ，( g ) g u 即 为由1 ( g ) c 7 诱导的子图图g 的线图x ( g ) 定义为如下，x ( g ) 的顶点为 g 边，y ( g ) 的两个顶点相邻当且仅当g 的相对应的两条边相邻 设g = ( k e ) 为连通的简单图若对某个”ev ，g 一”不连通，则称u 为 g 的一个割点g 的一个点割集是指、? 的一个子集，使得它的删除导致g 不连通类似地，e e 称为g 的割边，若g e 不连通fce 称为g 的 一个边割集，若g f 不连通g 的点连通度u ( g ) ，边连通度e ( g ) 分别定义 为g 的点割集与边割集的最小基数g 中基数为v ( a ) 的点割集，和基数为 e ( g ) 的边割集分别称为g 的极小点割集和极小边割集设s 是g 的一个极小 点割集，则g 一，s 非连通称g s 的连通分支，c f 小g n 2 ，为g 在 ，的连通分支 设g 1 = ( ，e 1 ) ，g 2 = ( k ，f 2 ) 分别为具有r 个顶点和8 个顶点的不相交 简单图它们的并图为g l + g 2 = ( ku 1 f 2 ，e 1ue 2 ) ，它们的联图为g lvg 2 = ( q + 嘭) c ，即在图g 1 + g 2 中添加由g 1 中每个顶点到g 2 中每个顶点的边所 得一个简单图称为可分的，如果它能由孤立点经过有限次的并和联得到 6 6 】 记k ，= 肌v 肌为r 8 的二部完全图k 1 ，。称为星图，8 3 更一般的， k n ，。= r ，v 虬：v v n h 记n ，2 ”的k 一部完全图完全图的 定向图称为竞赛图，k 部完全图的定向图称为k 一部竞赛图 设g = ( 1 ，e ) 为n 阶一般图，其中，v = ，u 。) ，e = 钆c 2 ，。) 为m 元重集图g 的关联矩阵b = b i7 定义如下：如果顶点u ，在边( 环) c t 2 0 0 1 年1 0 月第一章绪论 8 上，记b i j = 1 ；否则，记b i j = 0 易见，b 是m ， ( 0 ，1 ) 一矩阵图g 的定 向关联矩阵c = c 。 定义如下：给图g 一个定向( 除了环) ，记c i i = 1 ，如果 顶点t j 是边e ；起点；记c i ，= 一l ，如果顶点v ，是边e 。终点记c l j = 1 ，如果 顶点和环e 。关联其他的情况，记c 。，= 0 易见，c 是，：( o ，1 ，一1 ) 一 矩阵称d = d ( g ) = d i a g d ( t ，1 ) ，d ( v 2 ) ，d ( ) ) 为图g 的度对角矩阵记 “，= m e ( m v j ) 图g 的邻接矩阵即为”阶矩阵4 = a ( g ) = a i 门易见， 4 ( g ) 为对称矩阵容易验证：c t c 。= d ( g ) 一4 ( g 7 ) 三( g ) ，其中，g 为g 删 去所有环之后的重图上述矩阵l ( g ) 称为图g 的l a p l a c i a l l 矩阵( 1 4 ， 3 3 ) 对于n 阶有向图d = ( ve ) 记m ，= ，( ( v j ) 图d 的邻接矩阵为n 阶矩阵4 = a ( d ) = a i j 此时，a ( d ) 不一定对称称竞赛图的邻接矩阵为竞 赛矩阵，一部竞赛图的邻接矩阵为一部竞赛矩阵记工，0 。分别为，s 的全1 全0 矩阵简记j r ，0 。为工，0 “j r ，为“通过对二部竞赛图d 顶 点的一个重新编号，得到如下形式的二部竞赛矩阵 即，= h 甜 z 其中b c 为( 0 ，1 ) 矩阵满足b + c 口= j n 。：( m j 1 2 1 ) 对应于零对角块 o 。o 。：的顶点集分别记为h = u ，2 ，u 。) ，和k = h + ，。+ 2 ) 若( 1 2 1 ) 中的矩阵a ( d ) 不可约，则n l n 2 2 记具有形式( 1 2 1 ) 的不可 约二部竞赛矩阵的集合为b 。( j ? l 毗2 ) 记e 。为正整数f 的集合， 使得对每个t ，都存在。：里的一个二部竞赛矩阵，其零特征值的代数重数 为f 称e 。为二部竞赛矩阵的零特征值的代数重数集在第二章中，如果 h 矗。：，总假设h 就是矩阵( 1 2 1 ) 本文用乳( g ) ，既( g ) 分别记图g 的邻接谱和l a p l a c i a n 谱用p ( g ) 记一 般( 有向】图g 的邻接谱的谱半径( 或指数) ，即邻接矩阵a ( g ) 的最大模特征 值设，为实轴上一个区间，用m a ( i ) 记一般图g 的l a p l a c i a n 谱中属于， 的特征值的个数( 包括重数) 特别地，若，= a ) ，则m a ( i ) 为a 作为g 的 l a l ) l a c i a n 特征值的重数 根据上述定义可知，一般( 有向) 图的邻接( 或l a p l a c i a n ) 矩阵都是整数矩 阵一般图g 称为邻接( l a p l a c i a n ) 整性的，如果g 的邻接( l a p l a c i a a l ) 谱由整 数构成上述定义是将f h a r a r y 和a j s c h w e n k ( 5 1 ， 5 0 ) 关于简单图的邻接 谱，r m e r r i s 6 6 关于简单图的l a p l a c i a n 谱的整性定义的范围扩展到一般图 2 0 0 1 年1 0 月第一章绪论 9 上设g 为一般图，s ( g ) 为s ( g ) 或s l ( g ) 记2 1 = s ( g ) 1 3 s ( g + e ) 将集合 s ( g + e ) t 和s ( g ) k t 的元素按升序排列如果s ( g + e ) 归和s ( g ) k t 在相同 位置上的差值为整数，称图g 添加边( 或环) e 后邻接( 或l a , p l a c i a a ) 谱变化是 整性的，或称g 添加边( 或环) e 后发生邻接( 或l a p l a c b n ) 谱整性变化为方 便起见，上述定义简称为g 添加边( 或环) e 后发生a s i v ( a d j a c e n c ys p e c t r a l i n t e g r a lv a r i a t i o n s ) 或l s i v ( l a p l a c i a ns p e c t r a li n t e g r a lv a r i a t i o n s ) 看g 添加 边( 或环) e 发生a s i v ( l s i v ) ，且1 s ( g ) v l = 1 ，则称g 添加边( 或环) e 发生处a s i v ( l s i v ) 如果g 添加边( 或环) e 发生k 处a s i v ( l s i v ) 且已取到最小值，则称g 添加边( 或环) e 发生极小a s i v ( l s i v ) 设a 为n 阶实方阵a 的谱和谱半径分别记为s ( a ) 和p ( a ) a 的迹记 为t r ( a ) 记a 例为a 的行指标集为o ，列指标集为卢的的子矩阵4 称为 可约，如果存在某个付阶置换矩阵p ，使得 p t a p ：f b e l 0d j 其中，b ，c 为方阵否则，a 称为不可约约定，1 阶矩阵总是不可约的 设。冗n 为n 维的实向量记。为。的第i 个分量，i = 1 ，2 ，n 向 量z 称为f a r i a 向量( 6 6 ) ，如果。中仅有两个非零元，且分别为1 ，一1 设g 为 n 阶简单图，。= ( x 1 ，x 2 ，。n ) c “依照 3 0 】，称。给g 顶点的一个赋值， 意味着，对于g 的每个顶点陇，伴随着数。4 ，即为v i 的值，记为z ( v i ) = 。另 外，记( 竹) = l ，2 ，”) ，h 为不大于r 的最大整数，m 为不小于r 的最小 整数，其中r 为实数 矩阵或向量a 称为非负的，如果它的所有元索