（应用数学专业论文）代数图论和ramsey理论中若干问题的研究.pdf

同济大学博士学位论文 摘要 在图论中，为了研究图的性质，人们引进了各种各样的矩阵，诸如图的邻接矩 阵，关联矩阵，距离矩阵，拉普拉斯矩阵等等，这些矩阵与图都有着自然的联系， 代数图论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性 质反映出来，这里所指的矩阵的代数性质，主要指矩阵的特征值 在上面所提到的矩阵中，最重要的有两个：图的拉普拉斯矩阵和邻接矩阵 图的拉普拉斯矩阵的特征值和邻接矩阵的特征值都是图的在同构下的不变量， 图的邻接矩阵及其特征值是代数图论的一个基本的研究课题在过去的几十年 中，人们对图的邻接矩阵的特征值已经进行了大量的研究( 见文献f 1 一 3 9 1 ， 4 6 1 一f 6 4 1 ，f 7 0 卜8 7 ，f 1 0 1 一 1 0 5 ) 和图的邻接矩阵相比，由于在拉普拉斯矩阵中含有图 的顶点度的信息，因此图的拉普拉斯矩阵的特征值与图的很多不变量有着更加 密切的联系正如m o h a r 7 9 1 所说：图的拉普拉斯矩阵的特征值更能反映它的图 论性质，所以，对图的拉普拉斯矩阵的特征值的研究越来越受到人们的广泛关注 人们对图的拉普拉斯矩阵也经进行了一些的研究( 见文献f 9 】，f 1 6 ，f 1 7 1 ，f 4 0 一f 4 5 1 ， 【6 6 - 9 4 ， 9 9 一【1 0 8 】) 人们对拉普拉斯矩阵的研究，可以追溯到1 6 0 多年以前，对于邻接矩阵的研 究时间就更长了，r ，a m s e y 理论相对来说就是一个年轻的图论分支了可参见 文献f 1 0 9 一 1 1 5 我们知道在组合数学中有这样两个有趣的断言：一，在六个人 的派对中，总有三个人他们互相都认识或者互相都不认识二，将无限集上 的完全图中的边用红蓝两种颜色着色，那么一定存在一个无限集mc ，使得 m 中的所有的边着相同的颜色上面这两个断言都是r a m s e y 在1 9 3 0 年发表 的一个定理的两种特殊情形，这个定理后来从各方面被发展，从而形成了日后的 r a m s e y 理论r a m s e y 理论是一个广博而丰富的组合分支，很多其他数学分支中 的技巧都被用到了这一理论的研究中，并且它的研究结果不仅对图论和组合数学 来说非常重要，对集合论、逻辑、分析、代数和几何理论来说也是相当重要的 本文的研究主要分如下三个方面：一是对双圈图的邻接谱半径的研究，二是 对双圈图的拉普拉斯谱半径的研究，三是对r a m s e y 理论中t u r i n 数的研究 图的邻接谱半径是指图的邻接矩阵的最大特征值，在本文的第二章中，根据 邻接谱半径的定义证明了广义夺邻定理( 定理2 2 1 ) ，并利用此定理以及嫁接运 算，收缩内部路中边等技巧，研究了阶数为n 的双圈图的邻接谱半径，给出了具 有最大邻接谱半径的前三个双圈图以及它们对应的谱半径 图的拉普拉斯谱半径是指图的拉普拉斯矩阵的最大特征值，在本文的第三章 中，我们利用拉普拉斯特征多项式，研究了具有固定阶数的双圈图的拉普拉斯谱 半径且给出了具有最大拉普拉斯谱半径的前四个双圈图以及它们对应的谱半径 对于t u r i n 数的研究是r a m s e y 理论研究的重要部分之一在本文的第四章 中，我们利用有限域上的线性方程组和有限域上的范德蒙矩阵以及“临界零和序 列”等代数方法证明了：当m 3 时，对任意一个满足2 5 ，4 2 2 c h ( 局) ( 其 中c ( b ) 是有限域b 的特征) 的自然数z ，过w e n g e r 构造的图( g ) 中的任 一点都有长为2 z 的偶圈，从而说明了由图( g ) 不可能得到e x ( n ；q m ) ( m 2 ，3 ，5 ) 的下界 i v 摘要 关键词：图；拉普拉斯矩阵；邻接矩阵；拉普拉斯特征值；特征多项式；特征向量； 拉普拉斯谱半径；上( 下) 界；双圈图；加边运算；嫁接运算；剖分运算；有限域； 向量空间：线性方程组 v 同济大学博士学位论文 a b s t r a c t t h e r ea r ev a r i o u sm a t r i c e st h a ta r en a t u r a l l ya s s o c i a t e dw i t hag r a p h ，s u c h a st h ea d ja c e n c ym a t r i x ，t h ei n c i d e n c em a t r i x ，t h ed i s t a n c em a t r i xa n dt h el a p l a - c i a nm a t r i x o n eo ft h em a i np r o b l e m so fa l g e b r a i cg r a p ht h e o r yi st od e t e r m i n e p r e c i s e l yh o w ，o rw h e t h e r ，p r o p e r t i e so fg r a p h sa r er e f l e c t e di nt h ea l g e b r a i cp r o p e r t i e s ( e s p e c i a l l ye i g e n v a l u e s ) o fs u c hm a t r i c e s a m o n gt h ea b o v em e n t i o n e d m a t r i c e so fg r a p h s ，t h em o s ti m p o r t a n tt w oa r e t h ea d j a c e n c ym a t r i xa n d t h el a p l a c i a nm a t r i xo fg r a p h s b o t ht h ee i g e n v a l u e so f t h el a p l a c i a nm a t r i xa n dt h ea d ja c e n c ym a t r i xa r et h ei n v a r i a n t so fg r a p h su n d e r i s o m o r p h i s m t h el a t t e ri so n eo ft h ee l e m e n t a r yd i r e c t i o no fa l g e b r a i cg r a p h t h e o r y w h i c hw a sm u c hm o r ei n v e s t i g a t e di nt h ep a s tt h a nt h ee i g e n v a l u e so ft h e l a p l a c i a nm a t r i x t h er e a d e ri sr e f e r r e dt ot h em o n o g r a p h s 1 卜【3 9 ) 4 6 】_ 6 4 】， 7 0 卜 87 ， 1 0 1 一 1 0 5 1 ) h o w e v e r ，s i n c et h ee i g e n v a l u e so ft h el a p l a c i a nm a t r i x h a v eac l o s er e l a t i o nt on u m e r o u sg r a p hi n v a r i a n t s ( s e e 【7 9la n dt h er e f e r e n c e s t h e r e i n ) ，i ti sj u s t a sm o h a r 7 9 1s a i dt h a t ：“t h e ya r em o r en a t u r a la n dm o r e i m p o r t a n tt h a nt 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 x ”t h er e a d e ri sr e f e ：r r e dt o t h em o n o g r a p h ss u c ha 8 9 】 1 6 ， 17 】， 4 0 - 4 5 ， 6 6 一 9 4 ， 9 9 一 1 0 8 t h er e s e a r c ho fl a p l a c i a nm a t r i xa n da d j a c e n tm a t r i xa l lh a v eal o n gh i s t o r y , w h i l er a m s e yt h e o r yi say o u n gb r a n c ho fg r a p ht h e o r y ( 1 0 9 一 11 5 1 ) a sw e k n o w n ，t h e r ea r et w oi n t e r e s t i n ga s s e r t i o n si nc o m b i n a t o r i c s 壬i nap a r t yo fs i x p e o p l et h e r ei sa l w a y sag r o u po ft h r e ew h oe i t h e ra l lk n o we a c ho t h e ro ra r e a 1 1s t r a n g e r st oe a c ho t h e r i ft h ee d g e so ft h ec o m p l e t eg r a p ho ni n f i n i t es e 七 a r ec o l o r e dr e do rb l u et h e nf o rs o m ei n f i n i t es e tmcna l lt h ee d g e sj o i n i n g v e r t i c e so fmg e tt h es a m ec o l o r b o t ho ft h e s ea s s e r t i o n sa r es p e c i a lc a s e so fa t h e o r e mp u b l i s h e db yr a m s e yi n1 9 3 0 t h eo r i g i n a lt h e o r e m so fr a m s e yh a v e b e e ne x t e n d e di nm a n yd i r e c t i o n s ，r e s u l t i n gi 1 2w h a th a sc o m et ob ec a l l e dr a m s e y t h e o r y r a m s e yt h e o r yi sal a r g ea n db e a u t i f u la r e ao fc o m b i n a t o r i c s ，i nw h i c h ag r e a tv a r i e t yo ft e c h n i q u e sa r eu s e df r o mm a n yb r a n c h e so fm a t h e m a t i c s ，a n d w h o s er e s u l t sa r ei m p o r t a n tn o to n l yi ng r a p ht h e o r ya n dq o m b i n a t o r i c s ，b u ti n s e tt h e o r y ，l o g i c ，a n a l y s i s ，a l g e b r a ，a n dg e o m e t r ya sw e l l i nt h i sp a p e r ，t h r e et o p i c so i lg r a p hh a v eb e e ns t u d i e d t h ef i r s ti st h es t u d y o nt h ea d j a c e n ts p e c t r a lr a d i io fb i c y c l i cg r a p h s t h es e c o n di st h es t u d yo n t h el a p l a c i a ns p e c t r a lr a d i io fb i c y c l i cg r a p h s t h et h i r di st h es t u d yo i lt u r i n n u m b e ro fe v e nc y c l e t h el a r g e s te i g e n v a l u eo ft h ea d ja c e n tm a t r i xo fag r a p hgi sc a l l e dt h e ， s p e c t r a lr a d i u so fg i nc h a p t e r2 ，w ew i l lp r o o ft h e o r e mr e f g u a n g y i d u o l i n t h m ， a n du s et h i st h e o r e ma n do t h e rt e c h n i q u e s ，w eo b t a i nt h el a r g e s tt h r e es p e c t r a l r a d i ii nt h ec l a s so fa l lb i c y c l i cg r a p hw i t ho r d e rn ，t o g e t h e rw i t ht h ec o r r e s p o n d i n g g r a p h s t h e1 a r g e s te i g e n v a l u eo ft h el a p a l a c i a nm a t r i xo fag r a p hgi sc a l l e dt h e v i a b s t r a c t l a p a l a c i a ns p e c t r a lr a d i u so fg i nt h e s p e c t r a lr a d i ii nt h ec l a s so fa l lb i c y c l i c c o r r e s p o n d i n gg r a p h s c h a p t e r3 ，w eo b t a i nt h el a r g e s tf o u r g r a p hw i t ho r d e r 竹，t o g e t h e rw i t ht h e t h er e s e a r c ho ft u r i nn u m b e ri sai m p o r t a n tp a r to fr a m s e yt h e o r y i n c h a p t e r4 ，w eu s et h ea l g e b r a i cm e t h o d so fl i n e a rs y s t e mo fe q u a t i o n so v e rt h e f i n i t ef i e l d ，a n dt h e “c r i t i c a lz e r o - s u ms e q u e n c e s ”t os h o wt h a t ：i fm 3 ，t h e nf o r a n yi n t e g e r 粤w i t hz 5 ，4 z 2 c h ( b ) ( w h e r ec h ( f q ) i st h ec h a r a c t e ro ft h e f i n i t ef i e l db ) a n da n yv e r t e xui nt h eg r a p h ( g ) c o n t r a c t e db yw e n g e r 。t h e r e i sac y c l eo fl e n g t h2 之i n 日m ( q ) p a s s i n gt h r o u g ht h ev e r t e xu k e y w o r d s ：g r a p h ；l a p l a c i a nm a t r i x ；a d j a c e n c ym a t r i x ；l a p l a c i a ne i g e n v a l u e s i c h a r a c t e r i s t i cp o l y n o m i a l ；e i g e n v e c t o r ；l a p l a c i a ns p e c t r a lr a d i u s ；u p p e r ( 1 0 w e r ) b o u n d ；b i c y c l i cg r a p h ；a d d i n ga ne d g e ；g r a f t i n g ；s u b d i v i s i o n ；f i n i t ef i e l d ；v e c t o r p a c e ；l i n e a rs y s t e mo fe q u a t i o n s v i i 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：f 刁郜名 砷年月7 日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 伺郜席 棚年月7 日 学位论文独创性声明 本人声明，所呈交的学位论文系在导师指导下本人独立完成的研究成果。 文中依法引用他人的成果，均已做出明确标注或得到许可。论文内容未包含法 律意义上已属于他人的任何形式的研究成果，也不包含本人已用于其他学位申 请的论文或成果。 本人如违反上述声明，愿意承担以下责任和后果： 1 交回学校授予的学位证书； 2 学校可在相关媒体上对作者本人的行为进行通报； 3 本人按照学校规定的方式，对因不当取得学位给学校造成的名誉损害， 进行公开道歉； 4 本人负责因论文成果不实产生的法律纠纷。 论文作者签名：与蠢擎舀，_ 一 日期：丑年- l 月手日 第1 章绪论 第1 章绪论 1 1 研究背景与进展 图论起源于1 8 世纪欧拉研究和解决的柯尼斯堡七桥问题而其真正的发展 始于2 0 世纪5 0 年代，这与计算机技术的飞速发展是分不开的因此，它是一门 既古老又年轻的学科作为网络技术的理论基础和研究工具的重要部分，随着信 息时代的发展，图论正日益显现出其在计算机、通信、生物等诸多领域的强大活， 力 就数学内部各分支内部而言，图论和代数相结合产生了代数图论，就是用代 数的方法来解决图论的问题为了研究图的性质，人们引进了各种各样的矩阵， 诸如图的邻接矩阵，关联矩阵，距离矩阵，拉普拉斯矩阵等等这些矩阵都与图有 着自然的联系代数图论的一个主要问题就是研究图的性质能否以及如何由这些 矩阵的代数性质反映出来这里所指的矩阵的代数性质，主要指矩阵的特征值 在上面所提到的矩阵中，最重要的有两个：图的邻接矩阵和拉普拉斯矩阵。图的 邻接矩阵的特征值和拉普拉斯矩阵的特征值都是图的在同构意义下的不变量 图谱理论主要研究的就是图的邻接矩阵和拉普拉斯矩阵的特征值和特征向 量，是代数图论研究的一个重要方向对图的邻接矩阵及其特征值目前已经形成 比较成熟的理论，详见专著f 6 ，1 3 ，1 4 1 ，由于图的拉普拉斯矩阵的特征值与图的结 构之间有着更自然的联系，更能反映图的图论性质，因此对拉普拉斯矩阵的特征 值的研究正越来越引起人们的关注，是当前图论研究中的一个热点伺题在图谱 理论的研究中，近年来，又兴起了对特殊图类的邻接谱半径和拉普拉斯谱半径的 排序的研究目前对树，单圈图的邻接谱半径和拉普拉斯谱半径的排序的研究已 经比较多了，可参见f 9 3 ，9 2 ，9 4 ，9 5 ，9 6 ，9 7 1 由于双圈图的结构相对复杂，无论是 研究它的邻接谱半径还是拉普拉斯谱半径的都是很复杂的下面我们总结一下 对这一图类的邻接谱半径和拉普拉斯谱半径的研究情况 文1 0 1 1 给出了阶数为扎，悬挂点数为k 的单圈图和双圈图中邻接谱半径最 大的图，文f 1 0 2 1 中给出了阶数为佗，匹配数为m 的双圈图中邻接谱半径最大的 图，文【1 0 3 1 给出了阶数为n ，具有完美匹配的双圈图中邻接谱半径最大的图，文 1 0 4 】给出了双圈图邻接谱半径的和圈上点变化的关系目前对双圈图的邻接谱 半径的研究仅限于此，对它的拉普拉斯谱半径的研究的结果就更少了，基本上就 没有，这主要是因为图的拉普拉斯谱矩阵不再是一个非负矩阵，矩阵论中很多结 果都用不上，导致很多对邻接谱成立的结论，对拉普拉斯谱都不成立或者很难证 明它们是成立的，这就使得对双圈图的拉普拉斯谱半径的排序更为困难本文借 鉴了前人对双圈图的分类，对双圈图中邻接谱半径和拉普拉斯谱半径作了进一步 的研究 就图论的研究方法而言，近年来，人们又引进了一些现代方法，比如随机图方 法、分析方法、渐近方法、代数构造方法等，这些现代方法的引进得到了一些完 全不平凡的结果，它们揭示了有限的离散结构经常比人们想象的要复杂的多，这 改变了人们对图论的第一印象图论的问题中通常以极值问题最为棘手，r a , m s e y 同济大学博士学位论文 问题就是极值问题中最重要的问题之一关于t u r i n 数的研究则是r a r a s e y 理论 的重要部分之一确定任意一个图日的t u r i n 数e x ( n ；h ) 的渐近阶是一件非常 困难的事，因为我们不仅要给出一个上界还要给出一个不平凡的下界，即与上界 有相同的阶的下界，要想得到这样的下界就必需要构造出个图使得日不是这 个图的子图，这样的工作似乎比给出上界还要困难 于是人们就从二部图着手开始研究，试图能够有所突破但从现有的结果 来看，也只有完全二部图凰。的t u r i n 数e x ( n ；k ，) 的渐近阶完全确定了人 们又把目标锁定在另一特殊二部图一偶圈q 仉上1 9 6 5 年，e r d s s 给出了偶 圈q m 的t u r i n 数e x ( n ；q m ) 的一个上界l o m n l + 去1 9 9 1 年，w e n g e r 构造了 偶图( g ) ，并由这种图得到了e x ( n ；q 仇) ( m = 2 ，3 ，5 ) 的一个下界饥l + 去( 其 中c 为一个与佗无关的常数) 这样结合e r d s s 给出的上界，我们就可以得到 e x ( n ；q m ) ( m = 2 ，3 ，5 ) 的渐近阶在本文中我们利用有限域上的线性方程组和 有限域上的范德蒙矩阵以及“临界零和序列”等代数方法证明了：当m 3 时 对任意一个满足孽5 ，4 z 2 c h ( f q ) ( 其中c h ( f q ) 是有限域日的特征) 的自然 数幺过w e n g e r 构造的图( 口) 中的任一点都有长为2 粤的偶圈，从而说明了由 图( 口) 不可能得到e x ( n ；岛m ) ( 仇2 ，3 ，5 ) 的下界 在本文中，我们主要做了如下一些工作： ( 一) 根据邻接谱半径的定义证明了广义夺邻定理( 定理r e f g u a n g y i d u o l i n t h m ) ，利用此定理以及嫁接，收缩内部路中边等技巧，研究了具有固定阶 数的双圈图的邻接谱半径( 第2 章) 且给出了具有最大邻接谱半径的前三个双 圈图以及它们对应的谱半径 ( 二) 利用拉普拉斯特征多项式，研究了具有固定阶数的双圈图的拉普拉斯 谱半径( 第3 章) 且给出了具有最大拉普拉斯谱半径的前四个双圈图以及它们 对应的谱半径 ( 三) 利用有限域上的线性方程组和有限域上的范德蒙矩阵以及“临界 零和序列”等代数方法证明了( 第4 章) ：当仇3 时，对任意一个满足 粤5 ，4 粤2 c h ( b ) ( 其中c h ( b ) 是有限域b 的特征) 的自然数z ，过w e n g e r 构造的图( g ) 中的任一点都有长为2 e 的偶圈，从而说明了由图( g ) 不可能 得到e x ( n ；c 2 m ) ( m 2 ，3 ，5 ) 的下界 1 2 基本概念 在本文中，所用到的未加定义的图论和矩阵论中的一些基本定义和术语可见 文献( 7 ，8 和 5 5 】) 设g = ( ee ) 是有r t 个顶点的简单连通图( 不含环和多重 边) ，其中v = v l ，口2 ，) 表示点集合、e 是边集合图g 的邻接矩阵定 义为一个仡x 佗矩阵a ( a ) = ( q i ，) ，其中当忱和秒，相邻时o i j = 1 ；，当仇和u i 不相邻时a ，= 0 假如g 是一个简单图，则a ( g ) 是一个实对称的( 0 ，1 ) 矩阵且 它的主对角线上的元素全为零从而它的特征值全为实数不失一般性，可以假 设它们按照如下从大到小的顺序排列为： a 1 ( g ) a 2 ( g ) a n ( g ) 2 第1 章绪论 且称a 七( g ) 为图g 的第k 大的特征值特别地，称a l ( g ) 为图g 的谱半径假 如m 是一个亿阶方阵且其特征值全为实数，我们不妨用a i , ( m ) 表示它的第k 大的特征值特别令o ( m ) = m a x ( 队( m ) i ：i = l ，2 ，礼) ，称为m 的谱半径 设x 是图g 的相应于a 七( g ) 的一个特征向量，自然地，x 中的分量可以与 图g 的顶点之间建立一个一一对应关系，称为给g 一个点赋值我们常将对应 于点仇的x 中的分量记为x ( v i ) 或或特别地，假如是相应于p ( g ) 的单位特征向量，则我们有 p ( g ) = x t a ( g ) x = ：x 池) x ( 叼) 仉吩e e 令d ( v i ) 表示顶点仇的度，魂( g ) 表示g 的第i 大的度，即有d l ( g ) 如伶) 2 厶( g ) ，j g i 或i y ( g ) j 表示图g 的顶点数，图g 的拉普拉斯矩阵定义为 l ( g ) = d ( g ) 一a ( g ) ，其中d = d ( g ) = d i a g ( d ( v 1 ) ，d ( 忱) ，d ( ) ) 是图g 的度对角矩阵对图g 的每一条边，取其一个端点为始点，另一端点为终点，这 一过程称为给图g 一个定向当图g 取定二定向时，其定向关联矩阵定义为 q = q ( a ) = ( 蜘) ，其中， f ，l ，当地是边e f 的始点时； g ，= c - 1 ，当耽是边e ，的终点时； 。 【0 ，其它 。 则l ( g ) = q ( g ) q ( g ) t ( 其中q ( g ) ? 是矩阵q ( g ) 的转置矩嘲且l ( g ) 与 g + 的定向无关( 见 3 5 】p 1 6 8 ) 容易证明l ( g ) 是一个半正定的、对称的实矩阵 且它的每一行的行和为零，因此，l ( g ) 又是奇异的从而，我们可以假设它的特 征值按照从大到小的顺序排列为： 弘l ( g ) 乒匕( g ) 弘再( g ) = 0 且称肌( g ) 为图g 的第七大的拉普拉斯特征值。特别地，称弘1 ( g ) 为图g 的拉 普拉斯谱半径，记为弘( g ) 矩阵l ( g ) 的谱称为g 的拉普拉斯谱，记作s p e c ( a ) ， 即s p e c ( a ) = 肛l ( g ) ，p 2 ( g ) ，脚( g ) ) 设x 是图g 的相应于肌( g ) 的一个特征向量，自然地，x 中的分量也可以 与图g 的顶点之间建立一个一一对应关系，也是给g 一个点赋值 7 - 4 】特别地， 假如x 是相应于p ( g ) 的单位特征向量，则我们有 。1 p ( g ) = x t l ( g ) x = ( x 池) 一x ( 吻) ) 2 亍y 嚣黼。l 等 饥吩置 。 “。 对x 的每一个分量取绝对值，得到一个新的向量，记作l xj 图g = ( ve ) 的线图记作z ( g ) ，它是由g 通过如下方式而得到：以g 的边 集合b 作为t ( g ) 的点集合，e 中任意两个元素在z ( g ) 中是邻接的当且仅当它 们在。g 中有公共点 对i 于图的拉普拉斯矩阵，还可以从另外一个角度来研究它，即k ( g ) = q ( g ) t 固( g ) f o r s m a n 3 2 和g u t m a n 4 6 】研究了l ( g ) 和k ( g ) 之间的联系 一方面，与l ( g ) 不同的是，k ( g ) 要依赖于g 的定向：另一方面，当g 是二 分图时，我们总是可以给g 一个定向，使得k ( g ) 是一个非负矩阵且k ( g ) = 2 聪+ a ( ：g ( g ) ) ，其中a ( g ( g ) ) 是g 的线图粤( g ) 的邻接矩阵，k 是一个仍阶的 3 同济大学博士学位论文 单位矩阵由于k ( g ) = q ( g ) t q ( g ) 和己( g ) = q ( g ) q ( g ) r 有相同的非零特征 值( 见 5 5 p 5 3 ) ，因此，假如g 是一个二分图，则l ( g ) 与2 k + a ( 粤( g ) ) 有相同 的非零特征值 1 3 矩阵论中的基本定理及其在图谱理论中的应用 由矩阵论中的基本定理可以得到图的邻接矩阵和拉普拉斯特矩阵征值的某 些基本性质在本节中，我们将只给出与图的拉邻接矩阵和拉普拉斯特矩阵征值 密切相关的矩阵论中的某些最重要的基本定理，而对于一些其它的矩阵论中的结 果，我们将在后面需要的时候再引进 如下的定理通常被称为c o u r a n t w e y l 不等式( 见 1 4 】p 5 1 ) 定理1 3 1 设a l ( x ) a 2 ( x ) k ( x ) 表示礼阶实对称矩降x 的n 个 特征值设a 和b 都是n 阶实对称矩阵且c = a + b ，则有 a t + l ( c ) a i + t ( a ) + + 1 ( b ) ， a n 一讧j ( c ) a n - i ( a ) + a n j ( b ) ， 其中0 i ，歹，i + 歹一i = 1 礼特另1 ， a l ( c ) a i ( a ) + a 1 ( b ) 设g l 是g 的一个子图，由上面的c o u r a n t w e y l 不等式，我们有： 推论1 3 1 设g l 是g 的一个子图，则有p ( g t ) p ( g ) ，u ( a i ) p ( g ) 若g l 是g 的一个真子图，则有p ( a 1 ) p ( g ) 定理1 3 2 【1 4 】每一个非负矩阵a 的真主子阵的最大特征值f 不超过a 的最 大特征值r 进一步，假如a 是不可约的，则总有f r ；假如a 是可约的，则至 少存在一个真主子阵，使得f = r 成立 定理1 3 3 【1 4 】设a 是一个非负矩阵，则a 的最大特征值随着a 中元素的增 加而递增进一步，如果a 是不可约的，则a 的最大特征值随着a 中元素的增 加而严格递增 定理1 3 4 【4 0 设g 是一仑二分图，则非负对称阵日( g ) = d ( g ) + a ( g ) = l 己( g ) j 和i ( c ) 是酋相似的；特别地，如果g 是连通的，则g 的拉普拉斯谱半径 是l ( c ) 的一个单特征值 推论1 3 2 设g 1 是连通二分图g 的一个真子图，则有p ( g 1 ) p ( m k + i ，m 一1 ) 引理2 2 4 ( 6 4 1 ) 设g 是连通图，g 7 是g 的真诱导子图，则对任意的z p ( g ) ， 都有p ( c ，z ) p ( a ，z ) 设( g ) 是g 的最大度，由引理2 2 4 ，我们可以得到 p ( a ) p ( k 1 ，( g ) u ( 礼一( g ) 一1 ) 砬) = ( g ) 定理2 2 1 设g 是连通图，u ，口l ，u 2 ，协( 7 1 ) 是g 中的点 设 ，w 是g 中互不相交的非空顶点子集，并且 k = 0 i l ， 幽，忱) ( 优) ( ( 钆) u _ u ) ) ( i = 1 ，2 ，7 i ) 7 同济大学博士学位论文 设g 让( u 1 ，? j r ) 的顶点集v ( a 让( v l ，诈) ) = y ( g ) ，边集 一 t 、r、 e ( a u ( u 。，) ) = le ( g ) u 仇仇，仇秽魄) ) uiu “仇，乱口幽) ) i = lu = 1 x 是g 的p e r r o n 向量假设我们有孔之m a x k 1 ，k ) ，其中丘表示向 量x 中点u 对应的分量，则p ( a u ( u 1 ，) ) p ( g ) 。 证明：设g 7 = g 。( u 。，嘶) ，由线性代数中关于实对称矩阵的知识知 x t a ( g ) x = | p ( g ) ，p ( a ) x t a ( g 7 ) k 所以有 p ( a 7 ) 一p ( a ) x t a ( g 7 ) x x r a ( g ) x = x t 陋( g 7 ) 一a ( g ) i x r k i = ( ( 溉一墨i ) 五玎) 0 ( 2 2 1 ) i = 1j = l 下面我们证明( 2 2 1 ) 式中的严格不等式成立若不然，则( 2 2 1 ) 中所有等 号均成立特别的有 p ( a 7 ) = p ( a ) = x ? a ( g 7 ) 只 一 由此可得x 也是a ( a ) 对应于p ( a ) 的特征向量，即有a ( g 7 ) x = p ( ) x 因 此 ( a ( g ) 一a ( g ) ) x = ( p ( c ) 一p ( g ) ) x = 0 ( 2 2 2 ) 然而，设钆是a ( g 7 ) 一a ( g ) 对应于缸的取值，因为k l ，k r 不全为0 ，易知 口u 0 ，a 乜0 所以q u x o ，与( 2 2 2 ) 矛盾 由定理2 2 1 可得下面的推论： 推论2 2 2 设g 是一个连通图，u 1 ，v k v ( a ) ( k 2 ) 是g 中一些与悬挂 点相邻的点假设g 有8 个悬挂点与 1 ，相邻g i ( i = 1 ，k ) 是由g 删掉这8 条悬挂边并把这s 个悬挂点都与某一个仇点相连得到的图则 m a x p ( g 1 ) ，j d ( g 七) ) p ( g ) 引理2 2 5 设g t ( u ) 是由边集不空的图g 和k + 1 阶树t 组成的，且丁和g 只有一个公共点，设为口再设 g 7 = g + ? j w l + + v w k ， 其中w l ，w 2 ，叫七是不在g 中的七个不同的悬挂点则p ( a 7 ) p ( a t ( u ) ) 8 第2 章双圈图的邻接谱半径 证明：对t 中异于点u 的非悬挂点的个数g 用归纳法 如果口= 0 ，显然结论已成立所以我们可以假设g 1 。 设x 是r 中异于u 的并且是t 中与钞距离最远的非悬挂点设p 是t ，到 z 在t 中的唯一的路，y 是路p 中与x 相邻的点设n ( x ) = 可，z 1 ，。d 一1 ) ， 其中d = d ( z ) ，于是z 1 ，z d 一1 都是悬挂点 在定理2 2 1 中取u = y ，r = 1 ，口1 = z ，= ( 。1 ，一，z d l ，则定理2 2 1 中的图g ( u 。) 就是 g 仙( u 1 ) = g 一 z z l ，x x d 一1 ) 十 y x t ，y x d l 另方面，如果我们取让= x ，r = 1 ，v l = y ，y i = ( 可) z ) ，那么不难看出定理 2 2 1 中的g 。( u ) 同构于吼( 口1 ) 因为我们要么有为恐要么有恐， 所以由定理2 2 1 ，总是有p ( c 犯( 口1 ) ) p ( g ) 同时显然在g u ( 口1 ) 对应的树t 中不同于点可的非悬挂点的个数是