论文部分内容阅读
图的谱理论是近年来组合数学与图论领域一项重要的研究内容,在量子化学、计算机科学、通讯网络等方面有广泛的应用.这一课题主要研究一些与图相关的矩阵,如邻接矩阵、Laplacian矩阵、距离矩阵等的谱性质(包括其特征值、特征向量、特征多项式系数的性质等).图的谱理论引起了国内外众多学者的关注,其内容不断得到丰富与发展. 本学位论文第一章首先回顾了图谱理论的研究历史与相关进展,接着介绍了本文所探讨课题的一些基本概念以及使用的记号,并概述了得到的主要结果. 第二章中,我们考虑一般矩阵的谱理论.对于不含零行(即每一行和都为正数)的非负矩阵,我们首先利用其平均2-行和给出了谱半径的上界和下界,并分别刻画了谱半径取得该上、下界的非负不可约矩阵;接着用一些具体例子说明我们所得到的结果与文献中利用非负矩阵行和给出的谱半径的上、下界无法比较优劣.我们还将这些结果应用于一些与图相关的非负矩阵谱半径的估计中,从而对一些已知的结果进行推广和改进.另外,我们得到了对角线为零的实对称矩阵主子阵最小特征值的上界和下界,以及实对称矩阵最小特征向量的分量的一些性质,并将这些结果应用于图的邻接矩阵最小特征值和最小特征向量中. 第三章中,我们重点讨论仙人掌图(即任意两个圈至多只有一个公共顶点的简单无向连通图)的邻接矩阵最小特征值,刻画了给定顶点数和悬挂点数的仙人掌图中最小特征值取得最小值的极图. 第四章中,我们研究连通图的距离矩阵谱半径.我们首次给出了一个只利用图中顶点之间的距离作为条件的与距离谱半径相关的图的变换.进而我们刻画了给定顶点数的非星状树中取得最大距离谱半径的图、给定顶点数的非毛虫树中取得最大和最小距离谱半径的图、以及给定顶点数的非星状非毛虫树中取得最小距离谱半径的图,同时也证明了在给定顶点数的非星状非毛虫树中只有两个图可能取得最大的距离谱半径,并刻画了这两个图.另外,我们还刻画了给定顶点数的双圈图中取得最小和第二小距离谱半径的图. 连通图的距离无符号Laplacian矩阵是最近新提出的与图相关的矩阵.第五章中,我们考虑其谱半径.我们分别刻画了给定顶点数的树图、单圈图、双圈图、二部图中取得最小距离无符号Laplacian谱半径的图.同时,我们还得到了双圈图中取得第二小距离无符号Laplacian谱半径的图.我们也分别确定了给定顶点数和悬挂点数的连通图中、以及给定顶点数和(点)连通度的连通图中取得最小距离无符号Laplacian谱半径的图.