Description | 图谱理论是图论研究的一个非常活跃的重要领域,它在量子化学、统计力学、通信网络及信息科学中均有一系列重要应用。图谱理论主要是利用线性代数、矩阵论等成熟的代数理论和技巧,并结合图论和组合数学的理论来研究图谱及其与图的结构性质以及与图的其它参数(如色数、度序列、直径、连通度等)之间的关系,它将图与网络的代数性质与其拓扑性质紧密结合在一起。
在图论中,为了研究图的性质,人们引进了各种各样的矩阵,诸如图的邻接矩阵、关联矩阵、距离矩阵、拉普拉斯矩阵、规范拉普拉斯矩阵等等。这些矩阵与图的结构都有着密切的联系。代数图论的一个主要问题就是研究图的性质能否以及如何由这些矩阵的代数性质反映出来。这里所指的矩阵的代数性质,主要指矩阵的特征值。
在上面所提到的矩阵中,最重要的有两个:图的拉普拉斯矩阵和邻接矩阵。图的拉普拉斯矩阵的特征值和邻接矩阵的特征值都是在图的同构下的不变量,图的邻接矩阵及特征值是代数图论的一个基本研究课题。在过去的几十年中,人们对图的邻接矩阵已经进行了大量的研究。和图的邻接矩阵相比,由于拉普拉斯矩阵中含有图的顶点度的信息,因此图的拉普拉斯矩阵的特征值与图的很多变量有着更加密切的联系。正如Mohar所说:图的拉普拉斯矩阵的特征值更能反映它的图论性质。所以对图的拉普拉斯矩阵的特征值的研究越来越受到人们的广泛关注。
人们对拉普拉斯矩阵的研究,可以追溯到160多年以前。拉普拉斯矩阵最著名的应用是在1847年Kirchhoff研究电流理论时所发现的矩阵-树定理:
矩阵-树定理:设G是一个有n个顶点的连通图且L(G)是它的拉普拉斯矩阵,去掉L(G)的第i行及j列得到一个n-1阶的子矩阵,记为L(i｜j)。则L(i｜j)的行列式的绝对值等于图G的生成树的个数。
在数学物理上,由于拉普拉斯矩阵可以被视为拉普拉斯微分算子的离散情形,故在数学上,该矩阵一般被称为拉普拉斯矩阵。图的拉普拉斯矩阵的特征值被称为图的拉普拉斯特征值。
在图的拉普拉斯特征值中,最重要的有两个:图的最大拉普拉斯特征值(即拉普拉斯谱半径)和图的次小拉普拉斯特征值(即代数连通度)。1981年,Cvetkovi(c)指出了图谱理论中进一步研究的十二个方向,其中之一就是用图的谱对图进行分类和排序。2007年,Abreu总结了Grone和Merris对树的代数连通度进行排序的结论,指出他们所作的一些工作只是初步的,并提出按照代数连通度的大小给出所有n阶树的-全序仍是一公开问题。
本文主要研究了按从大到小的顺序对图的拉普拉斯谱半径以及代数连通度进行排序的问题,所得结果具体如下:
(一)对有n个顶点的单圈图的拉普拉斯谱半径按照从大到小的顺序进行排序。在第二章中我们确定了单圈图拉普拉斯谱半径第五大值到第十三大值,并刻画了达到这些数值的相应的图。
(二)在第三章中我们对有n=g+k个顶点且圈长为g的单圈图的拉普拉斯谱半径按照从大到小的顺序进行排序,确定了圈长为g的单圈图的拉普拉斯谱半径从大到小的前”g/2”个图。
(三)在第四章中通过对瓶颈矩阵和图的代数连通度的研究,我们对有2k个顶点的具有完美匹配树的代数连通度按照从大到小的顺序进行排序,确定了具有完美匹配树的代数连通度第二大值到第五大值,并刻画了达到这些数值的相应的图(或图类)。
(四)在第五章中对单圈图的代数连通度进行研究,我们按照从小到大的顺序确定了有n个顶点的单圈图代数连通度第二小和第三小的图。 |
|---|
