圖的哈密頓(g，f)-因子.pdf

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

2、結(jié)論.到1970年,Lovász又得到了圖有(g,f)-因子的一個判定準(zhǔn)則.從此,因子理論的研究開始活躍起來,大量關(guān)于因子理論的結(jié)果不斷的涌現(xiàn)出來.這些理論廣泛應(yīng)用于組合設(shè)計、網(wǎng)絡(luò)設(shè)計、集成電路布圖設(shè)計等領(lǐng)域.眾所周知,一個網(wǎng)絡(luò)可以用圖來表示.圖的頂點和邊分別對應(yīng)網(wǎng)絡(luò)中的結(jié)點和線路.常見的文件傳輸問題就可以如下描述:每個計算機x都有f(x)個通信端口,為了平衡整體傳輸過程中計算機的運載,在這f(x)個端口中,有g(shù)(x)個可以在任意時隙為

3、同一個作業(yè)傳輸文件.在這個環(huán)境中,要解決的問題是如何來安排文件的傳輸過程,才能使得整個過程用時最短.
　　 本文所考慮的圖在無特殊說明的情況下均為簡單、有限無向圖.對于一個圖G=(V(G),E(G)),我們分別用V(G)和E(G)表示圖的頂點集合和邊集合.圖G的頂點數(shù)｜V(G)｜我們通常稱為G的階,一般用n來表示.對任意的v∈V(G),用dG(v)表示頂點v在G中的度數(shù).△(G)和δ(G)分別表示圖G的最大度和最小度.對V(G)

4、的子集S,用G-S表示從G中刪去頂點集合S及與S關(guān)聯(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)=X∪Y,且G的所有邊均有一個端點在X內(nèi),另一個端點在Y內(nèi),則稱G為二部圖,記為G=(X,Y,E(G)).如果｜X｜=｜Y｜,則稱G為均衡二部圖.
　　 設(shè)g和f是定義在V(

5、G)上的兩個整數(shù)值函數(shù),對每個v∈V(G),都有0≤g(v)≤f(v).若H是圖G的一個支撐子圖,對任意頂點v∈V(H),滿足g(v)≤dH(v)≤f(v)那么我們稱H是圖G的一個(g,f)-因子.如果H是連通的,則稱H是G的一個連通因子.特別地,如果圖G本身是一個(g,f)-因子,則稱G為一個(g,f)-圖.設(shè)a和b是兩個非負(fù)整數(shù),如果對任意的v∈V(G),有g(shù)(v)=a,f(v)=b,則稱(g,f)-因子為[a,b]-因子.如果對每

6、個v∈V(G),有g(shù)(v)=f(v),則稱(g,f)-因子為f-因子.如果a=b=k,則稱這樣的[a,b]-因子為k-因子;當(dāng)k=1時,也稱1-因子為完美對集.對于圖G的一個因子,如果它同時包含G的一個哈密頓圈,我們就稱該因子為G的一個哈密頓因子.
　　 在以上概念的基礎(chǔ)上,我們上面提到的文件傳輸問題就可以對應(yīng)為:求G的邊集E(G)的一個劃分{F1,F2,…,Fm}.使得每個F,1≤i≤m,都是一個(g,f)-因子.并且這個劃分

7、有最小數(shù)目的(g,f)-因子.事實上,我們知道對任意一個圖而言,可能并沒有(g,f)-因子,所以我們有必要研究圖的(g,f)-因子的存在性.當(dāng)更具體實際的問題出現(xiàn)時,可能就需要圖中存在更特殊的因子,比如連通因子,本文中我們研究的圖的哈密頓(g,f)-因子就屬于連通因子的范疇.
　　 我們對于哈密頓因子問題的研究,主要有兩方面的意義.一方面,就像我們上面的敘述,這類研究可以看作是哈密頓圈問題的推廣,因此有助于我們更加深入研究哈密頓

8、圈問題.另一方面,研究哈密頓因子對我們研究連通因子也是很有幫助的,連通因子問題與哈密頓問題和實際的信息網(wǎng)絡(luò)有著密切的聯(lián)系.如果一個圖有哈密頓因子的話,那么顯然該圖有連通因子(而且是2-連通因子).事實上,這也是我們研究哈密頓因子問題的根本目的和出發(fā)點.
　　 一個圖要存在哈密頓因子,那么首先要滿足哈密頓圈存在的條件,因此我們的研究思路可以從哈密頓圈存在的條件出發(fā):從已有的一些關(guān)于哈密頓圈存在性的充分條件出發(fā)做相應(yīng)的推廣,進而得到

9、一些相關(guān)或者類似的充分條件,使得在G中存在包含某個(甚至任意一個)哈密頓圈的因子.事實上,很多學(xué)者已經(jīng)對圖的特殊哈密頓因子做了研究,并且得到了豐富的結(jié)論.這里的特殊哈密頓因子指的是g(v)=a,f(v)=b時,圖的哈密頓[a,b]-因子以及a=b=k時,圖的哈密頓k-因子.本文正是將這類特殊的哈密頓因子推廣到更一般的圖的哈密頓(g,f)-因子的研究上.
　　 我們在本文中主要研究的就是圖的哈密頓(g,f)-因子方面的一些結(jié)果.<

