论文部分内容阅读
图的Laplace谱理论是图论与组合矩阵论的一个重要研究课题,其主要研究图的代数表示(图的邻接矩阵,Laplace矩阵等)的谱,建立图的拓扑结构(特别是图的各种不变量)和图的特征空间的联系,应用代数,几何理论以及概率方法研究图的拓扑结构性质,或者应用图的拓扑结构来研究代数和几何中的谱性质,它在物理,化学,生物和计算机等科学中有着广泛的应用。 简单图的Laplace矩阵,在二十世纪七十年代初引起了研究者的注意,并逐渐成为代数图论和几何图论的研究热点,取得了很多优美的结论,特别是关于图的次小Laplace特征值(称为图的代数连通度)和其所对应的特征向量(称为Fiedler向量)的研究。和图的其它反映连通性能的不变量(如点连通度和边连通度)一样,代数连通度被视为图的连通性的一个定量的度量。Fiedler给出了Fiedler向量一个非常优美的组合结构性质,为图的拓扑结构分析提供了一个代数的方法。 近年来,相关研究者关注比简单图更广泛的一类图—混合图的Laplace谱,期望通过混合图的Laplace谱给出图的结构或不变量的更好刻画。本文主要针对两类混合图研究如下问题:与简单图的代数连通度和Fiedler向量相对应,混合图的Laplace矩阵的极小特征值与其所对应的特征向量是否也具有相类似的性质?本文就上述问题给出若干结论,建立了两类混合图的极小特征值与其全定向图的代数连通度的不等式关系,并给出了其极小特征值所对应特征向量的类似于Fiedler向量的组合结构性质。论文组织如下: 第一章首先介绍图的Laplace谱理论的研究背景,其次介绍有关图的基本概念和记号,最后,介绍所要研究的问题及进展,以及本文所取得的主要结果。 第二章讨论了恰含一个非奇异圈的连通混合图的特征值与特征向量,建立了这类混合图的极小特征值与其全定向图的代数连通度的不等式关系,并给出了其极小特征值所对应特征向量的组合结构性质。 第三章讨论了比第二章中图类更广泛的一类混合图的特征值与特征向量。该类混合图具有如下性质:所有非奇异圈恰有一条公共边,且除了该公共边的端