（应用数学专业论文）某些图的谱半径与代数连通度.pdf

摘要 对图谱的研究是代数图论中的一个重要研究方向，其主要研究对象是图的邻接谱与 图的l a p l a e i a n 谱。该研究方向是通过图的矩阵表示将图论中的图与代数中的矩阵联系 起来，再利用图论和代数方面的一些方法来研究图的代数性质。 b r u a l d i s o l h e i d 问题是图谱研究中的一个重要问题。目前为止，这一问题的结论已 经很多，但问题还没有得以完全解决。本文继续对b r u a l d i s o l h e i d 问题进行了研究。主 要研究内容分为三章。 第一章，对图谱理论进行了概述，介绍了其中的相关概念和记号，并对全文结构进 行了说明。 第二章，研究了给定阶和边独立数的单圈图的谱半径，研究了双圈图的谱半径。 第三章，按代数连通度对树进行了排序，确定了阶不小于4 5 且代数连通度属于区 可业2 , 2 - 压卜黼 关键词：邻接矩阵，拉普拉斯矩阵，谱半径，拉普拉斯谱半径，代数连通度 s p e c t r a lr a d i u sa n da l g e b r a i cc o n n e c t i v i t yo f s o m eg r a p h s w a n gx 协然e ( a p p l i e dm a t h e m a t i c s ) d i r e c t e db yp r o f t a ns h a n g w a n g a b s t r a c t t h es t u d yo fg r a p hs p e c t r ai sa l li m p o r t a n td i r e c t i o no fr e s e a r c hi na l g e b r a i cg r a p ht h e o r y , a n di t sm a i n o b j e c to fs t u d yi st h ea d j a c e n c ys p e c t r u ma n dt h el a p l a c i a ns p e c t r u m t h i sd i r e c t i o no fr e s e a r c ha s s o c i a t e s t h eg r a p hi ng r a p ht h e o r yw i t ht h em a t r i xi na l g e b r ab yt h em a t r i xr e p r e s e n t a t i o no fag r a p h , t h e ns t u d i e s t h ea l g e b r a i cp r o p e r t yo fg r a p h sw i t ht h em e t h o d si ng r a p ht h e o r ya n da l g e b r a b r u a l d i - s o l h e i dp r o b l e mi sav e r yi m p o r t a n tp r o b l e mi nt h er e s e a r c ho fg r a p hs p e c t r u m s of 打t h e r e s u l t sr e l a t e dt ot h i sp r o b l e mh a v eb e e ns om u c h ，b u tt h ep r o b l e mi sn o tf u l l yr e s o l v e d t h i st h e s i sw i l l p r o c e e dw i 付1t h er e s e a r c ho f t h i sp r o b l e m t h em a i nc o n t e n tc a l lb ed i v i d e di n t ot h r e ec h a p t e r s t h ef i r s tc h a p t e rg i v e sa l lo v e r v i e wo fg r a p hs p e c t r u m ，i n t r o d u c e st h er e l a t e dd e f m i t i o n sa n dn o t a t i o n s ， a n de x p l a i n st h es t r u c t u r eo f t h i st h e s i s t h es e c o n dc h a p t e rs t u d i e st h es p e c t r a lr a d i u so fu n i c y c l i cg r a p h sg i v e no r d e ra n de d g ei n d e p e n d e n c e n u m b e r , t h es p e c t r a lr a d i u so f b i c y c l i cg r a p h s t h et h i r dc h a p t e ro r d e r st h et r e e sb yt h e i ra l g e b r a i cc o n n e c t i v i t y , a n dd e t e r m i n e sa l lt h et r e e so fo r d e r 训哪5 m 姆响m r v a l 竽卜压) k e y w o r d s ：a d j a c e n c ym a t r i x ，l a p l a c i a nm a t r i x ，s p e c t r a lr a d i u s ，l a p l a c i a ns p e c t r a l r a d i u s ，a l g e b r a i cc o n n e c t i v i t y 独创性声明和使用授权书格式 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名： 圣兰辞 r 期 年月日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：至墨盔丑 指导教师签名： 日期： 日期： 年 年 月 月 日 日 中国石油大学( 华东) 硕士学位论文 1 1 图谱概论 第一章绪论 图论是一门悠久的学科，它起源于十八世纪欧拉研究和解决的格尼斯堡七桥问题。 从那以后，图论开始了漫长的发展历程。二十世纪五十年代以后，由于计算机技术的广 泛应用图论真正获得了飞速发展。它开始作为网络技术的理论基础和重要研究工具，为 计算机、通讯、生物等诸多领域的发展提供越来越强大的理论支持。 随着图论自身的发展，它开始呈现出与其它数学分支相融合的特点，于是许多新的 数学分支诞生了。代数图论就是代数与图论结合后的产物，它的实质就是用代数上的方 法来解决图论中的一些问题。在代数图论中，图谱理论是一个开始得比较早且非常重要 的研究方向。最初，图谱理论作为一套离散的数学方法被理论化学家和物理学家用于求 解一类偏微分方程的近似解。随后，历经数学家、物理学家、理论化学家的共同努力， 图谱理论获得了飞速发展和广泛应用。时至今日，经过不断积累、完善，图谱理论已经 自成体系，并作为一种重要的数学理论被写进了教科书，成为数学、计算机、通信等专 业学习的必要知识。 图谱理论的核心内容是图的各种谱。在这门理论中，为了研究图的性质人们引入了 各种各样的矩阵。例如：图的邻接矩阵，拉普拉斯矩阵，无符号拉普拉斯矩阵等等。这 些矩阵与图都有着自然的联系，它们的特征值就是对应图的各种谱。图谱理论的一个主 要问题就是研究图的结构性质能否以及如何由这些矩阵的代数性质反映出来( 这里所说 的结构性质是指与图的结构有关的量，如顶点数，边数，匹配数等等。而代数性质主要 指矩阵的特征值和特征向量) 。可喜的是，在这方面人们已经取得了大量的研究成果。 这极大地丰富了图谱的研究内容。 图谱理论取得如此巨大的发展与其重要的研究意义是分不开的。对此，可以从以下 几点进行理解： 1 现实中产生的各种问题往往可以抽象为图论中的模型，而图谱理论对这些问题 的解决无疑提供了一种新方法、新思路。例如：在量子化学中，某些不饱和碳氢化合物 的分子结构可以用图论中的图来表示。在这样的分子里，电子的能量级别与分子所对应 的图的特征值密切相关。因此，诸如分子的稳定性等化学性质都可通过研究图的谱来知 道。 第一章绪论 2 在计算机上存储图的信息时，面临着数据量大，不便于描述等问题。相比而言， 图的谱却是比较简单的一组有限序列。如果我们需要的信息完全包含在图的谱中，我们 完全可以用谱来代替对应的图。这样就可以方便地用计算机进行存储、计算。 3 图谱理论是图论与组合论研究的重要领域之一。它丰富了图论和组合数学的研 究内容，又为它们的研究提供了一种重要的工具一谱技术。这一工具的广泛应用极大地 推动了它们的发展。 1 2 基本概念和记号 代数图论脚踏图论与代数这两个数学分支，图谱的研究不可避免地牵涉到了图论和 代数方面的一些概念。下面对本文即将出现的一些概念和记号做一下说明。对于没有解 释的概念，读者可以参阅相关文献【1 1 。 在本文中，所研究的图均是无环无重边、有限无向的简单图。设g = ( 矿，e ) 是这样 的简单图，其中v = y ( g ) = v 1v ：，v 。) ，e = e ( g ) = e l , p ：，e 埘) 。则称矿和e 分别 为图g 的顶点集和边集，并且y 的势lv | _ r l 称为图g 的顶点数，或称阶数。若顶点u 和 顶点v 是边g 的两个端点，则记e = u y ，并称u 、v 与e 相关联，u 和v 相邻接。若两条边 存在一个公共端点，也称这两条边是相邻的。设v 是图g 的一个顶点，g 中与v 关联的 边的数目称为v 的度，记为d g ( 1 ，) 或d ( v ) 。 图g 的邻接矩阵彳= 4 ( g ) = f ) 是一个聆阶( 0 ，1 ) - 方阵，其中a 扩= 1 ，当且仅当v ， 与v ，邻接。显然，么是实对称的。图g 的特征多项式定义为d e t ( x i a ) ，记为( g ，x ) 或 ( g ) ，且( g ，x ) 的根称为g 的特征值。由么是实对称的可知g 的特征值都是实数。称g 的最大特征值为g 的谱半径，记为p ( g ) 。 图g 的拉普拉斯矩阵定义为l = l ( g ) = d ( g ) 一a ( g ) ，其中 d = d ( g ) = a i a g ( d ( v 1 ) ，d ( ) ) 是图g 的度对角矩阵。容易证明l ( g ) 是一个半正定实对称矩阵。不失一般性，设l ( g ) 的 特征值按从大到小的顺序排列为： u ( g ) = “1 ( g ) “2 ( g ) 口( g ) = “。一l ( g ) z ，。( g ) = 0 2 中国石油大学( 华东) 硕士学位论文 则称z ( g ) 的特征值为图g 的拉普拉斯特征值。特别地，甜( g ) 称为图g 的拉普拉斯谱半 径，a ( g ) 称为图g 的代数连通度。 类似地，图g 的无符号拉普拉斯矩阵定义为q = 烈g ) = d ( g ) + 彳( g ) 。q ( g ) 的特征 值称为图g 的q 一特征值，并且g 最大的q 一特征值称为g 的q 一谱半径或拟拉普拉斯 谱半径。 到目前为止，图谱理论的研究内容主要集中于邻接谱和拉普拉斯谱的研究，对于无 符号拉普拉斯谱的研究也有一定的涉及。 1 3 本文的研究内容及结构安排 在图谱研究中，b r u a l d i ，s o l h e i d l 2 1 曾提出一个重要的研究方向：给定一个图的集合 s ，在这个集合中寻找一个谱半径的上界，并刻画达到这个上界的图。 经过中外学者的不懈努力，这个问题取得了一系列进展。 1 b e r m a n ，z h a n g 3 1 证明了：在所有具有，z 个顶点和后个割点的连通图中，q 是唯 一具有最大谱的图，其中q 1 是添加n - k 条长度几乎相等的路( 长度可以为o ) 到完全 图巧一七的不同顶点而得到的图。 2 l i u ，l u ，t i a n 4 l j , l t b ) j 了：在所有具有甩个顶点和k 条割边的连通图中，g ：是唯一 具有最大谱的图，其中瞵是在完全图瓦一。的某个顶点上加上k 条悬挂边而得到的图。 3 w u ，x i a o ，h o n g i s e r i , 0t ：在所有具有，2 个顶点和七条悬挂边的树中，乙七是唯一 具有最大谱的树，其中乙。是由一个顶点连接k 条长度几乎相等的路得到的图。 除了上述结论，在一些文献【8 1 中读者将发现更多的研究成果，这里不再赘述。同 时，随着研究的深入，学者们对b r u a l d i ，s o l h e i d 所提的问题有了更深的思考。实际上， 这个问题包含着依据某种标准对类图进行排序的思想，只不过在原问题中所选的标准 是按图的谱半径从大到小，对图进行排序也只是找出最大的一个即可。意识到以上这点， 学者们的研究思路就大大开阔了。总的来讲j 有三个方面可以进行推广。一是变换排序 的标准( 例如，改为按代数连通度从大( 小) 到小( 大) ，按拉普拉斯谱半径从大( 小) 到小( 大) 等等) ，二是扩大目标图形的范围( 如，同时求出第二大，第三大的图) ， 3 第一章绪论 三是更改研究对象( 如单圈图，双圈图等等) 。通过在以上三个方向的不断探索，尝试， 人们取得了不小的进展，写出了大量的文章。这极大地丰富了图谱的研究内容，充实了 相关的研究成果。 本文仍以b r u a l d i ，s o l h e i d 所提的问题为基础，并在上述三个方面寻求一些新的突 破，进行一些有意义的推广。具体来讲，本文解决了三个问题。 1 在具有固定阶和边独立数的单圈图中，给出了谱半径的前三个最大值，并且得 到了相应的极图。 2 确定了双圈图谱半径的第六大至第十大值和对应的极图。 3 确定了阶不小于4 5 且代数连通度在区间i 下5 - , a i , 2 - ；1 内的所有树。 l 二 其中，前两个问题将在第二章解决，第三个问题将在第三章解决。 4 中国石油大学( 华东) 硕士学位论文 2 1 引言 第二章邻接矩阵的谱半径 图所对应的邻接矩阵的谱( 简称邻接谱) 是最早被研究的一种谱。它起源于量子化 学领域。1 9 3 1 年，e h i i c k e l 对非饱和碳氢化合物的研究引入了一种近似处理的方法， 得到了对应分子的图论模型。在这种模型中，图的特征值被用来表示特定电子的能量级。 自此以后，基于应用的需要，图的邻接谱引起了众多数学家和化学家的广泛研究和应用。 从目前来看，邻接谱的研究成果是各种谱的研究中最多的。这是因为，一方面邻接 谱的研究相对比较简单，有许多的研究工具可以用；另一方面，邻接谱的研究开始得比 较早，图的邻接矩阵是最直观的与图相联系的矩阵。考虑到以上两点，本文首先研究图 的邻接谱。 在本章中，我们沿袭b r u a l d i 。s o l h e i d 问题的研究思路，选定单圈图、双圈图作为研 究对象，找出了满足一定条件的图形。下面具体介绍一下单圈图、双圈图的研究现状， 并给出本文的研究成果。 单圈图是阶数等于边数的连通图。单圈图研究的早期，许多学者，如李乔、洪渊、 c v e t k o v i dd 和r o w l i n s o np 等f 9 - 1 1 】，主要研究仅依赖于阶的单圈图谱半径上界或下界。 目前，郭曙光【1 2 】确定了给定阶的单圈图谱半径的前六个最大值；常安，田丰6 1 确定了完 美单圈图谱半径的前两个最大值；谭尚旺等【1 3 1 确定了给定阶和边独立数的单圈图谱半径 的最大值。在2 2 节，我们将给出具有固定阶和边独立数的单圈图谱半径的前三个最大 值，并给出相应的极图，它推广了已有的许多结论。 双圈图是另一类重要的连通图，它的边数比阶数多1 。对双圈图，已有许多研究成 果，本文主要关注给定阶的双圈图。何常香【1 4 】等人确定了双圈图谱半径的前三个大值和 对应的图，丌静【1 5 】进一步给出了谱半径的第四和第五大值以及对应的图。2 3 节将给出 双圈图谱半径的第六大至第十大值和对应的图。 2 2 给定阶和边独立数的单圈图的谱半径 2 2 1 引理及具体证明 引理2 1 【1 川设g = 珊是图g 的一条边，c ( 口) 是包含e 的所有圈构成的集合，则 5 第二章邻接矩阵的谱半径 矽( g ，x ) = # ( g - e ，x ) - # ( g - u - v ，x ) - 2 矽( g y ( z ) ，z ) 引理2 2 t 1 6 1 设v 是图g 的一个点，c ( v ) 是g 中包含v 的所有圈的集合，g ( v ) 表 示1 ，在g 中的邻接顶点集，则 矽( g ，z ) = x # ( g - v ，x ) - d ( g - u - v ，x ) - 2 q 6 ( g - v ( z ) ，x ) 暂乍g ( v ) 2 e c ( v ) 引理2 3 吲设v 是非平凡连通图g 的顶点，记在g 的顶点v 处接出两条路最和毋后 得到的图为g k ，。则七，+ 2 时，p ( g 女，) p ( g f + 1 ) 。从g 女，到g “+ 1 的过程称为图的 第一类边变换，简记为1 e r 。 引理2 4 【9 】设v 和“是连通图g 中邻接的两个度2 的顶点，记在v 和u 分别接出路 只和只后得到的图为瓯f o 则七之，+ 2 时，p ( g k j ) 夕( g 乙，j + 1 ) 。从g ：，到g ：刮+ ，的过程 称为图的第二类边变换，简记为2 e 。 引理2 5 【5 1 设“和v 为连通图g 的两个顶点，v l ，v 2 ，v 芦是在g 中邻接v 但不邻接 “的一些顶点，x = ( 五，恐，) 7 是对应户( g ) 的一个正的特征向量，其中x ，对应，。记 g = g - w l 一w p + 洲1 + + w j p 。如果x 。石，则p ( g ) p ( g ) 。于是x p 、g ok ，) 时，b 中的两部分 都是非负的。特别d c ( v ) s i 时，b 中的第二部分是正的；d a ( v ) = s - i 且g k l p ，时， b 中的第一部分是正的。因此，x p ( g 三i ，) 时， o ，即( q k 岛o ) f ，b f 、g o , ，) 。这包含需 要的结论。 设u ( n ，i ，) 表示阶为n 、边独立数为i 且圈长为z 的所有单圈图的集合；u ( n ，f ) 表示 阶为1 1 且边独立数为f 的所有单圈图的集合。设h u ( n ，f ，z ) ，材是劈不在圈上的一个点。 如果存在不全为零的非负整数k ，s ( 其中k = 0 时，s 2 ) ，使日一g = 蝎u 蝎ug ，其中 g 是阶至少是3 的连通图，则称u 是日的一个末端分枝点。令v ，v 2 屹是日的一个路， 如果该路上各点的度满足d ( v ，) 3 ，d 片( v t ) = 1 并且d h ( v 。) = 2 ( 皓2 , 3 ，k - 1 ) ，则称 该路是日在点h 的长为尼一1 的悬挂路。特别地，与1 度顶点关联的边称为图h 的悬挂 边。 7 第二章邻接矩阵的谱半径 如果一个单圈图可通过在一个圈的某些顶点上增加一些长为2 或1 的悬挂路而得 到，则称它为简化单圈图。显然，一个单圈图是简化单圈图，当且仅当它没有末端分枝 点。在所有简化单圈图中，圈上至多一个顶点w 可能同时有长为2 和l 的悬挂路且圈上 其它顶点都至多有一条悬挂边的图称为稀疏单圈图，其中w 称为该稀疏单圈图的主要生 长点。如果一个稀疏单圈图圈上的每个点上都无长为2 的悬挂路且每个点至多有一条悬 挂边，则每个有悬挂边的点都是主要生长点。 引理2 7 设玎 ，日u ( ，2 ，i ，) 不是稀疏单圈图或是主要生长点无悬挂边的稀疏单 圈图，则存在主要生长点有悬挂边的稀疏单圈图，u ( n ，i ，) ，使户( 日) ，知，日至少有一个点不在圈上。令t 表示日的末端分枝点的个数。 情形1 设r = 0 。令“和1 ，是圈上两点。 如果“和v 处都有长为2 的悬挂路，或者u 和1 ，的一个点上有长为2 的悬挂路而另一 个点上至少有2 条悬挂边，或者甜和1 ，处每个点都至少有2 条悬挂边，则在不减小图的 边独立数的前提下，在u 和v 处应用3 e t ，使这些悬挂边和长为2 的悬挂路连到同一个 点上。反复进行上述过程最后能够得到一个阶为，z 、边独立数f 且圈长为珀勺稀疏单圈 图形。设形的主要生长点“有m 条长为2 的悬挂路和p 条悬挂边，“在圈上的两个邻接 点分别为w ，v 并且它们悬挂边的个数分别为口，b ，则记形= w ( u ，m ，p ；w , a ；v ，b ) 。 如果聊= 0 或m 0 且p 1 ，则取h = w ( u ，m ，p ；w ，a ；v ，b ) 。下面设m 0 且p = 0 。 令m 是w ( u ，鹣p ；w ，a ；v ，的一个有最多悬挂边的最大匹配。 情形1 1 设不被m 饱和。 用j e t ，形能变成w ( u ，m - 1 ，p + 2 ；w ，a ；v ，b ) ，该图是在主要生长点z f 有悬挂边的阶 为胛、边独立数f 且圈长为，的稀疏单圈图，于是取h = w ( u ，m - i ，p + 2 ；w ，a ；v ，b ) 。 情形1 2 设“被m 饱和。 由m 假设，铭不被在u 处的长为2 的悬挂路上的边饱和，从而豁v m 或剃m 。 不妨设舢m ，则由m 假设，口= 0 。用2 e f ，形能变成w ( u ，聊- 1 ，p + 1 ；w ，a + 1 ；v ，b ) ， 该图是在主要生长点u 有悬挂边的阶为职、边独立数f 且圈长为，的稀疏单圈图，于是 取h = w ( u ，m 一1 ，p + 1 ；w ，a + 1 ；v ，b ) 。 8 中国石油大学( 华东) 硕士学位论文 根据上面讨论，从日可得到一个阶为刀、边独立数i 并且圈长为，的稀疏单圈图 h = w ( u ，掰7 ，p 7 ；w ，a 7 ；v ，b 7 ) ，其中p 7 0 。如果f 的边独立数了大于i ，则令 u 。l ，= w ( u ，聊7 一( 于一班p 7 + 2 ( 于一班w ，口7 ；v ，b7 ) ；否则，取u 。，= h 。于是乩u ( n ，i ，) 是在主要生长点有悬挂边的稀疏单圈图。由引理2 3 - 2 5 ，p ( 日) p ( h ) p ( u 蜊) ，并 且两个不等号至少一个成立。 情形2 设，0 。 设日的一个末端分枝点为“且日一“= 皿u 嵋dg ，其中东，s 不全为零( 露= 0 时， j 2 ) 且g 是一个单圈图。利用引理2 6 的记号，取日= a ，k 留，则当s 1 时，应用4 卫f ， h 能变成日l = g 。o , k l ；当s = 0 时，应用4 e ，h 能变成且= g o o ：o 。显然日1 是一个阶为 n 、边独立数i 、圈长为，且末端分枝点个数不增加的单圈图。对q 重复上述过程，直 到得到一个末端分枝点个数为0 的单圈图以为止。于是得到一个阶为刀、边独立数i 且 圈长为，的单圈图序列1 4 , ，凰，皿，并且由引理2 6 ，p ( h ) p ( 骂) 户( 皿) 。由 于皿满足情形1 的条件，于是由情形1 知：结论成立。 引理2 8 设，4 并且u 叫u ( n ，i ，z ) 是稀疏单圈图，则存在个稀疏单圈图 玑洲u ( n ，i ，一1 ) ，使尸( 巩，f ，) p ( u “，一1 ) 。 证明令c ，“，a ，b ，p 是玩， ，圈上的相继五个点( 按照顺时针) ，记 ( 口) = u ，b ，口。，q ) ，n v “( 6 ) = 函，p ，6 l ，一，b ，) ， “。肛) = 叠以，1 ，1 ，一，v 。 ， 其中口l ，一，a ，翻，包，v 1 ，1 ，女都是1 度点，“口都是2 度点，o s ，f l 且七0 。 令z 是属于夕( u 了) = p 的正特征向量，t 是z 中对应顶点z 的分量。设m 是u 。的 一个包含悬挂边最多的最大匹配，则由u ，的定义知，它的圈上除点甜外，其它点上的 悬挂边都在m 内。 设s = f = 0 。如果扼m ，则砑= ( m b e ) u 扛6 ) 是u 圳的一个含悬挂边最多的最 9 第二章邻接矩阵的谱半径 大匹配。因此，- f 面设a b m 。不失一般性，设x 口。令u 。，1 = u 。u 一沈+ 钟，则 m 仍然是u 酬一l 的一个最大匹配，并且由引理2 5 ，p ( u 州) p ( u n , i , l - i ) 。 下面假设s + t 0 ，分两种情形讨论。 情形1 设毛吒。令u 州一l = ，一a b + u b ，由j 0 ，或s = 0 _ r t 0 ，容易证明 m 仍然是v 州一1 的一个最大匹配，并且由引理2 5 ，p ( u w j ) p ( u 叫一1 ) 。 情形2 设屯 艺。如果s 0 ，则令 u w h ：u 。 ，一0 函甜，) 一0 函v ，- - u 2 + 0 口甜，) + ( = j 每v ，) + 口c 容易发现m 仍然是u 删一l 的一个最大匹配，并且由引理2 5 ，p ( u 叫) p ( u 2 ) p ( u 3 ) 。 证明 显然，u o = n ( i 一2 ，0 ，0 ，刀一2 f + 1 ，0 ，0 ) ，u l = h ( i 一3 , 0 ，0 ，n 一2 i + l ，l ，1 ) ， u 2 = h ( i 一2 ，0 ，0 ，聆一2 i ，1 ，0 ) 且u 3 = g ( i 一3 ，玎一2 i + 1 ，1 ，0 ，o ) 。由相关文献【1 3 】可知， p ( u o ) p ( u 。) 。应用2 e t ，能变成【厂l ，由引理2 4 ，p ( u 。) p ( u 2 ) 。由矽( g ( p ，k ，s ，t ，) ) 得 矿( u ，) 一( u ：) ：瓯乜x 3 ( x + 1 ) ( x 一2 ) + ( 以一f 一2 ) x 2 + 2 x + 【x 2 一( 胛一2 f ) 】 因此，当x p ( u ，) 时，矽( u 3 ) ( u 2 ) ，即得p ( u 2 ) p ( ) 。 引理2 1 0 假设i 5 ，g = g ( p ，k ，s ，t ，) g ( n ，f ) ，0ss ，t ，r l 并且k 0 ，则 p ( g ) p ( u 2 ) 。 证明不失一般性，假设s 厂。根据引理2 9 中p ( u 3 ) p ( u 2 ) ，下面设g u 3 。 情形1设s = 0 。此时，r = 0 ，p = f 一2 且k + f = 刀一2 f 。应用7 e f ，g 能变成 形= g ( p ，k + r ，0 ，0 ，0 ) ；再应用2 e ，形能变成g ( p - 1 ，k + ，+ 1 ，1 ，0 ，0 ) = u 3 。由引理2 5 、 引理2 4 和引理2 9 ，得p ( g ) p ( w ) 2 ，于是x p ( u ，) 时，矽( g ) 矽( ) 。所以p ( g ) 矽( u 2 ) u = o , 1 ；r = 1 , 2 ，3 ) 。因此，结论成立。 引理2 1 2 设f 4 且g = q j ( k ，z ，s ，f ) 仨妙。，u 1 ，u 2 ( ，= o ，1 ，2 ) ，则p ( q j ) p ( u 2 ) 。 证明记是引理2 1 1 中图的集合。由引理2 1 1 ，引理2 3 2 6 ，下面证明q ，应用图 的四类边变换能变成u 2 或，中的某个图即可。因此，只要证明下列三个断言。 断言1 q o ( 七，s ，) 应用图的四类边变换能变成u ：或中的某个图。 证情形1设s 0 且f 0 。此时，k + ，= i 一3 且j + r = 刀一2 i + 2 。 情形1 1 设r 2 。应用4 e t ，绕能变成 q o ( 露+ z ，0 ，s + f 一2 ，2 ) = o o ( f 一3 , 0 ，搬一2 f ，2 ) 情形1 2 设f = 1 。此时，由q o u o 知，0 。 如果七0 ，则应用3 e t ，q 0 能变成绕( | + ，一1 ，1 ，s ，r ) = q o 一4 , 1 ，2 2 i + 1 ，1 ) 。 如果k = 0 ，贝j 或= q o ( 0 ，f 一3 ，刀一2 i + l ，1 ) 。 情形2 设s = 0 或t = 0 。此时，由f 4 知，k + ，0 。 设j = t = 0 。由o o u o 知，0 ；且由i 4 知，k + ，2 。应用2 e t ，当z 2 时， 绕能变成q ( 七，- 1 ，s + 1 ，t + 1 ) ；当，= 1 时，q o 能变成q o ( i j 一1 ，z ，s + 1 ，f + 1 ) 。 设s = 0 且f 0 。应用2 e t ，当0 时，o o 能变成q 0 ( 七，z 一1 ，s + l ，f + 1 ) ；当z = 0 时， 绕能变成q o ( k - 1 ，s + l ，f + 1 ) 。设占0 且忙0 。由q o u o 知，z 0 。应用j e t ，q o 能 变成q o ( 七，z l ，s ，t + 2 ) 。 上面的讨论表明，应用j e t 或2 e f ，该情形的图可变成情形1 中的图。因此，由 1 3 第二章邻接矩阵的谱半径 情形1 ，该情形下结论也成立。 断言2 幺( 七，z ，s ，f ) 应用图的四类边变换能变成汐：或歹中的某个图。 证情形1设s 0 且r 0 。此时，k + ，= f 一4 且s + r = 胛一2 i + 2 。 情形1 1 设，2 。应用p ，q 1 能变成 q 1 ( k + 1 , 0 ，s + f 一2 ，2 ) = q 1 ( i 一4 , 0 ，甩一2 z ，2 ) 情形1 2 设，= 1 。此时，由q l u l 知，z 0 。 如果k 0 ，则应用3 e f ，q l 能变成q l ( 七+ ，一1 ，1 ，s ，r ) = g ( f 一5 ，1 ，i - - 2 i + 1 ，1 ) 。 如果k = 0 ，则q l = q 1 ( 0 ，i - 4 ，n - 2 i + 1 ，1 ) ，并且由q l u l 知，f 5 。 情形2设s = 0 或t = 0 。此时，由f 之4 知，k + z 0 。 设s = t = 0 。由q l u l 知，0 。当z 2 时，应用2 e t ，q 能变成q l ( 尼，l - 1 ， j + l ，r + 1 ) ；当，= l 时，如果k 0 ，则q 1 能变成q i ( k - 1 ，z ，s + l ，r + 1 ) ；如果k = 0 ，则应 用2 e t ，q l 能变成日( 1 ，1 ，0 ，0 ，0 ，1 ) ，再应用3 e 六，h ( 1 ，1 ，0 ，0 ，0 ，1 ) 能变成u 2 。 设s = 0 且f 0 。应用2 e t ，当z 0 时，q 1 能变成q ( 尼，- 1 ，s + 1 ，t + 1 ) ；当，= 0 时， q 能变成q 1 ( k 一1 ，z ，s + 1 ，f + 1 ) 。 设s 0 _ r t = 0 。由q 1 u l 知，z 0 。应用j e t ，q 能变成q l ( 七，一1 ，s ，r + 2 ) 。 上面的讨论表明，应用j e 厶2 量厶或3 e t ，该情形的图可变成情形l 中的图或玑。 因此，由情形1 ，该情形下结论也成立。 断言3 q ( 尼，z ，s ，f ) 应用图的4 e t 或1 e t 能变成。 证 因为q 2 ( 七，z ，s ，r ) u 2 ，所以，0 或r 2 。于是应用图的4 e f 或e f ， 鲛( 后，z ，s ，t ) 能变成u 2 。 引理2 1 3 设f 6 且g u ( n ，f ，3 ) 。如果g 萑了= 妙。，u 。，u 2 ，则p ( g ) p ( u 2 ) 。 证明只要证明下面三个断言即可。 断言1 p ( 日( f 一3 ，l ，0 ，1 7 - - 2 i + 1 ，0 ，o ) ) p ( u 2 ) 1 4 中国石油大学( 华东) 硕士学位论文 p ( h ( i 一3 , 0 ，0 ，刀一2 i ，1 ，2 ) ) p ( u 2 ) p ( h ( i 一4 , 1 ，0 ，刀一2 i + 1 , 1 ，1 ) ) 矽( u 2 ) ，即 p ( h ( i - 3 ，1 ，0 ，, - 2 i + 1 ，0 ，0 ) p ( u 2 ) 。类似方法能够证明另两个不等式。 断言2 如果存在非负整数k ，z ，p ，占，f ，g ，使g = h ( k ，z ，p ，s ，t ，g ) ，则p ( g ) p ( ) 。 证据断言1 、引理2 4 - 2 6 ，下面证明应用2 p f _ ，3 e t 和钇t ，图g ( k ，z ，p ，s ，t ，g ) 能 变成u 2 ，n ( i - 3 ，1 ，0 ，n 一2 f + 1 ，0 ，0 ) ，h ( i 一3 , 0 ，0 ，刀- 2 i ，1 ，2 ) 或n ( i - 4 ，1 , 0 ，i 1 2 f + 1 ，1 ，1 ) 即可。 为了方便，下面记4 ( k ，p ，s ，f ，g ) 为日。 情形1j ，t ，g 全为0 。应用3 e t ，日能变成- ( k + z + p ，0 ，0 ，0 ，0 ，0 ) = m ；再应用2 e t ， m 能变成- ( k + ，+ p - 1 ，0 ，0 ，1 ，1 ，0 ) = u 2 。 情形2s ，f ，g 恰一个不为0 。不妨设s o ，t = gi i 0 ，则露+ z + p = i - 2 。因gg 了， 所以，+ 夕0 。 如果，和p 都不为0 ，则应用3 e t ，日能变成h ( k ，1 ，+ p - 1 ，s ，0 ，0 ) = m ，然后m 再 变成h ( k + l + p - 1 ，1 ，0 ，s ，0 ，0 ) = h ( i - 3 ，1 ，0 ，n - 2 i + 1 ，0 ，0 ) 。 如果，和p 只有一个不为0 ，不妨设，= of tp 0 。当k 0 时，应用3 e f ，日能变 成h ( j j + ，+ p 一1 ，1 ，0 ，s ，0 ，o ) = ( f 一3 ，1 ，0 ，胛一2 i + l ，0 ，0 ) 。当k = 0 时，由g 隹，知，s 2 ，应 用3 e t ，日变成h ( k + ，+ p ，0 ，0 ，s 一1 , 1 ，0 ) = u 2 或变成 h ( k + 2 r + p 一1 , 1 ，0 ，s ，0 ，0 ) i i ( ( f 一3 , 1 ，0 ，n 一2 i + 1 , 0 ，o ) 1 5 第二章邻接矩阵的谱半径 情形3s ，t ，g 恰有两个不为0 。不妨设s 0 ，f 0 且q = 0 。应用3 e t ，日能变成 形= h ( k + l ，0 ，p ，s + t - 1 ，1 ，q ) ；w 再变成日( 七+ ，+ p ，0 ，0 ，s + r - 1 ，1 ，g ) = u 2 。 情形4s ，t ，g 都不为0 。此时k + l + p = i - 3 ，j j ，z ，p 至少一个不为0 ，不妨设k 0 。 如果i i ，z ，p 至少两个不为0 ，则应用3 e t ，日能变成 h ( k + j + p - 1 ，1 ，0 ，