论文部分内容阅读
令Gσ是简单无向图G的一个定向图,它具有顶点集V={v1,…,vn}和弧集Γ。定向图Gσ的斜邻接矩阵定义为一个n×n矩阵S(Gσ)=(sij),其中sij=1且sji=-1如果〈vi,vj〉∈Γ,否则sij=sji=0。斜邻接矩阵的所有特征根称为定向图的斜谱。定向图的斜谱半径定义为它的斜邻接矩阵的所有特征根的模的最大值。 斜邻接矩阵最早是由Tutte于1947年提出来的,Tutte利用斜邻接矩阵给出了一个图是否有完美匹配的判定条件。在1961年,物理学家Fisher,Kasteleyn和Temperley利用矩阵的行列式和Pfaffian给出了平面矩形网格的完美匹配的计数。他们发现:如果一个图G存在一个Pfaman定向σ,那么该图的完美匹配的个数等于其对应的斜邻接矩阵S(Gσ)的行列式的平方根。 在2010年,Adiga等人研究了定向图的斜谱并且引入了斜能量的概念,它定义为斜邻接矩阵的所有特征根的模之和。斜能量可以看作是无向图的能量在定向图上的一种推广。在2012年,Cavers等人对定向图上的斜邻接矩阵作了广泛的研究并且提出了一些关于斜谱半径的有趣的问题,例如:在给定顶点数的奇圈图(所有圈都是奇圈)中,哪些图具有最大斜谱半径?其实他们的研究主要基于在加拿大阿尔伯塔省“BIRS”研究站召开的“Theory and Applications of Matrices Described by Patterns”会议上讨论的结果。自从他们的结果问世以来,越来越多的学者开始了对斜邻接矩阵的研究。 定向图的斜谱半径的上界已经被很多学者研究并且关于这个上界已经有了很好的结果。但是,斜谱半径的下界方面的结果很少。在第二章,我们研究了斜谱半径的下界并得到了一些新结果。进一步我们给出了那些满足斜谱半径达到下界√△的图的一些性质,其中△为图的最大度。最后,利用已经得到的斜谱半径的下界,我们给出了斜能量的几个下界,这些结果改进了由Adiga等人得到的斜能量下界。 Cavers等人证明了一个结果:如果G是一个奇圈图(所有圈都是奇圈),那么G的任意一个定向图Gσ的斜谱半径都等于G的最大匹配根。其中,图G的最大匹配根指的是图G的匹配多项式的所有根的最大值。并且他们提出了一个猜想:在所有顶点数为n的奇圈图中,能达到最大斜谱半径的图一定同构于一个特殊奇圈图,该图有一个度为n-1的顶点并且恰好有|3(n-1)/2|条边。在第三章我们证明了这个猜想。进一步,我们给出了给定顶点数和边数的奇圈图的斜谱半径的紧上界,并且完全刻画了达到该上界的极值图。 在2012年,Gutman和Wagner提出了图G的匹配能量ME(G)的概念,它定义为图G的匹配多项式的所有根的绝对值之和。Gutman和、Wagner指出匹配能量在化学上有很重要的应用。他们得到了下面一个重要的关系式:TRE(G)=E(G)-ME(G),其中TRE(G)是图G的拓扑共振能而E(G)是图G的能量。对于n个顶点的随机图Gn,p,其中p∈(0,1),他们给出了匹配能量ME(Gn,p)的上界和下界。进一步,他们提出了一个猜想:当n→∞,n-3/2E(ME(Gn,p))几乎总是收敛于8√p/3π,其中E(ME(Gn,p))是ME(Gn,p)的期望。 在第四章,我们引入了随机图的经验匹配根(匹配多项式的根)分布函数的概念。大部分关于根分布的研究主要集中于随机矩阵的谱分布。随机矩阵的谱分布可追溯到Wigner的杰出工作一半圈分布。利用矩方法,我们证明了随机图的经验匹配根分布几乎总是弱收敛于半圈分布。最后,我们利用分析的方法证明了他们的猜想。事实上,我们证明了一个更强的结果:当n→∞,n-3/2ME(Gn,p)几乎总是收敛于8√p/3π。