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

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

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

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

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

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

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

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

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

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