图的斜谱和匹配根的若干结果

来源 :南开大学 | 被引量 : 0次 | 上传用户:LITAO14073164
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
令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π。
其他文献
知识经济时代的图书馆面临着巨大的挑战,人力资源管理对图书馆来说具有极其重要的战略意义,优秀的图书馆员成为图书馆的重要资源,在图书事业中发挥着重要作用.
据中国轻工商会消息,2005年9月8日,美国文具纸供应协会向美商务部和国际贸易委员会提交申诉,要求对来自中国的文具纸(Lined Paper School Supplies)进行反倾销立案调查。根据
计算机档案管理工作中存在一些不容忽视的弊端,其中最为关键的即为安全防护工作.计算机在档案管理中的安全防护工作与档案信息安全有着直接紧密的联系.本文通过总结计算机应
虚拟现实技术是指通过多媒体技术与仿真技术相结合生成逼真的虚拟环境,使用户以自然的方式与环境中的物体进行交互,从而产生身临其境感的一种技术。虚拟手术仿真技术是虚拟现
相容结构是指一个线性空间上的两个相同类型的代数结构,这两个代数结构对应乘法的任意线性组合还构成原来类型的代数结构.双代数结构是满足一定“相容性”条件的一个代数结构
凸性和广义凸性在优化问题、均衡问题和变分不等式问题研究中起着非常重要的作用,这主要是因为凸函数在凸集上的局部极值也一定是其全局极值.但是,凸函数的局限性也十分明显.
新课程标准实施后,人们都在努力追求课堂教学的高效率。从事小学数学教学多年,深感离开了学生的自主学习,那么高效就不可能实现。而学生的自主学习如果离开了课堂上听、说、
股票市场作为金融市场的一个重要组成部分,股票的趋势与波动反映了一个国家的政治、经济和社会状况,能够指导国家宏观调控。但股票市场是一个十分复杂的非线性动力系统,影响股价
边界层问题在物理、力学和工程等实际领域中是十分重要的。至今,绝大多数工作是对边界层现象进行实验分析和数值模拟,其数学理论是很欠缺的。近几年对于不可压缩Navier - Sto
粗糙集是由波兰数学家Pawlak首先提出的一种处理不完备和不确定性知识的新型数学工具,已经在机器学习、决策分析、知识获取、模式识别和专家系统等领域取得了一些成功的应用