论文部分内容阅读
在二十世纪七十年代,Fiedler将简单图的Laplace矩阵的次小Laplace特征值定义为“代数连通度”,并用它来描述图的连通性.与代数连通度相对应的特征向量称为是图的Fiedler向量. Fiedler给出了Fiedler向量的一个非常优美的组合结构性质.自此,国内外研究者对图的代数连通度和Fiedler向量进行了深入研究,获得了一系列有意义的结论.
混合图的Laplace矩阵是简单图的Laplace矩阵的一个推广.但是,当混合图的Laplace矩阵为非奇异时,后者的性质并不能简单地平移到混合图上.因此,奇异性是导致混合图与简单图的谱性质差异的一个本质因素.
本文主要讨论混合图的奇异性.与Fiedler用图的特征值来刻画图的结构性质(连通性)相比拟,我们的思路是:用图的结构性质来刻画图的Laplace矩阵的奇异性(主要是极小特征值,称之为混合图的奇异度).我们对昆合图定义了两个参数:“点奇异度”与“边奇异度”,并用它们来描述图的奇异度.另一方面,考虑到简单图的Fiedler向量有非常优美的组合结构性质,Fan等人把这种性质推广到非奇异单圈混合图和恰含一个非奇异圈的混合图.本文把此性质进一步推广到边奇异度为1的混合图上,而后者包含了上述两类图.论文的组织结构如下:第一章首先介绍Laplace谱理论的研究背景,图的有关概念和记号,其次介绍所要研究的问题及进展,以及本文取得的主要结果。第二章介绍边奇异度与点奇异度的概念及相关性质,建立了它们与最小特征值之间的关系.第三章首先介绍非奇异单圈混合图与恰含一个非奇异圈的混合图的特征向量的结构,然后把该性质推广到边奇异度为1的混合图上.