论文部分内容阅读
图的谱是指与其相关矩阵的所有特征根及其重数构成的集合,它是特定组合结构的特有属性,往往能给出图的一些深刻的结论.图谱理论是代数图论重要研究课题之一,图谱理论的研究不仅促进和丰富了图论、组合学以及相关学科的研究,而且在信息科学、图像处理、压缩感知、量子化学、物理、计算机科学、网络以及信息技术、集成电路设计中均有广泛的应用.特别地,图的能量,图的谱的幂和,图的Kirchhoff指标,复杂网络的随机游走等与图的谱紧密相关.本文主要研究了图的谱计算,图的正规Laplacian特征值幂和的估计,图的无符号Laplacian特征值幂和的估计,图的关联能量的极值,复合图的电阻距离和Kirchhoff指标.全文共分五章,具体研究内容如下:第一章首先介绍了本文用到的一些基本概念、术语和记号,其次,介绍了与图谱相关问题的研究背景和研究进展,最后介绍了本文的主要结果.第二章首先给出了带有口袋的图的邻接特征多项式,Laplacian特征多项式,无符号Laplacian特征多项式及其相应的特征值.其次,构造了两类新的冠图:基于Q-运算的Q-点邻接冠图和Q-边邻接冠图,给出了它们的邻接(Laplacian,无符号Laplacian)谱;此外,给出了一类图是邻接(Laplacian,无符号Laplacian)整谱图的充分必要条件.第三章主要研究图的正规的Laplacian特征值的幂和和无符号Laplacian特征值幂和.图的特征值的幂和是指图的所有特征值的α-次幂的和,其中α是一个非零实数.首先,对一般图给出了图的正规Laplacian特征值的幂和的一些新的上、下界,作为应用,给出了乘法度Kirchhoff指标的一些新的界.同时,给出了一般图的无符号Laplacian特征值的幂和的一些新的上界和下界.第四章主要刻画了在所有给定具有固定连通度和边连通度的图中,图的关联能量的极大图.我们运用著名的Coulson积分公式,图G的剖分图的特征多项式,无符号Laplacian特征多项式和关联能量之间的关系,证明了在所有具有固定连通度和边连通度的图中,Kκ∨(K1∪Kn-κ-1)的关联能量最大.第五章主要研究了若干图的电阻距离和Kirchhoff指标.利用Laplacian矩阵的广义逆,我们首先给出了冠图和边冠图的任意两点间电阻距离,并在此基础上得到了它们的Kirchhoff指标公式.在文章[117]中,给出了剖分点-边冠图GS1?(GV2∪GE3)的A-谱,L-谱和Q-谱,但是Kf((GS1?(GV2∪GE3))的表达式有些复杂,继续运用分块矩阵的广义逆给出了剖分点-边冠图的任意两点间的电阻距离和Kirchhoff指标.接着,对剖分点-边冠图这种图运算做了更进一步的推广,将运算中拷贝相同的图推广到和不相同的图做点冠图运算和边冠图运算,即广义剖分点冠图和广义剖分边冠图,给出了它们的电阻距离和Kirchhoff指标.最后,对于正则图G1和任意图G2,建立了它的合成图:基于R-的点冠图和边冠图,G1ΘRG2和G1⊙RG2的Laplacian特征多项式与“原图”G1和G2的Laplacian特征多项式之间的联系,并在此基础上得到G1⊙RG2和G1ΘRG2Kirchhoff指标公式.