圖的特征向量的組合結(jié)構(gòu).pdf

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

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

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

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

5、證明了：對一個樹T，若其特征向量Y不含零分量且對應(yīng)于λk(T)，則λk(T)是單的且｜C(T,Y)｜=k-1．注意此結(jié)論中的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向量的性質(zhì)是一致的，因為任一個樹都是2-單樹．
　　 本文的另一個工作是研究特征集基數(shù)的極大性，對于樹的不同k-向量，特征集可能是變化的，如果僅考慮極大基數(shù)的k-向量，其特征集是否還是變化的？稱上述向量為k-極大向量，我們證明了：任一個k-向量的特征集都含于k-極大向量的特征集，因此k-極大向量的特征集是不變的．該結(jié)論和Fielder向量的性質(zhì)也是一致的，因為Fielder

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

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

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