混合圖的奇異度與特征向量.pdf

1、在二十世紀七十年代，Fiedler將簡單圖的Laplace矩陣的次小Laplace特征值定義為“代數連通度”，并用它來描述圖的連通性．與代數連通度相對應的特征向量稱為是圖的Fiedler向量． Fiedler給出了Fiedler向量的一個非常優(yōu)美的組合結構性質．自此，國內外研究者對圖的代數連通度和Fiedler向量進行了深入研究，獲得了一系列有意義的結論． 混合圖的Laplace矩陣是簡單圖的Laplace矩陣的一個推廣．但是，

2、當混合圖的Laplace矩陣為非奇異時，后者的性質并不能簡單地平移到混合圖上．因此，奇異性是導致混合圖與簡單圖的譜性質差異的一個本質因素． 本文主要討論混合圖的奇異性．與Fiedler用圖的特征值來刻畫圖的結構性質(連通性)相比擬，我們的思路是：用圖的結構性質來刻畫圖的Laplace矩陣的奇異性(主要是極小特征值，稱之為混合圖的奇異度)．我們對昆合圖定義了兩個參數：“點奇異度”與“邊奇異度”，并用它們來描述圖的奇異度．另一方面，

3、考慮到簡單圖的Fiedler向量有非常優(yōu)美的組合結構性質，Fan等人把這種性質推廣到非奇異單圈混合圖和恰含一個非奇異圈的混合圖．本文把此性質進一步推廣到邊奇異度為1的混合圖上，而后者包含了上述兩類圖．論文的組織結構如下：第一章首先介紹Laplace譜理論的研究背景，圖的有關概念和記號，其次介紹所要研究的問題及進展，以及本文取得的主要結果。第二章介紹邊奇異度與點奇異度的概念及相關性質，建立了它們與最小特征值之間的關系．第三章首先介紹非奇異