图的因子和分数因子

摘要

图是建立各种数学模型的强有力的工具.对图论的研究已经有二百多年的历史.最早关于图论的文章是在1736年由欧拉完成的,该文章研究了著名的哥尼斯堡七桥问题.自20世纪60年代以来,图论得到迅猛发展,关于图论的结果大量涌现.图论在各个学科分支,工程技术领域及社会科学有着广泛的应用.应用图论来解决运筹学,物理学,化学,生物学,网络理论,信息论,控制论,博弈论和计算机科学等学科问题已显示出极大的优越性.图论已经成为发展最快的数学分支之一.它作为组合数学中的一个分支,受到了各方面的普遍重视.
　　 因子理论作为图论的一个重要分支,在图论研究中得到了极大关注.在日常生活中,许多优化问题和网络问题诸如编码设计,积木设计,计算机网络的文件传输,进度表等关于运筹和网络设计问题都涉及到图的因子,因子分解和正交因子[1].其中,文件传输问题可以模拟为因子和(0,f)-因子分解(或f-染色),拉丁方块和空间方块的设计则涉及到图的因子和正交因子问题.本文我们主要研究图的因子和分数因子以及它们所关联的一些性质特征.
　　 本文所考虑的图都是有限简单图.设G是一个图,V(G)是顶点集,E(G)是边集.对v∈V(G),v在G中的度用dG(v)表示.我们用NG(v)表示在G中与v相邻的顶点集合,NG[v]表示NG(v)u{v｝.如果s是V(G)的一个子集,方便起见,我们用dG(s)代替(∑)dG(v).如果u∈V(G)-S,我们用eG(u,S)表示连接u和S中点的边的数目.G-S表示由V(G)＼S导出的子图,G[S]表示由S导出的子图.若Т∈V(G)-S,我们用eG(Т,S)代替(∑)eG(u,S).图G的边割是E(G)的子集[S,V(G)＼S],其中s是V(G)的非空子集.κ-边割是有κ个元素的边割.G的边连通度λ(G)是使得G有κ-边割的最小的κ.G称为κ-边连通的若λ(G)≥κ.图G的点割是V(G)的子集S,使得G-S是不连通的.κ-点割是有κ个元素的点割.G的连通度κ(G)是使得G有κ-点割的最小的κ.图G称为是κ-连通的若κ(G)≥κ.
　　 令g和f是两个整值函数且对所有x∈V(G),0≤g(x)≤f(x).图G的(g,f)-因子F是G的支撑子图且对所有x∈V(G),满足g(x)≤dF(X)≤f(x).若对任意x∈V(G),g(x)=f(z),则(g,f)-因子称为f-因子.对非负整数κ和所有x∈V(G),若f(x)=κ,则f-因子称为κ-因子.特别的,若对任意x∈V(G),g(x)=f(x)=1,(g,f)-因子称为1-因子,即完美对集.图G的完美对集可参见[17].
　　 对图的因子的研究始于一百多年以前.1859年,Reiss证明了κ2n可被分解成1-因子.1891年,J.Peterson证明了任意偶数度图可以分解成边不交2-因子的并.他还指出2-连通3-正则图有1-因子.这两个结果可被认为是现代因子理论的先驱.为了将对集理论从二分图推广到一般图(即非二分图),1947年Tutte[85]给出图有1-因子的判定准则.这个完美的理论或许是因子理论中最基础的结果.1952年Tutte[86]又给出了图有f-因子的判定准则.Lovász[68]得到了图有(g,f)-因子的充分必要条件.从此,关于因子的大量结果不断涌现出来.
　　 分数(g,f)-示性函数h是一个函数分配给图G的每一条边一个[0,1]之间的数使得对每一个点x∈V(G)有g(x)≤dGh(x)≤f(x),其中dGh(x)=∑e∈Exh(e)是点x∈V(G)的分数度,且Ex={e:e=xy∈E(G)｝.令h是图G的分数(g,f)-示性函数.令Eh={e:e∈E(G)且h(e)≠0}.若Gκ是G的支撑子图使得E(Gh)=Eh,则Gh称为G的(g,f)-因子.当对任意x∈V(G),g(x)=O且f(x)=1,则这个分数示性函数是分数对集的示性函数.若g(x)=f(x)=κ,则分数(g,f)-因子称为分数κ-因子.当对任意x∈V(G),g(x)=f(x)=1,则分数示性函数是分数完美对集的示性函数,即分数1-因子.
　　 分数图论是相对年轻的分支.关于这方面的第一本专著是由ClaudeBerge[14]在1978年写的分数图论.1997年E.R.Scheinerman和D.H.Ullman写了一本新的分数图论教材,其中包括分数匹配,分数边着色,分数着色和分数同构等几乎所有分数图论所涉及的内容.在图论中遇到的整数值常量几乎都可以给出它的类似的分数形式.
　　 本文分为四章,主要讨论了三个方面的问题.(1)联结数和图的因子的关系；(2)韧度和图的因子的关系；(3)独立集可去的因子临界图.
　　 第一章我们给出了简短的但较完整关于图的因子和分数因子的综述.
　　 图G的联结数定义是由Woodall给出的,
　　 许多作者研究了图的联结数和因子存在性的关系.第二章我们分三部分来研究联结数和图的因子的关系.第一部分讨了论联结数和图的(g,f)-因子,分数f-因子以及κ1,n-图中的f-因子之间的关系.第二部分讨论当a　　 定理2.2.5设G是一个图,g和f定义在V(G)上的正整值函数满足对所有x∈V(G),a≤g(x)　　 和定理2.2.5类似,我们得到联结数和分数f-因子之间的关系.
　　 定理2.2.6设G是一个图,f定义在V(G)上的正整值函数且满足对所有x∈V(G),a≤f(x)≤b.如果bind(G)≥(a+b)2+2(b-a)+1/4a,其中a,b是两个正整数,则G有分数f-因子.
　　 接着我们讨论了κ1,n-自由图中的f-因子
　　 定理2.2.7设G是一个κ1,n-自由图,f定义在V(G)上的正整值函数使得对所有x∈V(G),2≤n-1≤a≤f(x)≤b.如果∑x∈V(G)f(x)≡O(mod2),bind(G)≥(a+b-1)2+4(b+n)/4(a-n),其中a,b是两个正整数,则G有f-因子.
　　 对图的[a,b]-因子,其中2≤a　　 定理2.3.1令a,b是非负整数且2≤a　　 我们还得到了分数κ-因子存在的联结数条件并且这些结果在某种意义下是最好的.
　　 定理2.4.2令κ是正整数且κ≥2.设G是一个连通图且｜V(G)｜≥κ+2.如果bind(G)≥κ-1/k,则G有分数κ-因子.
　　 Chvátal[19]第一次介绍了韧度的概念,记作
　　 其中ω(G-S)表示G-S中的分支数且G是非完全图.若G是完全图,则t(G)=∞.
　　 随后许多学者研究了韧度与哈密尔顿圈或因子的关系.刘桂真,马英红[72]定义了图的另一个参数-孤立韧度
　　 其中i(G-S)记为G-S的孤立顶点数且G是非完全图.若G是完全图,则I(G)=∞.显然I(G)≥t(G).
　　 第三章我们讨论了韧度和因子之间的关系.首先我们给出韧度和具有指定性质的(g,f)-因子之间的关系.接着讨论了韧度和具有指定性质的[a,b]-因子之间的关系,我们还给出了(a,b,κ)-临界图的孤立韧度条件.
　　 定理3.2.1设G是一个图,g和f是定义在V(G)上的正整值函数使得对所有x∈V(G),a≤g(x)a>2,则G存在一个包含e1和e2的(g,f)-因子.
　　 定理3.2.2设G是一个图,g和f是定义在V(G)上的正整值函数使得对所有x∈V(G),a≤g(x)a>2,则G存在一个(g,f)-因子包含e1且不包含e2.
　　 定理3.2.3设G是一个图,g和f是定义在V(G)上的正整值函数使得对所有x∈V(G),a≤g(x)a>2,则G存在一个(g,f)-因子不包含e1和e2.

目录

文摘

英文文摘

符号说明

第一章 绪论

1.1 基本定义和符号

1.2 关于图的因子的历史及其进展

1.3 关于分数因子的历史及其进展

第二章 联接数和图的因子

2.1 介绍

2.2 联结数和图的(g,f)-因子

2.2.1 联结数和(g,f)-因子

2.2.2 联结数和K1,n-自由图中的f-因子

2.3 联结数和图的[a,b]-因子

2.4 联结数和图的分数k-因子

第三章 韧度和图的因子

3.1 介绍

3.2 韧度和图中具有指定性质的(g,f)-因子

3.2.1 主要结果和有用的引理

3.2.2 主要定理的证明

3.3 韧度和图的具有指定性质的[a,b]-因子

3.3.1 主要结果和有用引理

3.3.2 主要定理的证明

3.4 孤立韧度和(a,b,k)-临界图

第四章 独立集可去的分数k-因子临界图

4.1 介绍

4.2 主要结果

4.3 说明

参考文献

致谢

作者简介

学位论文评阅及答辩情况表