论文部分内容阅读
图谱理论是图论研究的一个非常活跃的重要领域,它在量子化学、统计力学、通信网络及信息科学中均有一系列重要应用。图谱理论的研究主要是利用线性代数、矩阵理论等成熟的代数理论和技巧,并结合图论和组合数学的理论来研究图谱及其与图的结构性质以及与图的其它参数(如色数、度序列、直径、连通度等)之间的关系,它将图与网络的代数性质与其拓扑性质紧密结合在一起。
在图谱理论中人们引入了多种矩阵,诸如图的邻接矩阵、关联矩阵、距离矩阵、拉普拉斯矩阵、规范拉普拉斯矩阵等等,这些矩阵与图的结构都有着密切的联系。图谱理论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质反映出来,这里所指的矩阵的代数性质,主要指矩阵的特征值。
上面所提到的各种矩阵中,最重要的就是图的邻接矩阵和图的拉普拉斯矩阵。本文首先较详细地介绍了图的邻接矩阵和图的拉普拉斯矩阵特征值中几个重要课题的研究概况,然后分四部分介绍了我们围绕这些课题所取得的主要研究成果。本文所得的主要结论有:
一.在第二章中我们讨论图的邻接谱半径(即邻接矩阵最大的特征值),确定了直径为n-4的所有n(n≥9)阶连通图中取得最小邻接谱半径的图,所得结果正面回答了文献[93](E.R.vanDam,R.E.Kooij,The minimal spectral radius of graphs with a given diameter,Linear Algebra Appl.423(2007)408-419)中的一个问题,这同时也是[93]中猜想8中的一种情形。
用U(n,△)表示最大度为△的n阶单圈图的集合。当△≥(n+3)/2时,我们确定了U(n,△)中邻接谱半径达到最大的图;证明了结论当△(G)≥「7n/9」+1时,n(n≥30)阶单圈图G的邻接谱半径ρ(G)是其最大度△(G)的严格增函数。
二.在第三章中我们讨论图的零度,即图的邻接特征值0的重数。用η(G)表示图G的零度。通过利用图的邻接特征值的几个经典结论,我们分别刻画了η(G)=n-2的所有n阶图和η(G)=n-3的所有n阶图;证明了结论:n阶(n≥6)双圈图的零度集合是<0,n-4>,并且刻画了η(G)=n-4的所有n阶(n≥9)双圈图和η(G)=n-5的所有n阶(n≥10)双圈图。
三.在第四章中我们讨论树的拉普拉斯谱半径(即拉普拉斯矩阵最大的特征值)。用T(n,△)表示最大度为△的n阶树的集合。利用图的变形技巧以及特征多项式的一些技巧我们分别确定了当△≥(n+1)/2时,T(n,△)中拉普拉斯谱半径达到最大和次大的树,以及T(n,△)中拉普拉斯谱半径达到最小的树;证明了结论当△(T)≥(n+3)/2时,n(n≥4)阶树T的拉普拉斯谱半径是其最大度△(T)的严格增函数。
用T(2k)表示2k阶具有完美匹配的树的集合。通过将T(2k)中树分类,我们确定了T(2k)中拉普拉斯谱半径的第二大至第六大值,并确定了达到这些值的相应的树。
四.在第五章中我们讨论树的代数连通度(即拉普拉斯矩阵次小的特征值)。树T的代数连通度α(T)和其Perron分支的Bottleneck矩阵M之间有一个重要的关系,就是α(T)≥1/ρ(M),其中ρ(M)表示(实对称)矩阵M的最大特征值,我们给出了上述不等式中等号成立的充要条件;确定了所有满足α(T)≥2-√3的n(n≥15)阶树T,并对这些树按照代数连通度的大小作了完全排序。