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

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

2、它．
　　 分數(shù)消去圖和分數(shù)臨界圖是分數(shù)因子概念的兩種擴展．這兩個方面是最近幾年分數(shù)因子領(lǐng)域研究的重點，在前人的基礎(chǔ)上，本文的研究和得到的結(jié)果如下：
　　 在第二章中，我們將研究分數(shù)（k，m）-消去圖的度條件，得到兩個相關(guān)結(jié)論，對于k≥2且m≥0是兩個整數(shù)，若下面兩個條件之一成立：1）n≥4k+4m-3,δ(G)≥K十m，且max{dG(u)，dG（υ）}≥n/2對每一對G中不相鄰的頂點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是分數(shù)（k，m）-消去圖，同時我們將說明結(jié)論是最好可能的．
　　 在第三章中，我們首先證明對k≥2且m≥0是兩個整數(shù)，且n≥8k+4m-7，δ(G)≥k十m，若|NG(X)∪NG(y)|≥n/2對每一對G中不相鄰的頂點x和y成立，則G是分數(shù)（k，m）-消去圖．并說明鄰域并條件，G的階條件和最小度條件都是緊的．其次，將分數(shù)（k，m）-消

4、去圖的概念擴展到分數(shù)（g，f，m）-消去圖，并得到一個圖是分數(shù)(g，f，m)-消去圖的充分必要條件．最后考慮分數(shù)(g,f，m)-消去圖的鄰域并條件，證明若a≤g(x)≤f(x)≤b對所有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對所有V(G)的獨立集{X1，X2，…，xi）成立，這里i≥2，則G是分數(shù)（g，f,m）-消去圖．更進一

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

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