圖的哈密頓（gf）-因子

1、圖的哈密頓（g，f）-因子    近年來,圖論獲得了空前的發(fā)展,已經滲透到物理學、化學、電子學、生物學、運籌學、經濟學、系統(tǒng)工程以及計算機科學等學科領域.圖的因子理論是圖論的一個重要分支,在網(wǎng)絡設計和計算機科學中有較重要的應用價值,并因此成為圖論研究中最活躍的課題之一.在因子理論發(fā)展歷程中,最基本的結論是Tutte在1947年給出來的1-因子存在性條件,他的這一理論奠定了因子理論的基礎.1952年,Tutte又給出了圖有f-因子的充要條件,從而推廣了上述結論.到1970年,Lovasz又得到了圖有(g,f)-因子的一個判定準則.從此,因子理論的研究開始活

2、躍起來,大量關于因子理論的結果不斷的涌現(xiàn)出來.這些理論廣泛應用于組合設計、網(wǎng)絡設計、集成電路布圖設計等領域.眾所周知,一個網(wǎng)絡可以用圖來表示.圖的頂點和邊分別對應網(wǎng)絡中的結點和線路.常見的文件傳輸問題就可以如下描述：每個計算機x都有f(x)個通信端口,為了平衡整體傳輸過程中計算機的運載,在這f(x)個端口中,有g(x)個可以在任意時隙為同一個作業(yè)傳輸文件.在這個環(huán)境中,要解決的問題是如何來安排文件的傳輸過程,才能使得整個過程用時最短.本文所考慮的圖在無特殊說明的情況下均為簡單、有限無向圖.對于一個圖G=(V(G),E(G),我們分別用V(G)和E(G)表示圖的頂點集合和邊集合.圖G的頂點數(shù)|V

3、(G)|我們通常稱為G的階,一般用n來表示.對任意的vV(G),用dG(v)表示頂點v在G中的度數(shù).(G)和(G)分別表示圖G的最大度和最小度.對V(G)的子集S,用GS表示從G中刪去頂點集合S及與S關聯(lián)的邊所得到的子圖.若S=v,則令G-v=G-v.對E(G)的子集X,用G-X表示從G中刪去邊集合X所得的子圖.若X=e,則G-e簡記為G-e.若存在V(G)的兩個不交子集X和Y,使得V(G)=XY,且G的所有邊均有一個端點在X內,另一個端點在Y內,則稱G為二部圖,記為G=(X,Y,E(G).如果|X|=|Y|,則稱G為均衡二部圖.設g和f是定義在V(G)上的兩個整數(shù)值函數(shù),對每個vV(G),都

4、有0g(v)f(v).若H是圖G的一個支撐子圖,對任意頂點vV(H),滿足g(v)dH(v)f(v),那么我們稱H是圖G的一個(g,f)-因子.如果H是連通的,則稱H是G的一個連通因子.特別地,如果圖G本身是一個(g,f)-因子,則稱G為一個(g,f)-圖.設a和b是兩個非負整數(shù),如果對任意的vy(G),有g(v)=a,f(v)=b,則稱(g,f)-因子為a,b-因子.如果對每個vy(G),有g(v)=f(v),則稱(g,f)-因子為f-因子.如果a=b=k,則稱這樣的a,b-因子為k-因子；當k=1時,也稱1-因子為完美對集.對于圖G的一個因子,如果它同時包含G的一個哈密頓圈,我們就稱該因子

5、為G的一個哈密頓因子.在以上概念的基礎上,我們上面提到的文件傳輸問題就可以對應為：求G的邊集E(G)的一個劃分F_1,F_2,F_m.使得每個F_i,1im,都是一個(g,f)-因子.并且這個劃分有最小數(shù)目的(g,f)-因子.事實上,我們知道對任意一個圖而言,可能并沒有(g,f)-因子,所以我們有必要研究圖的(g,f)-因子的存在性.當更具體實際的問題出現(xiàn)時,可能就需要圖中存在更特殊的因子,比如連通因子,本文中我們研究的圖的哈密頓(g,f)-因子就屬于連通因子的范疇.我們對于哈密頓因子問題的研究,主要有兩方面的意義.一方面,就像我們上面的敘述,這類研究可以看作是哈密頓圈問題的推廣,因此有助于我

6、們更加深入研究哈密頓圈問題.另一方面,研究哈密頓因子對我們研究連通因子也是很有幫助的,連通因子問題與哈密頓問題和實際的信息網(wǎng)絡有著密切的聯(lián)系.如果一個圖有哈密頓因子的話,那么顯然該圖有連通因子(而且是2-連通因子).事實上,這也是我們研究哈密頓因子問題的根本目的和出發(fā)點.一個圖要存在哈密頓因子,那么首先要滿足哈密頓圈存在的條件,因此我們的研究思路可以從哈密頓圈存在的條件出發(fā)：從已有的一些關于哈密頓圈存在性的充分條件出發(fā)做相應的推廣,進而得到一些相關或者類似的充分條件,使得在G中存在包含某個(甚至任意一個)哈密頓圈的因子.事實上,很多學者已經對圖的特殊哈密頓因子做了研究,并且得到了豐富的結論.這

7、里的特殊哈密頓因子指的是g(v)=a,f(v)=b時,圖的哈密頓a,b-因子以及a=b=k時,圖的哈密頓k-因子.本文正是將這類特殊的哈密頓因子推廣到更一般的圖的哈密頓(g,f)-因子的研究上.我們在本文中主要研究的就是圖的哈密頓(g,f)-因子方面的一些結果.全文共分四章,第一章簡單介紹一下圖論中的一些基本概念,并給出因子、哈密頓圈問題的歷史背景和進展狀況以及一些已有的相關結論.這一章是后面其他各章節(jié)的基礎.第二章我們主要討論圖的哈密頓(g,f)-因子的一些情況.主要結論為：定理2.1.3.設G=(X,Y)是頂點數(shù)為n的均衡二部圖,ba>2為正整數(shù).g(x),f(x)為定義在V(G)上

8、的非負整數(shù)值函數(shù),滿足(?)vV(G),ag(v)f(v)b,且f(X)=f(Y),(?)vi,vjV(G),有f(vi)-g(vi)=f(vj)-g(vj),如果G滿足,那么對G的任一給定的哈密頓圈C,G都有一個(g,f)-因子包含C.推論2.1.4.設G=(X,Y)是頂點數(shù)為n的均衡二部圖,ba>2為正整數(shù).g(x),f(x)為定義在V(G)上的非負整數(shù)值函數(shù),滿足(?)vV(G),af(v)f(v)b,且f(X)=f(Y),(?)vi,vjV(G),有f(vi)-g(vi)=f(vj)-g(vj),如果G滿足,那么G有2-連通的(g,f)-因子.定理2.2.1.設正整數(shù)b>a

9、>2,G是一個n階2-連通圖.g(x)和f(x)為定義在V(G)上的非負整數(shù)值函數(shù),滿足(?)vV(G),ag(v)a>2,G是一個n階2-連通圖.g(x)和f(x)為定義在V(G)上的非負整數(shù)值函數(shù),滿足(?)vV(G),ag(v)a>2是正整數(shù),G是一頂點數(shù)為n的簡單圖,g(x)和f(x)為定義在V(G)上的非負整數(shù)值函數(shù),滿足ag(x)a>2是正整數(shù),G是一頂點數(shù)為n的簡單圖,g(x)和f(x)為定義在V(G)上的非負整數(shù)值函數(shù),滿足ag(x)同主題文章1.    呂濤軍. 關于哈密頓路圖的Chartrand,Kapoor和

10、Nordhaus猜想的解決' J. 科學通報. 1987.(13)    2.    呂濤軍. 正則的哈密頓路圖' J. 應用數(shù)學與計算數(shù)學學報. 1989.(02)    3.    孫惠泉. 競賽圖中的有向哈密頓路' J. 北京郵電大學學報. 1993.(02)    4.    胡智全,鄭德印. Duffus等人的結果的一個推廣

11、' J. 華中師范大學學報(自然科學版). 1998.(01)    5.    禹繼國,劉桂真,曹寶香. 圖的連通因子(英文)' J. 運籌學學報. 2005.(01)    6.    呂濤軍. 關于哈密頓路圖' J. 數(shù)學學報. 1988.(06)    7.    陳瑞袁. 關于2-連通圖哈密頓路的Lindquester猜測' J. 福建師范大學學報(自然科學版). 1991.(04)    8.    陶瑞華. 圖有H鏈的一個充分條件' J. 北京交通大學學報. 1991.(02)    9.    毛經中. 不含K3的哈密頓圖的次序列' J. 華中師范大學學報(自然科學版). 1986.(01)    10.