關(guān)于分?jǐn)?shù)消去圖的若干結(jié)果.pdf

1、圖的分?jǐn)?shù)因子起初是作為研究著名的基數(shù)匹配問題的工具而引入的，但后來人們發(fā)現(xiàn)分?jǐn)?shù)因子還可以解決其他很多問題，它已經(jīng)廣泛地應(yīng)用于網(wǎng)絡(luò)設(shè)計(jì)、運(yùn)籌學(xué)、多面體組合學(xué)等多個(gè)領(lǐng)域．例如：在通訊網(wǎng)絡(luò)中，我們?cè)试S一些大的數(shù)據(jù)包通過若干個(gè)渠道發(fā)送到不同的目的地．如果我們?cè)试S把這些大的數(shù)據(jù)包分割成小的數(shù)據(jù)包，那么整個(gè)網(wǎng)絡(luò)的效率將大大提高，而數(shù)據(jù)包的可行分割問題可以看成是分?jǐn)?shù)流問題，當(dāng)目的地和發(fā)送地分離時(shí)這個(gè)問題就變成了分?jǐn)?shù)匹配問題，用分?jǐn)?shù)因子的理論就可以解決

2、它．
　　 分?jǐn)?shù)消去圖和分?jǐn)?shù)臨界圖是分?jǐn)?shù)因子概念的兩種擴(kuò)展．這兩個(gè)方面是最近幾年分?jǐn)?shù)因子領(lǐng)域研究的重點(diǎn)，在前人的基礎(chǔ)上，本文的研究和得到的結(jié)果如下：
　　 在第二章中，我們將研究分?jǐn)?shù)（k，m）-消去圖的度條件，得到兩個(gè)相關(guān)結(jié)論，對(duì)于k≥2且m≥0是兩個(gè)整數(shù)，若下面兩個(gè)條件之一成立：1）n≥4k+4m-3,δ(G)≥K十m，且max{dG(u)，dG（υ）}≥n/2對(duì)每一對(duì)G中不相鄰的頂點(diǎn)u和v成立；2）δ(G)≥k+m，

3、σ2(G)≥n，n≥4k十4m-5若（k，m）≠(3，o)或n≥8若（k，m）=(3，0)．則G是分?jǐn)?shù)（k，m）-消去圖，同時(shí)我們將說明結(jié)論是最好可能的．
　　 在第三章中，我們首先證明對(duì)k≥2且m≥0是兩個(gè)整數(shù)，且n≥8k+4m-7，δ(G)≥k十m，若|NG(X)∪NG(y)|≥n/2對(duì)每一對(duì)G中不相鄰的頂點(diǎn)x和y成立，則G是分?jǐn)?shù)（k，m）-消去圖．并說明鄰域并條件，G的階條件和最小度條件都是緊的．其次，將分?jǐn)?shù)（k，m）-消

4、去圖的概念擴(kuò)展到分?jǐn)?shù)（g，f，m）-消去圖，并得到一個(gè)圖是分?jǐn)?shù)(g，f，m)-消去圖的充分必要條件．最后考慮分?jǐn)?shù)(g,f，m)-消去圖的鄰域并條件，證明若a≤g(x)≤f(x)≤b對(duì)所有x∈V(G)成立，δ(G)≥b2（i-1）/a+2m，n>（a+b)(i(a+b)+2m-2)/a，且|NG(X1)∪…∪NG(Xi)|≥bn/a+b對(duì)所有V(G)的獨(dú)立集{X1，X2，…，xi）成立，這里i≥2，則G是分?jǐn)?shù)（g，f,m）-消去圖．更進(jìn)一

5、步，我們將說明鄰域條件是最好可能的．
　　 在第四章中，我們將分?jǐn)?shù)臨界圖和分?jǐn)?shù)消去圖的概念進(jìn)行組合，提出分?jǐn)?shù)臨界消去圖的概念，給出圖G是分?jǐn)?shù)（g，f，n’，m）-臨界消去圖的充要條件，并得到若干推論，由此我們從鄰域并，鄰集，獨(dú)立數(shù)等角度出發(fā)，給出一個(gè)圖是分?jǐn)?shù)臨界消去圖的若干充分條件．
　　 在第五章中，我們將研究分?jǐn)?shù)（k，n’）-臨界消去圖的兩類韌度條件，證明：1）當(dāng)I(G)>K（n’+1），且δ(G)≥K(n’+1)+

6、1時(shí)，G是分?jǐn)?shù)(k，n')-臨界消去圖；2）當(dāng)T(G)≥（K2—1)(n'+1），且n>k十n’+1時(shí)，G是分?jǐn)?shù)（k，n’）-臨界消去圖．
　　 在第六章中，我們將研究分?jǐn)?shù)（g,f,n'm）-臨界消去圖的聯(lián)結(jié)數(shù)條件，并得到若干結(jié)果：1）a，b，n’，m均為非負(fù)整數(shù)且2≤a≤6．設(shè)g，f是定義在V(G)上的兩個(gè)整數(shù)實(shí)值函數(shù)且對(duì)所有z∈V(G)滿足a≤g(x)≤f(x)≤b．若bind(G)(a+b-1)(n-1)/an-(a+b)

7、-bn'-2m+2且n≥(a+b)(a+b-3)/a+bn'+2m/a-1，則G是分?jǐn)?shù)（g，f，n’,m）-臨界消去圖；2)a，b，n’，m是非負(fù)整數(shù)滿足2≤a≤b，n≥（a+b一1）(a+b-2）/a+bn'+2m/a-1．設(shè)g，f是定義在V(G)上的兩個(gè)整數(shù)實(shí)值函數(shù)且對(duì)所有z∈V(G)滿足a≤g(x)≤f(x)≤b．若G滿足bind(G)≥(a+b-1)(n-1)/a(n-1)-bn'-2m，且δ(G)≠』(b-1)n+a+b+bn