论文部分内容阅读
图谱理论作为代数图论和组合矩阵论的一个重要研究分支,其核心是将图表达为各种矩阵,然后通过研究矩阵的谱(或特征值)以期进一步揭示图的结构性质.刻画某一图类的谱半径的上下界和相应的极图,图的零维数和秩的问题,以及图能量的问题是图谱理论中,三个十分重要的研究方向,受到众多图论专家的青睐和关注.它们在量子化学、理论化学、通信网络及信息科学等学科和领域中,均有一系列重要的应用.本学位论文主要考虑图的匹配数——这一结构参数,在以上三个图谱理论的研究方向中发挥的作用,分别建立了匹配数与图的两类特征值、图的零维数(零度)、图的秩以及图的能量的关系.全文共分五章,具体研究内容如下.第1章是绪论部分,主要介绍本论文的研究背景、研究现状、主要结论以及一些符号约定.第2章研究匹配数与图的距离拉普拉斯谱半径的关系.令G为一个n阶的无向简单图,我们利用图G的匹配数m(G)给出G的距离拉普拉斯谱半径ρL(G)的下界,得到:(ⅰ)当m(G)=[n/2]时,ρL(G)≥ n,等号成立的充分必要条件为G =K;(ⅱ)当1 ≤ m ≤[n/2]-1时,ρL(G)≥ 2n-m(G),等号成立的充分必要条件为G是Km(?)Kn-m的生成子图,且G含有完全二部图Km,n-m作为生成子图.第3章研究匹配数与混合图的零维数和秩的关系.首先,令G为一个混合图,利用图G的匹配数m(G)及图的阶数,给出了混合单圈图的Hermitian邻接矩阵零维数ηH(G)的表达式.其次,刻画了 Hermitian邻接矩阵的秩为3的所有混合图,并证明了这些图在转换同构的意义下,是由其Herrmitian邻接矩阵的谱所完全决定.最后,利用图C的匹配数m(G)及圈空间维数β(G),得到混合图的Hermitian邻接矩阵的秩γH(G)的上、下界,即:2m(G)-2β(G)≤<γHG)≤ 2m(G)+β(G);此外,我们完全刻画了达到上、下界的极图.第4章研究匹配数与图的能量的关系.令Gσ是一个底图为G的定向图,我们得到定向图Gσ的斜能量εS(Gσ)关于匹配数m(G)的下界:εS(Gσ)≥2m(G),等号成立的充分必要条件为Gσ转换等价于(?);其中,定向σ’将所有的边从一个部集指向另一个部集.此外,对于一个不含三角形的简单无向图G,我们得到其能量ε(G)关于匹配数m(G)和最大边度Δe的上界:(ⅰ)若Δe为偶数,ε(G)≤ 2m(G)(?),且等号成立的充分必要条件为G是m(G)个P2和一些孤立点的不交并;(ⅱ)若Δe 为奇数,£ε(G)≤ m(G)((?)),其中(a = 2(Δe +1)),且等号成立的充分必要条件为G是m(G)个P3和一些孤立点的不交并.第5章是总结与展望部分,对本论文的主要结论进行了整体的概括与总结,并介绍了本论文中可进一步研究的后续工作.