含割边的图的距离无符号拉普拉斯谱半径论文

1目录摘要..........................................................2Abstract.................................................................................................................31引言.........................................................41.1研究背景与研究意义................................................41.2基本符号与概念....................................................51.2.1基本符号....................................................51.2.2基本概念....................................................51.3研究问题及主要结论................................................72图的距离无符号拉普拉斯谱半径.................................82.1谱半径及对应特征向量的相关性质.........................................................................82.2含割边的图的距离无符号拉普拉斯谱半径...........................................................11总结和展望.........................................................................................................14参考文献......................................................15致谢.........................................................162摘要图论是一门应用广泛的数学分支，被广泛的应用在离散数学问题中.在构成图论重要领域的图谱理论的研究过程中，人们引入了与图的结构有密切联系的矩阵，如：邻接矩阵、关联矩阵、距离矩阵和无符号距离矩阵.图谱理论主要研究图的性质能否及如何由这些矩阵的代数性质（主要为矩阵的特征值）反映出来.在众多矩阵中，因为无符号矩阵包含图的各点度的信息，更能反映出图的某些性质，所以备受研究者的青睐.本文在其基础上进一步研究距离无符号拉普拉斯谱半径.一个连通图G的距离无符号Laplace谱半径就是G的距离无符号Laplace矩阵的谱半径.连通图G的距离无符号Laplace矩阵定义为：)()()(GDTrDiagGDQ()(GTr是G的顶点距离度；)(GD为G的距离矩阵).本文主要研究含割边的n阶连通图的最小距离的无符号Laplace谱半径。具体内容分为下面两大部分：1.介绍图论研究背景与研究意义；所涉及的记号、基本概念；研究问题和主要结论；2.在含割边的n阶连通图中，以特征向量研究特征值的方法为指导思想，首先确定具有最小距离的无符号Laplace谱半径的取值范围为：))1,2(()(nGG，等号当且仅当)1,2(nGG成立；随后，运用Matlab求解，)(G为：21))1510123226822391627916726816273954(677596605028314123275815227475200424(29(3612525)(32654322nnnnnnnnnnG当且仅当)1,2(nGG时等号成立；最后进一步的得到一个特例，2)(G，当且仅当)2,2(GG等号成立.关键词：图；割边；距离无符号Laplace矩阵；谱半径3AbstractGraphtheory,abranchofAppliedMathematics,hasbeenwidelyusedindiscretemathematicsproblems.Inthecourseofthestudyofit,wehaveintroducedamatrix,closelyrelatedtothestructureofagraphsuchas:theadjacencymatrix,theincidencematrix,thedistancematrixandunsigneddistancematrixetc.ThenatureismainlyresearchedonGraphSpectraTheorywhetherandhowthesealgebraicpropertiesofthematrix,mainlytheeigenvalueofthematrix,canreflectsomeproperties.Inmanymatrix,manyresearcherslovenosymbolmatrix,foritcontainseachpointofinformationmapandreflectsomepropertiesofgraphs.Inthispaper,weresearchondistanceunsignedLaplacianspectralradiusfuther.Thespectralradiusofagraphdistancespectralradiusistheunsignedunsigneddistancematrix.Connectedgraphdistancematrixisdefinedasunsigned:)()()(GDTrDiagGDQ.Nosignofthespectralradiusoftheminimumdistanceinthispaperincludingthecutedgesofthegraphoforder.Specificcontentisdividedintothefollowingtwoparts:1.Introductiontographtheory,thebackgroundandresearchsignificance;markandthebasicconcept;theresearchquestionandthemainresearchconclusions;2.Containingcuttingedgesinthegraph,methodtostudytheeigenvaluesofthefeaturevectorastheguidingideology,firstdeterminetheminimumdistancehasnorangeofspectralradius:))1,2(()(nGGwithequalilyifandonlyif)1,2(nGG;then,usingtheMatlab,21))1510123226822391627916726816273954(677596605028314123275815227475200424(29(3612525)(32654322nnnnnnnnnnGwithequalilyifandonlyif)1,2(nGG;finallyfurthergetaspecialcase,2)(G,withequalilyifandonlyif)2,2(GG.Keywords:graph;cuttingedge;unsigneddistancematrix;spectralradius41引言本章首先介绍图的距离无符号拉普拉斯谱半径的研究背景与研究意义，再介绍本文中需要用到的基本概念与相关术语，最后介绍本文所研究的问题以及所取得的主要结果.1.1研究背景与研究意义图论是研究离散对象二元关系中关系结构的一个数学分支，与群论、矩阵论、拓扑学、概率论、数值分析等其它数学分支有着密切的联系，其广阔的应用领域涵盖了计算机科学、物理学、化学、运筹学、控制论、信息论、经济学、心理学、环境保护领域等.同时随着这些学科的发展，特别是计算机科学的快速发展，又促进了图论的发展.图论起源于著名的哥尼斯堡七桥问题，经过两百多年的发展，目前形成的研究分支主要包括代数图论、组合图论、拓扑图论和随机图论等.其中，代数图论是应用代数的方法来解决图论问题，或者用图论的方法来解决代数问题.图的谱理论是代数图论的一个研究热点，主要研究图的不同矩阵表示的谱性质（图的谱即图的邻接矩阵全体特征值，又称邻接谱[1]），通过讨论图的特征空间和特征多项式，建立图的拓扑结构（图的各种不变量）和图的矩阵表示的置换相似不变量之间的联系，应用置换群理论、矩阵论（特别是非负矩阵理论、对称矩阵理论、组合矩阵论）和谱几何理论来研究图的拓扑结构性质，同时也将图谱理论的研究结果应用于群论、矩阵论和谱几何论,以推动它们的理论发展.因此，图的谱理论是图论与组合数学共同关注的一个重要的研究领域.因此，利用代数组合和分析的方法建立图的极端特征值和这些参数的联系有着非常重要的意义.另外，图的极端特征值可视为一些特殊矩阵（如(0,1)-矩阵和整数Z-矩阵）的极端特征值.由于表示图的矩阵蕴含着图的结构信息，借助于图的特征向量的组合性质，研究这一类特殊矩阵的极端谱性质，对组合矩阵论的研究有着重要的理论意义.随着图所提供的组合模型在其他学科的广泛应用，图的极端特征值在这些领域发挥着令人惊奇的效果.例如，在结构化学中，图的邻接谱半径和最小特征值可以用于表示分子结构图中电子的能量级范围；而在计算机视觉中，利用图的邻接或Laplace谱半径及其对应特征向量是处理结构图匹配问题中的重要方法.关于极端特征值的研究在过去的几十年里主要集中于图的邻接矩阵、拉普拉斯矩阵、无符号拉普拉斯矩阵和距离矩阵等，均取得了丰硕的成果.由此可见，刻画给定图类中距离无符号谱半径的极值具有重要意义.近年来，在给定图类中谱半径取值的研究成果很多，如[2-6].类似于（邻接）拉普拉斯矩阵和（邻接）无符号拉普拉斯矩阵，近来，AouchicheM.和HanseP.在文献[7]中给出了连通图的距离拉普拉斯矩阵和距离无符号拉普拉斯矩阵.随后，关于它们的极端特征值的研究很快就受到了国内外学者的关注.5本文在含割边的n阶连通图中，运用特征向量研究特征值的方法，确定了具有最小距离的无符号Laplace谱半径的极图，并刻画了距离无符号Laplace谱半径关于阶数n的一个下界，从而进一步刻画出含割边的任意阶连通图中距离无符号Laplace谱半径的最小值.1.2基本符号与概念1.2.1基本符号设G表示一个图，本文中我们采用以下符号：GV:图G的顶点集GE:图G的边集),(vud:连接u和v的最短路的长度)(GD:图G的距离矩阵)(GTr:顶点v的距离度:)(GDQ的谱半径nK:n个顶点的完全图T:G的任意生成树),(mpG:完全图PK与mK的粘合1.2.2基本概念表示图的概念和矩阵有很多，下面介绍与本文有关的概念与矩阵.设图),(EVG，其中V为点集，}...,{)(21nvvvGVV，nV称为图G的阶数，E表示边集，}...,{)(21neeeGEE，mE称为图G的边数.定义1平行边：两个结点间方向相同的若干条边称为平行边或重边.定义2环：两端点相同的边称为环或自回路.定义3无环且无平行边的图形称为简单图[8].定义4G为有限图，如果对任意)(,GVvu，图中都存在一条连接vu,的路径，则称G为连通图.定义5树：连通无圈图为树[9].定义6任意不同两结点之间都有边相连的简单无向图成