关于分数消去图的若干结果

摘要

图的分数因子起初是作为研究著名的基数匹配问题的工具而引入的，但后来人们发现分数因子还可以解决其他很多问题，它已经广泛地应用于网络设计、运筹学、多面体组合学等多个领域．例如：在通讯网络中，我们允许一些大的数据包通过若干个渠道发送到不同的目的地．如果我们允许把这些大的数据包分割成小的数据包，那么整个网络的效率将大大提高，而数据包的可行分割问题可以看成是分数流问题，当目的地和发送地分离时这个问题就变成了分数匹配问题，用分数因子的理论就可以解决它．
　　 分数消去图和分数临界图是分数因子概念的两种扩展．这两个方面是最近几年分数因子领域研究的重点，在前人的基础上，本文的研究和得到的结果如下：
　　 在第二章中，我们将研究分数（k，m）-消去图的度条件，得到两个相关结论，对于k≥2且m≥0是两个整数，若下面两个条件之一成立：1）n≥4k+4m-3,δ(G)≥K十m，且max{dG(u)，dG（υ）}≥n/2对每一对G中不相邻的顶点u和v成立；2）δ(G)≥k+m，σ2(G)≥n，n≥4k十4m-5若（k，m）≠(3，o)或n≥8若（k，m）=(3，0)．则G是分数（k，m）-消去图，同时我们将说明结论是最好可能的．
　　 在第三章中，我们首先证明对k≥2且m≥0是两个整数，且n≥8k+4m-7，δ(G)≥k十m，若|NG(X)∪NG(y)|≥n/2对每一对G中不相邻的顶点x和y成立，则G是分数（k，m）-消去图．并说明邻域并条件，G的阶条件和最小度条件都是紧的．其次，将分数（k，m）-消去图的概念扩展到分数（g，f，m）-消去图，并得到一个图是分数(g，f，m)-消去图的充分必要条件．最后考虑分数(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是分数（g，f,m）-消去图．更进一步，我们将说明邻域条件是最好可能的．
　　 在第四章中，我们将分数临界图和分数消去图的概念进行组合，提出分数临界消去图的概念，给出图G是分数（g，f，n’，m）-临界消去图的充要条件，并得到若干推论，由此我们从邻域并，邻集，独立数等角度出发，给出一个图是分数临界消去图的若干充分条件．
　　 在第五章中，我们将研究分数（k，n’）-临界消去图的两类韧度条件，证明：1）当I(G)>K（n’+1），且δ(G)≥K(n’+1)+1时，G是分数(k，n')-临界消去图；2）当T(G)≥（K2—1)(n'+1），且n>k十n’+1时，G是分数（k，n’）-临界消去图．
　　 在第六章中，我们将研究分数（g,f,n'm）-临界消去图的联结数条件，并得到若干结果：1）a，b，n’，m均为非负整数且2≤a≤6．设g，f是定义在V(G)上的两个整数实值函数且对所有z∈V(G)满足a≤g(x)≤f(x)≤b．若bind(G)(a+b-1)(n-1)/an-(a+b)-bn'-2m+2且n≥(a+b)(a+b-3)/a+bn'+2m/a-1，则G是分数（g，f，n’,m）-临界消去图；2)a，b，n’，m是非负整数满足2≤a≤b，n≥（a+b一1）(a+b-2）/a+bn'+2m/a-1．设g，f是定义在V(G)上的两个整数实值函数且对所有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'+2m-2/a+b-1],则G是分数(g，f，n’，m)-临界消去图．

目录

声明

摘要

第一章 绪论

1.1 关于分数消去图和临界图的若干进展

1.2 本文主要结果

第二章 分数(k,m)-消去图的度条件

2.1 预备知识和结果

2.2 定理2.1.8的证明

2.3 定理2.1.9的证明

第三章 分数消去图的邻域并条件

3.1 主要结论及证明

3.2 概念的扩展和一个相关结论

第四章 分数临界消去图

4.1 分数(g,f,n′,m)-临界消去图的充要条件

4.2 分数(k,n′,m)-临界消去图的邻域并条件

4.3 分数(g,f,n′,m)-临界消去图的邻集条件

4.4 分数(g,f,n′,m)-临界消去图的两个充分条件

第五章 分数(k,n′)-临界消去图的韧度条件

5.1 孤立韧度与分数(k,n′)-临界消去图

5.2 韧度与分数(k,n′)-临界消去图

第六章 分数临界消去图的联结数条件

6.1 联结数与分数(g,f,n′,m)-临界消去图

6.2 定理6.1.8的证明

6.3 定理6.1.9的证明

进一步研究的问题

参考文献