圖的特征向量的組合結構.pdf

1、有限個或至多可數(shù)個存在某種關系的對象都可以用圖模型來表示．圖論主要研究這種模型所蘊藏的內部結構性質并借助圖參數(shù)予以表達，但一些具有廣泛應用前景的參數(shù)的計算復雜度屬NPH或NPC問題．鑒于此，代數(shù)組合分析的方法在圖的結構性質討論中有著非常重要的意義，譜圖理論即是借助圖的矩陣表示的譜及特征空間，來刻畫圖自身的結構參數(shù)，是現(xiàn)代數(shù)學表示論觀點的體現(xiàn)，本論文主要研究圖的矩陣表示的極小非零特征值所對應的特征向量的組合結構性質，并推廣到一般的特征向量

2、．此外，本文把特征向量的組合結構性質應用于圖劃分問題．
　　 圖的極端特征值，如譜半徑和極小非零特征值，在刻畫圖參數(shù)方面發(fā)揮很好的作用，這些極端特征值的特征向量在刻畫圖的整體結構性質方面也發(fā)揮著同等的作用．1975年Fiedler給出了圖的Laplace矩陣的次小特征值（稱為代數(shù)連通度）所對應的特征向量（稱為Fiedler向量）的組合結構性質，圖的Fiedler向量的符號變化和數(shù)值增減變化可以窺測圖的結構性質．1987年Merr

3、is根據(jù)Fiedler向量的符號變化提出特征集的概念（其中的元素稱為特征元），證明了：任一個樹的特征集都恰含一個特征元，并且該特征元與Fiedler向量的選取無關．1998年Bapat和Pati把特征集的概念推廣至一般圖，并給出特征集基數(shù)的一個上界，特別地對單圈圖的Fiedler向量的結構性質給予刻畫，在上述工作中，特征集定義于圖的Laplace矩陣的次小特征值所對應的特征向量．2002年Pati把特征集引入到樹的第三小特征值所對應的特

4、征向量，然而，這些特征向量不再具有樹的Fiedler向量所具有的性質，即特征集以及其基數(shù)與特征向量的選取有關．
　　 對于一個n階圖G，其Laplace特征值排序為：0=λ1(G)＜λ2(G)≤···≤λn(G)．
　　 對應于G的特征向量Y，其特征集記為C(G，Y).為了討論方便，我們稱特征向量y為圖G的k-向量，如果Y對應于λk(G)且λk(G)＞λk-1(G)．因此，F(xiàn)iedler向量是一個2-向量．Fiedler

5、證明了：對一個樹T，若其特征向量Y不含零分量且對應于λk(T)，則λk(T)是單的且｜C(T,Y)｜=k-1．注意此結論中的Y是一個k-向量．事實上，對樹的任一個k-向量Y，1≤｜C(T,Y)｜≤k-1．
　　 本文的工作之一是研究特征集或其基數(shù)的不變性，對于任意給定的k，是否存在樹T，使得對任意的k-向量Y都有｜C(T,Y)｜=1？稱滿足上述條件的樹為k-單樹，我們的回答是肯定的，并給出了k-單樹的等價條件．同時，我們發(fā)現(xiàn)，對

6、于k-單樹T，C(T,Y)也是不變的，這和Fielder向量的性質是一致的，因為任一個樹都是2-單樹．
　　 本文的另一個工作是研究特征集基數(shù)的極大性，對于樹的不同k-向量，特征集可能是變化的，如果僅考慮極大基數(shù)的k-向量，其特征集是否還是變化的？稱上述向量為k-極大向量，我們證明了：任一個k-向量的特征集都含于k-極大向量的特征集，因此k-極大向量的特征集是不變的．該結論和Fielder向量的性質也是一致的，因為Fielder

7、向量是一個2-極大向量，
　　 混合圖就是對簡單圖的部分邊進行定向后所得到的圖，在現(xiàn)實生活中有很多的應用背景．1999年Bapat等人引入了混合圖的Laplace矩陣，并推廣了經典的矩陣一樹定理．2002年張曉東和李炯生討論了混合圖的Laplace譜，給出了譜半徑的一些上界，考慮到奇異混合圖的Laplace譜在本質上等同于經典的Laplace譜，2005年范益政討論了非奇異的混合圖的的最小特征值，并給出對應特征向量的組合結構性質

8、，在該文中作者提出了一個公開問題，即給定腰長的非奇異單圈混合圖的最小特征值達到極小的極圖的刻畫，
　　 本文專注于上述問題，把特征集拓展到非奇異混合圖的Laplace最小特征值所對應的特征向量，我們給出了特征集的可能基數(shù)，并對特征元進行了刻畫；應用該性質，獲得了特征向量的符號變化；最終解決了范益政論文中所提的公開問題．
　　 本文的最后一部分就是把圖的k-向量應用于圖劃分問題，圖劃分的目標就是把一個圖分解成若干子圖并受某

9、種平衡約束，使得子圖之間的互聯(lián)代價或權值最小，在圖像分割和聚類中得到了廣泛應用，把一個圖分成兩個部分（即二劃分），可采用經典的最大流一最小割定理．但考慮分割大小的平衡性，1992年Hagen和Kahng提出了比值割的度量準則，并利用圖的Fiedler向量的結構性質給出分割方法，針對k-劃分問題，1994年Chan，Schlag，Zien推廣了比值割準則，應用圖的Laplace矩陣的前k個特征向量實現(xiàn)劃分，此外，2000年Shi和Mali