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

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

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

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

4、的子集S,用G-S表示從G中刪去頂點(diǎn)集合S及與S關(guān)聯(lián)的邊所得到的子圖.若S={v},則令G-v=G-{v}.對(duì)E(G)的子集X,用G-X表示從G中刪去邊集合X所得的子圖.若X={e},則G-{e}簡(jiǎn)記為G-e.若存在V(G)的兩個(gè)不交子集X和Y,使得V(G)=X∪Y,且G的所有邊均有一個(gè)端點(diǎn)在X內(nèi),另一個(gè)端點(diǎn)在Y內(nèi),則稱G為二部圖,記為G=(X,Y,E(G)).如果｜X｜=｜Y｜,則稱G為均衡二部圖.
　　 設(shè)g和f是定義在V(

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

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

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

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

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

10、br>　　 全文共分四章,第一章簡(jiǎn)單介紹一下圖論中的一些基本概念,并給出因子、哈密頓圈問(wèn)題的歷史背景和進(jìn)展?fàn)顩r以及一些已有的相關(guān)結(jié)論.這一章是后面其他各章節(jié)的基礎(chǔ).
　　 第二章我們主要討論圖的哈密頓(g,f)-因子的一些情況.主要結(jié)論為:
　　 定理2.1.3.設(shè)G=(X,Y)是頂點(diǎn)數(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,那么對(duì)G的任一給定的哈密頓圈C,G都有一個(gè)(g,f)-因子包含C.
　　 推論2.1.4.設(shè)G=(X,Y)是頂點(diǎn)數(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是一個(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.且對(duì)于G中任意兩個(gè)不相鄰頂點(diǎn)u,v,都滿足max{dG(u),dG(v)}≥(b-5/2)n/a+b-4.那么對(duì)G的任意一個(gè)給定的哈密頓圈C,G都有一個(gè)(g,f)-因子包含C.
　　 推論2.2.2.設(shè)正整數(shù)b＞a＞2,G是一個(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.且對(duì)于G中任意兩個(gè)不相鄰頂點(diǎn)u,v,都滿足max{dG(u),dG(v)}≥(b-5/2)n/a+b-4.那么G有2-連通的(g,f)-因子.
　　 定理2.3.1.設(shè)G是一個(gè)n階2-連通圖,整數(shù)a,b滿足2≤a＜b.令g(x),f(x)是定義在V(G)上的兩個(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中任意兩個(gè)不相鄰的頂點(diǎn)u和v,有max{dG(u),dG(v)≥(b-1)n/a+b-2'則G有一個(gè)哈密頓(g,f)-因子.
　　 推論2.3.2.設(shè)G是一個(gè)n階2-連通圖,整數(shù)a,6滿足2≤a＜b.令g(x),f(x)是定義在V(G)上的兩個(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中任意兩個(gè)不相鄰的頂點(diǎn)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是一頂點(diǎn)數(shù)為n的簡(jiǎ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.對(duì)G中任一給定的哈密頓圈C和邊e∈E(G),存在G的一個(gè)(g,f)-因子過(guò)e且包含C.
　　 2.對(duì)G中任一給定的哈密頓圈C和邊e(∈)E(C),存在G的一個(gè)(g,f)-因子包含C但是不包含e.
　　 推論3.0.5.設(shè)b＞a＞2是正整數(shù),G是一頂點(diǎn)數(shù)為n的簡(jiǎ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.對(duì)G中任意邊e∈E(G),存在G的一個(gè)2-連通的(g,f)-因子包含e.
　　 2.對(duì)G中任一給定的哈密頓圈C和邊e(∈)E(C),存在G的一個(gè)2-連通的(g,f)-因子不包含e.
　　 另外,在本文中我們提出了一些有待進(jìn)一步研究的問(wèn)題.
　　 在第四章中,我們對(duì)本