【硕士论文】最大匹配数为q的n阶单圈图谱半径的研究.pdf

《【硕士论文】最大匹配数为q的n阶单圈图谱半径的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最大匹配数为q的n阶单圈图谱半径的研究摘要谱半径是指图的邻接矩阵的特征多项式的最大特征根。研究图的谱半径不仅有着重要的图论意义，而且在物理，化学，生物学和计算机网络技术中有着广泛的应用。单圈图是边数等于顶点数的简单连通图，本文主要研究最大匹配数[1]为q的n阶单圈图谱半径的排序问题。在2003年，常安,田丰给出了有完美匹配的2k阶单圈图中具有最大和第二大谱半径的极图，近年来，郭[2][3]曙光和余爱梅，田丰分别给出了最大匹配数为q的n阶单圈图（简记为Unq(,)）中具有最大和第二大谱半径的极图。本文系统地研究了Unq(,)中谱半径的性质，讨论了Unq(,)中

2、的图移接变形后的谱半径的变化规律。在此基础上给出了在Unq(,)中具有最大和第二大谱半径的所有极图的刻画以及一个新的简单的证明；其次给出具有第三大谱半径的所有极图的猜想；特别地，刻画了Un(,2)中具有前四大谱半径的所有极图。关键词：特征多项式，谱半径，单圈图，最大匹配数5第1章引言１.1基本概念与记号本节对论文研究涉及的基本概念及记号进行介绍。图是图论的基本研究对象，因此我们首先给出图的一般定义和相关概念，记号。定义1.1称数学结构GVGEG=((),())为一个图，其中VG()表示G的顶点集，EG()表示G的边集，VG()和EG()之间存在着某种关系使得

3、每条边和两个顶点相关联，并将这两个顶点称为这条边的端点。我们通常用euv=来表示一条以u和v为端点的边e。图G中顶点集VG()的大小称为图的阶，记为G；在图中与顶点u相邻的点的集合称为u的邻域，记为Nu()；与顶点u相关联的边的条数称为u的度，记为deg()u；度为1的顶点称为悬挂点，与该点相关联的边称为悬挂边；在一个顶点上连接n−1条悬挂边的n阶图称为星图，记为K或S。1,n−1n对于图中的某些特殊的边，我们也有确切的定义。定义1.2一个环是一条边，它的两个端点是相同的；重边是具有同一对端点的多重边。一个简单图是不含有环和重边的图。我们这里只研究简单图。由

4、于图以多种形式出现，我们需要给出图的结构的有关概念。定义1.3设图GVE=(,)，GVE=(,)，若满足VV⊆且EE⊆，则称G是111111G的一个子图。若VV⊂，EE⊂，则称G是G的一个真子图。特别的，当VV=时，1111称G是G的一个生成子图。11定义1.4从简单图G到简单图H的同构是一个双射f：VG()→VH()，使得uv∈EG()当且仅当f()()ufvEH∈()。如果存在从G到H的同构，我们说“G同构于H”，记为GH≅。我们还需要一些术语来描述图中的两种路线：道路和圈以及一些相关的概念。定义1.5在顶边交错链Wveveev=L中，eEG∈()，ik

5、=1,2,L,，0112kkivVG∈()，jk=0,1,2,L,，且evv=，则称W是图G的一条道路，其中允许vv=，jiii−1ijee=，ij≠。称v是W的起点，v为W的终点，k为路长。各顶相异的道路称为ij0k轨道。起点与终点重合的轨道叫做圈，长为k的圈称为k阶圈，记作C。k对图G的任意两个顶点uv,的距离是指u与v为起止点的最短路长，记作duv(,)；图的直径是指图的任两个顶点间的最大距离；如果图G中的每对顶点都属于某一条道路，则称图G是连通图；没有圈的连通图称为树。本论文研究的是仅含有一个圈的连通图，称之为单圈图，也可以定义为顶点数和边数相等的连

6、通图。最后我们要介绍本论文涉及到的两个很重要的概念：匹配和谱半径。定义1.6设M是图GVE=(,)的边集E的一个子集，如果M中任意两条边在G中均不邻接，则称M是图G的一个匹配。若匹配M的某条边与顶点v相关联，则称M饱和顶点v，并且也称顶点v是M-饱和的，否则称v是M不饱和的。如果G的每一个顶点都是M-饱和的，则称M是G的一个完美匹配。定义1.7设M是图G的一个匹配，若不存在的另外的匹配M′使得M′>M，则称M是G的最大匹配。其中M表示匹配所包含的边数，称为匹配数。为了更好地说明一个图，便于研究图的性质，我们常用矩阵来表示一个图。下面我们给出简单图的三种矩阵表

7、示。定义1.8设GVE=(,)，Vvvv={,,L}，Eeee={,,L},12n12m21,(vv)∈Eij定义邻接矩阵:AG()(),,1,2,,==aijLn，其中a=；ijnn×ij0,否则定义关联矩阵:B()()Gb===,i1,2,,,LLnj1,2,,m，其中ijnm×1,ve是的端点ijb=；ij0,否则定义Laplacian矩阵:LG()=−DG()()AG,其中DG()=diagdd(,,,)Ld是图G的12n度对角矩阵，这里d是点v的度。ii定义1.9设G是n阶简单图，称邻接矩阵AG()的特征多项式为G的特征多项式，

8、记为PG(;)λ，PG(;)λ的特征值就称为G的特征