10、br>　　 全文共分四章,第一章簡單介紹一下圖論中的一些基本概念,并給出因子、哈密頓圈問題的歷史背景和進展?fàn)顩r以及一些已有的相關(guān)結(jié)論.這一章是后面其他各章節(jié)的基礎(chǔ).
　　 第二章我們主要討論圖的哈密頓(g,f)-因子的一些情況.主要結(jié)論為:
　　 定理2.1.3.設(shè)G=(X,Y)是頂點數(shù)為n的均衡二部圖,b≥a＞2為正整數(shù).g(x),f(x)為定義在V(G)上的非負(fù)整數(shù)值函數(shù),滿足(∨)v∈V(G),a≤g(v)≤f(

11、v)≤b,且f(X)=f(Y),(∨)vi,vj∈V(G),有f(vi)-g(vi)=f(vj)-g(vj),如果G滿足δ(G)≥(b-2)n/2(a+b-4)+2,n≥2(a+b-4)2/a-2,那么對G的任一給定的哈密頓圈C,G都有一個(g,f)-因子包含C.
　　 推論2.1.4.設(shè)G=(X,Y)是頂點數(shù)為n的均衡二部圖,b≥a＞2為正整數(shù).g(x),f(x)為定義在V(G)上的非負(fù)整數(shù)值函數(shù),滿足(∨)v∈V(G),a≤

12、g(v)≤f(v)≤b,且,f(x)=f(Y),(∨)vi,vj∈V(G),有f(vi)-g(vi)=f(vj)-g(vj),如果G滿足δ(G)≥(b-2)n/2(a+b-4)+2,n≥2(a+b-4)2/a-2,那么G有2-連通的(g,f)-因子.
　　 定理2.2.1.設(shè)正整數(shù)b＞a＞2,G是一個n階2-連通圖.g(x)和f(x)為定義在V(G)上的非負(fù)整數(shù)值函數(shù),滿足(∨)v∈V(G),a≤g(v)＜f(v)≤b.如果G滿

13、足δ(G)≥b-1,n≥2(a+b-4)2/a-3/2.且對于G中任意兩個不相鄰頂點u,v,都滿足max{dG(u),dG(v)}≥(b-5/2)n/a+b-4.那么對G的任意一個給定的哈密頓圈C,G都有一個(g,f)-因子包含C.
　　 推論2.2.2.設(shè)正整數(shù)b＞a＞2,G是一個n階2-連通圖.g(x)和f(x)為定義在V(G)上的非負(fù)整數(shù)值函數(shù),滿足(∨)v∈V(G),a≤g(v)＜f(v)≤b.如果G滿足δ(G)≥b-1

14、,n≥2(a+b-4)2/a-3/2.且對于G中任意兩個不相鄰頂點u,v,都滿足max{dG(u),dG(v)}≥(b-5/2)n/a+b-4.那么G有2-連通的(g,f)-因子.
　　 定理2.3.1.設(shè)G是一個n階2-連通圖,整數(shù)a,b滿足2≤a＜b.令g(x),f(x)是定義在V(G)上的兩個非負(fù)整數(shù)值函數(shù),使得(∨)v∈V(G),滿足a≤g(v)＜f(v)≤b.如果G滿足δ(G)≥(b-1)2-(a-1)(b-a)/a-

15、1,n＞(a+b-3)(a+b-2)/a-1,且G中任意兩個不相鄰的頂點u和v,有max{dG(u),dG(v)≥(b-1)n/a+b-2'則G有一個哈密頓(g,f)-因子.
　　 推論2.3.2.設(shè)G是一個n階2-連通圖,整數(shù)a,6滿足2≤a＜b.令g(x),f(x)是定義在V(G)上的兩個非負(fù)整數(shù)值函數(shù),使得(∨)v∈V(G),滿足a≤g(v)＜f(u)≤b.如果G滿足δ(G)≥(b-1)2-(a-1)(b-a)/a-1,n

16、＞(a+b-3)(a+b-2)/a-1,且G中任意兩個不相鄰的頂點u與V,滿足max{dG(u),dG(v)≥(b-1)n/a+b-2'則G有2-連通的(g,f)-因子.
　　 第三章則討論了圖的帶約束條件的哈密頓(g,f)-因子的一些情況,其主要結(jié)論為:
　　 定理3.0.4.設(shè)b＞a＞2是正整數(shù),G是一頂點數(shù)為n的簡單圖,g(x)和f(x)為定義在V(G)上的非負(fù)整數(shù)值函數(shù),滿足a≤g(x)＜f(x)≤b.圖G滿足n

17、≥(a+b-4)2-2(b-2)/a-2,δ(G)≥(b-2)n/(a+b-4),那么
　　 1.對G中任一給定的哈密頓圈C和邊e∈E(G),存在G的一個(g,f)-因子過e且包含C.
　　 2.對G中任一給定的哈密頓圈C和邊e(∈)E(C),存在G的一個(g,f)-因子包含C但是不包含e.
　　 推論3.0.5.設(shè)b＞a＞2是正整數(shù),G是一頂點數(shù)為n的簡單圖,g(x)和f(x)為定義在V(G)上的非負(fù)整數(shù)值函數(shù)

18、,滿足a≤g(x)＜f(x)≤b.圖G滿足n≥(a+b-4)2-2(b-2)/a-2,δ(G)≥(b-2)n/(a+b-4),那么
　　 1.對G中任意邊e∈E(G),存在G的一個2-連通的(g,f)-因子包含e.
　　 2.對G中任一給定的哈密頓圈C和邊e(∈)E(C),存在G的一個2-連通的(g,f)-因子不包含e.
　　 另外,在本文中我們提出了一些有待進一步研究的問題.
　　 在第四章中,我們對本