一、3限制边连通度与正则因子（论文文献综述）
王函[1]（2015）在《彼得森对图因子理论的贡献》文中研究表明图论自1736年诞生之日起,在200多年的发展进程中,数学家们围绕着名的“四色问题”展开研究。20世纪以来,随着图论与其他学科的相互融合,涌现了诸如代数图论、概率图论、随机图论等众多新的学科交叉分支。图因子理论就是代数图论的范畴,主要研究一般图具有图因子的图特征问题。丹麦数学家彼得森的独创性思维和学科交叉思想致使他创作出第一篇包含图论方面（图因子理论）基本结论的文章《正则图理论》,其在图因子理论的工作被认为是具有开创性的。本文在整理、研读、分析文献的基础上,结合图因子理论发展历史,以彼得森三篇图论文章为核心展开具体研究,系统分析了彼得森解决问题的创新思维和学科交叉思想。全文主要讨论了以下问题:1.详细介绍了彼得森的生平。彼得森是19世纪下半叶丹麦数学的领军人物之一,虽生活艰苦,但不忘数学研究。独特的创造性和优雅的教学态度,使其一生受到尊重,享有国际荣誉。2.概述了图因子理论形成的学术背景。（1）泰特对“四色问题”的研究使得1-因子凸显出来。（2）西尔维斯特将形象直观的“图”应用于不变量理论的研究中,其方法为彼得森提供了创造性思维的来源。3.深究了彼得森在图因子理论的工作。以彼得森的三篇图论文章为核心展开细致研究,分析了《正则图理论》的创作初衷、研究框架及主要结论。重点剖析了彼得森的两个定理,简要分析了作为泰特“定理”反例给出的彼得森图以及彼得森在3-正则图的工作。4.阐述了彼得森对图因子理论后续发展的影响。回溯并分析了受彼得森工作影响的柯尼希、门格尔、霍尔、塔特在图因子理论的重要工作,揭示彼得森的工作在图因子理论后续发展的重要影响,进而更加明确了彼得森工作的开创性地位。
刘红霞[2]（2010）在《图参数与图的因子》文中指出二十世纪六十年代以来,图论作为年轻的数学分支,获得了空前的发展.图论在物理学、化学、生物学、网络理论、信息科学、计算机科学等学科有着极其广泛的应用.它作为组合数学的一个分支,受到了各方面的普遍重视.本文研究图的因子理论.因子理论是图论的一个重要分支,在很多领域有着广泛的应用.如计算机网络中的文件传输问题、时间表问题等等都涉及到图的因子、因子分解和正交因子分解.本文我们主要研究图的参数和图的因子、分数因子、临界图和连通因子的关系.本文中所考虑的图均为无向简单图.设G是一个具有顶点集V（G）和边集E（G）的图.对x∈V（G）,x在G中的度用dG（x）表示.我们用NG（x）表示在G中与x相邻的顶点集合.用δ（G）表示图G的最小度.如果S是V（G）的一个子集,用NG（S）表示∑x∈S NG（x）,用G[S]表示G中S的导出子图,用G-S表示G中去掉S中的点以及所有与S相关联的边的集合.若S,T （?）V（G）,我们用eG（S,T）表示S中的点与T中的点关联的边数.连通图G的点割是V（G）的子集S使得G-S不连通. k-点割是有k个元素的点割. G的连通度κ（G）是使得G有k-点割的最小的k.图G称作是k-连通的如果κ（G）≥k.图G的边割是E（G）的子集[S,V（G）＼S]其中S是V（G）的非空子集.k-边割是有k个元素的边割.G的边连通度λ（G）是使得G有k-边割的最小的k.G称为是k-边连通的若λ（G）≥k.设g（x）和f（x）是定义在V（G）上的两个非负整数值函数使得对所有的x∈V（G）,g（x）≤f（x）.图G的（g,f）-因子F是G的支撑子图且对所有的x∈V（G）,满足g（x）≤dF（x）≤f（x）.如果对任意的x∈V（G）,g（x）=f（x）,则（g,f）-因子称作f-因子.设a和b是两个非负整数满足0≤a≤b.若对所有x∈V（G）,g（x）≡a且f（x）≡b,则（g,f）-因子称作[a,b]-因子.若a=b=k,则[a,b]-因子称作k-因子,也称为正则因子.特别的,若对任意的x∈V（G）,g（x）=f（x）=1,（g,f）-因子称为1-因子,即完美匹配.对图的因子的研究最早归功于丹麦数学家Petersen （1891）.他证明了任意偶数度图可以分解成边不交2-因子的并.而且他证明了每一个2-连通三次图都有一个1-因子.这两个结果被认为是现代图因子理论的先驱.对于二部图的匹配,Konig （1931）和Hall（1935）给出了Konig-Hall定理（有时也称为Hall定理）.1947年Tutte[115]给出了图的完美匹配存在性的判别性准则（即Tutte1-因子定理）,这个定理成为了因子理论的基石.直到现在,这个优美的定理仍然是因子理论中最基本的结果之一.随后,1952年Tutte[116]推广了1-因子定理的证明技巧,给出了图有f-因子的充分必要条件.Lovasz[86]（1970）研究了最一般度约束条件因子和（g,f）-因子,并给出了图有（g,f）-因子的充分必要条件.这个结论是所有其它因子存在性准则的推广,如1-因子, k-因子,f-因子和[a,b]-因子.从此,关于因子的结果大量涌现出来.若对任意的N （?） V（G）满足|N|=n,G-N有一个（g,f）-因子,则称图G是（g,f,n）-临界图.若对所有的x∈V（G）,g（x）≡a且f（x）≡b,则称（g,f,n）-临界图为（a,b,n）-临界图.即任意去掉G中n个顶点后,剩下的图仍然有一个[a,b]-因子,则称图G为（a,b,n）-临界图.若a=b=k,则（a,b,n）-临界图为（k,n）-临界图.若k=1,则（k,n）-临界图简称为n-临界图.因子临界图是因子理论的延伸.Plummer [101]和Lovasz [85]研究了2-临界图的性质.Yu[130]研究了n-临界图.Liu与Yu研究了（k,n）-临界图.Liu和Wang [72]给出了当a<b时（a,b,n）-临界图存在性的充要条件.其它相关结论参见[3,131].分数（g,f）-示性函数h是一个取值于[0,1]之间的函数,它分配给图G的每条边一个数使得对每一个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}.若Gh是G的支撑子图使得E（Gh）=Eh,则Gh称作是G的分数（g,f）-因子.当对任意的x∈V（G）,g（x）=f（x）,称分数（g,f）-因子为分数f-因子.若对所有x∈V（G）,g（x）≡a且f（x）≡b,则称分数（g,f）-因子为分数[a,b]-因子.若a=b=k,则分数[a,b]-因子为分数k-因子.分数图论是图论的实数化的一面.目前,分数图论仍然是相对年轻的分支.1978年,Claude Berge[8]最早介绍并研究了分数图论.1997年E. R. Scheinerman和D.H.Ullman写了一本新的分数图论[110],这本专着几乎涵盖了现代分数图论的所有方面,其中包括分数匹配、分数边着色、分数着色、分数荫度和分数同构等分数图论所涉及的内容.他们将整值的定义和变量转换为分数形式.分数图论是研究各种图论问题的一个重要工具.许多在（整值）图论中未解决的问题或猜想能够在分数图论中被解决.1993年,M. Kano[48]提出了一些关于连通因子的问题和猜想.由于连通因子问题与哈密顿问题和信息网络密切相关,很多学者致力于图有连通因子的充分条件的研究.相关结论可参见.哈密顿圈的结论可见.图参数对于研究图的因子是非常重要的,经常用在因子存在性的充分条件中.由于图参数非常易于用来从不同方面证明和体现图的性质和结构,所以图论中经常研究图与各种参数的关系.这些结果主要与下列常用参数有关,如邻域、联结数、最小度、独立数、韧度、连通度等等.本文分为五章,从不同方面研究图参数与因子的关系.（1）图的（g,f）-因子；（2）（g,f,n）-临界图；（3）图的分数因子；（4）图的连通因子.第一章我们简述了图的因子、分数因子、临界图和连通因子.第二章我们研究图有（g,f）-因子的关于邻域的充分条件.本章分为两部分.第一部分讨论图有（g,f）-因子的邻域并条件.这一部分的结论在某种意义下是最好可能的.第二部分研究哈密顿（g,f）-因子和邻域并的关系.我们可以举例说明这一部分的结论在一定意义下是最好可能的.定理2.1.6.设G是阶为n的图,1≤a<b为整数.设g（x）和f（x）是定义在V（G）上的非负整值函数满足对任意的x∈V（G）都有a≤g（x）<f（x）≤b.设k≥2为不大于G的独立数的正整数.若且对V（G）的任意独立子集{x1,x2,...xk)都有则G有（g,f）-因子.定理2.2.3.设G是阶为n的2-连通图,a和b为整数满足a≥3且b≥2a-1.设g（x）和f（x）是定义在V（G）上的非负整值函数满足对任意的x∈V（G）都有a≤g（x）<f（x）≤b.若且对于G的任意不相邻的两个顶点x和y都有则G有哈密顿（g,f）-因子.第三章我们研究（g,f,n）-临界图和（a,b,n）-临界图存在性的充分条件.本章分为两部分.首先给出了（a,b,n）-临界图和（g,f,n）-临界图关于联结数和最小度存在性的若干充分条件.其次,我们给出了（a,b,n）-临界图和（g,f,n）-临界图关于邻集存在性的若干结论.文中指出一些结论在一定意义下是最好可能的,并且是一些已知的[a,b]-因子结论的推广.定义图G的联结数如下：定理3.1.4.设G是阶为p的图, a,b和n是非负整数且满足1≤a<b,p≥b+3a+2n.令λ1=（（a+b-1）（b+3a+2n））/（b2+3ab+bn）.若bind（G）≥λ1,且δ（G）≥1+（（a-1）p+bn）/（a+b-1）,则G是（a,b,n）-临界图.我们将定理3.1.4推广到（g,f,n）-临界图的情形.定理3.1.5.设G是阶为p的图, a,b和n是非负整数且满足1≤a<b,p≥（b（b+3a+2n））/（a+1）.设g（x）和f（x）是定义在V（G）上的非负整值函数满足对任意的x∈V（G）都有a≤g（x）<f（x）≤b.令λ2=（（a+b-1）（b+3a+2n））/（（a+1）（b+3a+n））.若bind（G）≥λ2,且δ（G）≥1+（（b-2）p+bn）/（a+b-1）,则G是（g,f,n）-临界图.定理3.2.3.设G是阶为p的图,a,b和n是非负整数且满足2≤a<b,p≥6a+b+n.令λ=（a-1）/b.如果对任意子集X （?） V（G）.都有若或若则G是（a,b,n）-临界图.我们将定理3.2.3推广到（g,f,n）-临界图的情形.定理3.2.4.设G是阶为p的图,a,b和n是非负整数且满足2≤a<b,设g（x）和f（x）是定义在V（G）上的非负整值函数满足对任意的x∈V （G）都有a≤g（x）<f（x）≤b.令λ’=b/（a+1）.如果对任意子集X （?） V（G）,都有若或若则G是（g,f,n）-临界图.第四章我们研究分数因子.本章分为两节,第一节我们给出了图有分数f-因子的一个邻域条件.这个条件在在某种意义下是最好的.第二节我们给出了分数（g,f,n）-临界图关于参数独立数和最小度存在性的若干充分条件.目前关于这一问题的研究还非常少,因此本节的结论具有相当的创新性.更进一步地,我们指出本节的结论在一定意义下是最好的并且是一些已知的分数,一因子结论的推广.定理4.1.5.设G是阶为n的图,1≤a≤b为整数,f（x）是定义在V（G）上的非负整值函数且满足对任意的x∈V（G）都有a≤f（x）≤b.设k为不大于G的独立数的正整数.如果δ（G）≥（b2（k-1））/a,n>（（a+b）（k（a+b）-2））/a,且对于V（G）的任意独立子集{x1,x2,...xk)都有其中k≥2,则G有分数f-因子.定理4.2.5.设G是一个图,a,b和n是非负整数,a≤b.设g（x）和f（x）是定义在V（G）上的非负整值函数且满足对任意的x∈V（G）都有a≤g（x）≤f（x）≤b.若δ（G）≥b,独立数α（G）≤（4（a（δ-b+1）-bn））/（（b+1）2）,则G是分数（g,f,n）-临界图.第五章我们讨论图的连通因子.判断一个图是否有连通因子是一个NP-完全问题.因为一个连通的2-因子就是一个哈密顿圈,所以连通因子问题与哈密顿问题密切相关.我们给出了图有连通的（g,f）-因子和哈密顿（g,f）-因子的关于邻域并和邻集的若干充分条件.我们的结果是一些已知结论的推广.定理5.1.4设k≥3为整数, G是阶为n的2-连通图, n>（9k2-8k-3）/（k-2）,且b（G）≥k.如果对于V（G）的任意两个不相邻的顶点u和v都有则G有哈密顿[k,k+1]-因子.定理5.2.4.设G是阶为n的图,a,b和n是非负整数满足2≤a≤b,n≥（（a+b-3）2）/（a-1）.设g（x）和f（x）是定义在V（G）上的非负整值函数满足对任意的x∈V（G）都有a≤g（x）<f（x）≤b.令λ’=（b-1）/（a-1）.如果对于任意的子集X（?）V（G）都有若或若则G有哈密顿（g,f）-因子.
蔡建生[3]（2007）在《图的因子和分数因子》文中研究说明二十世纪六十年代以来，图论获得了空前的发展。应用图论来解决物理学、化学、生物学、网络理论、心理学、计算机科学等学科问题已显示出极大的优越性。因子理论是图论的一个重要分支，在图论研究中得到极大关注。在日常生活中，许多优化问题和网络问题诸如计算机网络中的文件传输问题、时间表问题等等都涉及到图的因子、因子分解和正交因子分解[1，6]。文件传输问题可以模拟为因子和（0，f）-因子分解（或f-染色）。本文我们主要研究图的因子、分数因子和连通因子。本文中所考虑的图均为无向简单图。设G是一个具有顶点集V（G）和边集E（G）的图。对v∈V（G），v在G中的度用dG（v）表示。我们用NG（v）表示在G中与v相邻的顶点集合，NG[v]表示N+G（v）∪{v}。如果S是V（G）的一个子集，为了方便，我们用dG（S）代替sum from v∈S to dG（v）。如果u∈V（G）＼S，我们用eG（u，S）表示连接u和S中的一点的边的数目。若T（?）V（G）＼S，我们用eG（T，S）代替sum from u∈T to eG（u，S）。对V（G）的一个子集S，用G-S表示由V（G）＼S导出的子图，用G[S]表示由S导出的子图。连通图G的点割是V（G）的子集S使得G-S不连通。k-点割是有k个元素的点割。G的连通度k（G）是使得G有k-点割的最小的k。图G称作是k-连通的如果k（G）≥k。图G的边割是E（G）的子集[S，V（G）＼S]，其中S是V（G）的非空子集。k-边割是有k个元素的边割。G的边连通度λ（G）是使得G有k-边割的最小的k。G称为是k-边连通的若λ（G）≥k。令g和f是定义在V（G）上的两个整数值函数使得对所有的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（x），则（g，f）-因子称作f-因子。若f（x）=k，则f-因子称作k-因子。特别的，若对任意的x∈V（G），g（x）=f（x）=1，（g，f）-因子称为1-因子，即完美对集。图G的完美对集可参见[6]．对图的因子的研究始于一百多年以前。1859年，Reiss证明了K2n图可分解为1-因子。1891年，J．Peterson证明了任意偶数度图可以分解成边不交2-因子的并。而且他证明了每一个2-连通3-正则图都有一个1-因子。这两个结果被认为是现代图因子理论的开端。1947年Tutte[90]给出了图的1-因子存在的判别性准则。这个优美的定理可看作是因子理论中最基本的结果。1952年Tutte[91]又给出了图有f-因子的判别准则。Lovasz[65]得到了图有（g，f）-因子的判别准则。从此，关于因子的结果大量涌现出来。分数（g，f）-示性函数h是一个取值于[0，1]之间的函数，它分配给图G的每条边一个数使得对每一个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}。若Gh是G的支撑子图使得E（Gh）=Eh，则Gh称作是G的分数（g，f）-因子。当对任意的x∈V（G），g（x）=f（x）。分数（g，f）-示性函数称作是分数f-示性函数。设h是图G的一个分数f-示性函数。设Eh={e：e∈E（G）且h（e）≠0}。如果Gh是G的支撑子图使得E（Gh）=Eh，那么Gh称作是G的分数f-因子。分数图论是相对年轻的分支。关于这方面理论的第一篇论文是由Claude Berge[4]在1978写的分数图论。1997年E．R．Schdnerman和D．H．Ullman写了一本新的分数图论[85]，这本专着几乎涵盖了现代分数图论的所有方面，其中包括分数匹配、分数边着色、分数着色和分数同构等分数图论所涉及的内容。在图论中遇到的整数值常量几乎都可以给出它的类似的分数形式。连通因子理论是由M．Kano提出的，1993年他提出了一些关于图的连通因子的问题和猜想[35]。在过去的十年中，许多学者致力于解决M．Kano提出的问题和猜想。从而促进了连通因子理论研究的进展，获得了若干关于连通因子的存在性条件，包括度条件、连通度条件、联结数条件等的各种结果。本文分为五章，主要讨论了四个方面的问题。（1）图的（g，f）-因子存在的若干充分条件；（2）关于一致图的若干结果；（3）图的分数（g，f）-因子；（4）关于图的连通因子若干结果。第一章我们给出了简洁而概括的关于图的因子和分数因子的综述。第二章我们研究在K1，n-自由图和一般图中（g，f）-因子存在的条件。本章分为两部分来研究（g，f）-因子存在的条件。一部分是讨论在K1，n-自由图和一般图中（g，f）-因子存在的与图的独立数有关的条件，并指出在某种意义下这些条件是最好的。另一部分是研究图的联结数和Hamilton（g，f）-因子存在性的关系。定理2．1．6设G是一个连通的K1，n-自由图，a和b是整数，f是定义在V（G）上的非负整数函数使得对任意的z∈V（G），1≤n-1≤a≤f（x）≤b。若f（V（G））是偶数，δ（G）≥b+n-1，且α（G）≤4a（δ-b-n+1）／（b+1）2（n-1），则G含有f-因子。下面的结果说明连通（f-2，f）-因子存在的独立数和最小度条件。定理2．1．7设G是一个连通的K1，n-自由图且|V（G）|≥3，a和b是整数，f是定义在V（G）上的非负整数函数使得对任意的x∈V（G），1≤n-1≤a≤f（x）-2≤b。如果f（V（G））是偶数，δ（G）≥b+n-1，且α（G）≤min{k（G），4a（δ-b-n+1）／（b+1）2（n-1）}，那么G含有连通的（f-2，f）-因子。然后我们试图证明相似的结果在一般图中也是成立的并得到下列结果。定理2．1．9设G是一个连通的n阶图，a和b是整数，f是定义在V（G）上的非负整数值函数使得对任意的x∈V（G），1≤a≤f（x）≤b，其中n≥（a+b）。如果f（V（G））是偶数，δ（G）≥bn／（a+b），且α（G）≤4a（δ-b）／（b+1）2，则G含有f-因子。定理2．1．10设G是一个n≥3阶连通图，a和b是整数，f是定义在V（G）上的非负整数值函数使得对任意的x∈V（G），1≤a≤f（x）-2≤b，其中n≥（a+b）。如果f（V（G））是偶数，δ（G）≥bn／（a+b），且α（G）≤4a（δ-b）／（b+1）2，那么G含有连通的（f-2，f）-因子。我们还得到下列结果。定理2．1．11设G是一个阶数为n的连通图，a和b是整数，f是定义在V（G）上的非负整数值函数使得对任意的x∈V（G），1≤a≤f（x）≤b，其中n≥（a+b）。如果f（V（G））是偶数，δ（G）≥bn／（a+b）且α（G）≤4a（δ-b）／（b+1）2，那么G含有连通的（f，f+1）-因子。如果n=a+b，我们得到下列推论。推论2．1．1设G是一个阶数为n的连通图，a和b是整数，f是定义在V（G）上的非负整数值函数使得对任意的x∈V（G），1≤a≤f（x）≤b，其中n=a+b。如果f（V（G））是偶数，δ（G）≥b且α（G）≤4a（δ-b）／（b+1）2，那么G含有一个f-因子。图G的联结数定义是由Woodal给出的，bind（G）=min{|NG（X）|／|X||+φ≠X（?）V（G），NG（X）≠V（G）}。许多作者研究了图的联结数和因子存在性的关系。第二节我们给出关于图G的联结数和Hamilton（g，f）-因子存在性之间的关系。定理2．2．4设G是一个阶数为n的连通图，a和b是整数且4≤a≤b。设g和f定义在V（G）上的正整数函数使得对任意的x∈V（G），a≤g（x）＜f（x）≤b。设n≥（a+b-5）2／a-2。如果bind（G）≥（a+b-5）（n-1）／（a-2）n-3（a+b-5），且对V（G）任意的非空独立子集X，|NG（X）|≥（b-3）n+（2a+2b-9）|X|／a+b-5，那么G包含Hamilton（g，f）-因子。第三章我们研究若干有指定性质的（g，f）-因子、f-因子和k-因子存在的充分条件。本章我们考虑三方面的问题。第一节我们首先给出覆盖图、消去图和一致图的定义，研究k一致图存在的一个度条件，推广了[12]中的结果；第二节我们给出了若干关于（m，n）-图和（g，f）一致图关系的结果；第三节讨论了f一致图存在的若干充分条件并说明这些条件在某种意义下是最好可能的。定理3．1．3设k≥2是整数，G是一个阶数为n≥4k+8的图，δ（G）＞k+1且kn是偶数。如果对G的任意两个不相邻接的顶点x和y，有max{dG（x），dG（y）}＞n／2。那么G是一个k一致图。关于有指定性质的（g，f）-因子的存在性，我们得到了以下结果。定理3．2．4设G是一个图，m≥2是整数，g和f是定义在V（G）上的两个整数值函数使得对任意的x∈V（G），0≤g（x）＜f（x）。那么对下面两个条件，（1） G是一个（mg，mf-m+1）-图且对任意的x∈V（G），g（x）是偶数；（2） G是一个（mg+m-1，mf）-图且对任意的x∈V（G），f（x）是偶数，只要其中之一成立，则G是一个（g，f）一致图。定理3．2．5设G是一个连通图，m≥2是整数，g和f是定义在V（G）上的两个正整数值函数使得对任意的x∈V（G），g（x）≤f（x）。那么（mg+1，mf）-图和（mg，mf-1）-图是（g，f）一致图。如果对g和f加以限制，我们可得到下列更强的结果。定理3．2．6设G是一个图，m≥2是整数，g和f是定义在V（G）上的两个偶整数值函数使得对任意的x∈V（G），0≤g（x）＜f（x）。如果G是一个（mg，mf）-图，那么G是一个（g，f）一致图。定理3．3．2设G是一个2-边-连通图，f是定义在V（G）上的整数值函数使得对任意的x∈V（G），f（x）≥2，|V（G）|≥maxx∈V（G）f（x）+3。如果对任意不相交的S，T（?）V（G）使得|S|≥2，δG（S，T）=dG-S（T）-f（T）-hG（S，T）+f（S）≥2max f（x）。那么图G是一个f一致图。如果对任意的x∈V（G），f（x）=k，则[56]中的结果是定理3．3．2的推论。推论3．3．3设G是一个2-边连通图，k≥2是一个整数，|V（G）|≥k+3。如果对V（G）的任意的两个不相交的子集S和T使得|S|≥2，有δG（S，T）=dG-S（T）-k|T|-hG（S，T）+k|S|≥2k，则图G是一个k一致图。第四章我们研究分数（g，f）-因子。本章分为两节，首先我们证明图的分数f-因子存在的独立数条件，这说明猜想2．2．8的分数形式是正确的，并且我们证明在某种意义下定理的条件是最好可能的。其次，我们讨论了分数一致图存在的若干条件。定理4．1．4设G是一个连通图，f是定义在V（G）上的非负整数值函数使得对任意的x∈V（G），0≤a≤f（x）≤b。如果δ（G）≥b且α（G）≤4a（δ-b）／（b+1）2，那么G包含分数f-因子。第二节我们研究有指定性质的分数（g，f）-因子的存在性。定理4．2．1设k≥2是一个整数，G是一个阶数为n≥k+1的连通图。如果对V（G）的任意两个不相交的子集S和T1使得|S|≥2都有φ（S，T1）=k|S|-k|T1|+dG-S（T1）≥2k-1，那么G是一个分数k一致图。定理4．2．2设k是一个正整数，G是一个阶数为n≥k+2的图。如果对任意的S（?）V（G）且|S|≥1，sum from j=0 to k（k-j）pj（G-S）≤k|S|-k，其中pj（G-S）表示在G-S中度数为j的顶点的数目。那么G是一个分数k一致图。当k=1，我们得到一个图是分数1一致图的充要条件。定理4.2.3设G是一个连通图。那么G是一个1分数一致图的充要条件是对任意的S（?）V（G），当S不是独立集时i（G-S）≤|S|-2；当S是独立集时i（G-S）≤|S|，其中i（G-S）表示G-S中孤立顶点的数目。根据定理4.2.3，我们可得到下列结果。推论4.2.4设G是一个阶数为n≥4的连通图。如果对任意的S（?）V（G），i（G-S）≤|S|-2，则G是一个分数1—致图。第五章我们讨论图的连通因子。众所周知，连通因子问题是一个NP-完全问题。本章我们给出了若干与最小度、联结数、独立数有关的连通（g，f）-因子和Hamilton（g，f）-因子存在的充分条件。定理5.1.4设G是一个n阶连通图，a，b是两个整数且2≤a≤b，g，f是两个定义在V（G）上的两个整数值函数使得对任意的x∈V（G），α≤g（x）≤f（x）≤b且，f（V（G））是偶数．如果n≥（（a+b）2）╱a，bind（G）＞（（a+d）（n-1））╱an，那么G包含一个连通的（g，f+1）-因子。定理5.1.5设G是一个n阶连通图，a和b是整数且3≤a≤b和b≥4，g，f是两个定义在V（G）上的正整数函数使得对任意的x∈V（G），a≤g（z）≤f（x）≤b。设定n≥（（a+b-4）2）╱（a-2）且f（V（G））是偶数。如果bind（G）＞（（a+b-4）（n-1））╱（（a-2）n-5╱2（a+b-4））且对任意的非空独立集合X（?）V（G），有NG（X）≥·（（b-3）n+（2a+2b-9）|X|）╱（a+b-5）那么G含有一个Hamilton（g，f）-因子。定理5.2.2设G是一个n阶2-连通图，k≥2是整数使得n≥3k—1且kn是偶数，如果a（G）≤（4k（δ-k））╱（k+1）2，δ（G）≥（n+1）╱3，并且对G中任意的两个不相邻接的顶点u，v，max{d（u），d（v）}≥（n-k）╱2。那么G有连通的[k，k++1]-因子。
欧见平,张福基[4]（2004）在《无向De Bruijn网络的可靠性》文中研究表明无向 De Bruijn 网络 UB（d,n） 是最受关注的网络模型之一。利用左邻域和右邻域的性质, 首先 研究这种网络拓扑的限制边连通性。证明了: 当 d ≥ 3, n ≥ 4 时, UB（d,n） 是超级限制边连通 的。然后应用所得到的结果分析它们的可靠性, 确定了其可靠多项式的前 4d ? 4 个系数。
欧见平,张福基[5]（2003）在《3限制边连通度与正则因子》文中研究表明设 G是一个阶不小于 6的 k正则连通点可迁图 .如果 G不含三角形 ,那么图 G是极大 3限制边连通的 ,或者 G含有各连通分支都同构于同一个 h阶点可迁图的 k- 1正则因子 ,其中2 k- 2≤ h≤ 3k- 5.唯一的例外是 :G是围长等于 4的 3正则图
二、3限制边连通度与正则因子（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、3限制边连通度与正则因子（论文提纲范文）
（1）彼得森对图因子理论的贡献（论文提纲范文）
| 摘要 |
| Abstract |
| 引言 |
| 第一章 图因子理论的开创者——彼得森 |
| 1.1 彼得森的生平 |
| 1.1.1 艰难求学路 |
| 1.1.2 学术活动 |
| 1.1.3 人格情操 |
| 1.2 图因子理论形成的背景 |
| 1.2.1 四色猜想与泰特“定理” |
| 1.2.2 不变量理论和西尔维斯特思想 |
| 第二章 彼得森的《正则图理论》 |
| 2.1 创作初衷及内容简介 |
| 2.1.1 《正则图理论》的创作初衷 |
| 2.1.2 《正则图理论》的内容简介 |
| 2.2 彼得森的写作风格及研究方法 |
| 2.3 彼得森的两个定理 |
| 2.3.1 彼得森的 2-因子分解定理 |
| 2.3.2 彼得森定理 |
| 第三章 彼得森的两篇注记 |
| 3.1 《关于泰特“定理”》 |
| 3.2 《“关于泰特‘定理’”的回应》 |
| 第四章 彼得森对图因子理论发展的影响 |
| 4.1 从柯尼希到霍尔 |
| 4.1.1 柯尼希定理 |
| 4.1.2 门格尔定理 |
| 4.1.3 霍尔定理 |
| 4.2 塔特在图因子理论的工作 |
| 结论 |
| 参考文献 |
| 致谢 |
（2）图参数与图的因子（论文提纲范文）
| 中文摘要 |
| 英文摘要 |
| 符号说明 |
| 第一章 绪论 |
| 1.1 基本概念和符号 |
| 1.2 关于图的因子的若干进展 |
| 1.3 关于图的分数因子的若干进展 |
| 1.4 关于因子-临界图的若干进展 |
| 第二章 图的(g,f)-因子 |
| 2.1 图有(g,f)-因子的一个邻域条件 |
| 2.1.1 预备知识和结果 |
| 2.1.2 定理的证明 |
| 2.2 图的邻域并和哈密顿(g,f)-因子 |
| 2.2.1 预备知识和结果 |
| 2.2.2 定理的证明 |
| 第三章 (g,f,n)-临界图 |
| 3.1 联结数、最小度与(g,f,n)-临界图的存在性 |
| 3.1.1 预备知识 |
| 3.1.2 联结数和(a,b,n)-临界图 |
| 3.1.3 联结数和(g,f,n)-临界图 |
| 3.2 邻集和(g,f,n)-临界图的存在性 |
| 3.2.1 预备知识 |
| 3.2.2 邻集和(a,b,n)-临界图 |
| 3.2.3 邻集和(g,f,n)-临界图 |
| 第四章 图的分数因子 |
| 4.1 邻域并和分数f-因子 |
| 4.1.1 预备知识和结果 |
| 4.1.2 定理的证明 |
| 4.2 关于分数(g,f,n)-临界图 |
| 4.2.1 预备知识和结果 |
| 4.2.2 引理 |
| 4.2.3 主要定理的证明 |
| 第五章 图的连通因子 |
| 5.1 图的邻域并和连通的[k,k+1]-因子 |
| 5.1.1 预备知识和结果 |
| 5.1.2 主要定理的证明 |
| 5.2 图的邻集和连通的(g,f+1)-因子 |
| 5.2.1 预备知识和结果 |
| 5.2.2 主要定理的证明 |
| 参考文献 |
| 致谢 |
| 作者简介 |
| 学位论文评阅及答辩情况表 |
（3）图的因子和分数因子（论文提纲范文）
| 中文部分 |
| 中文摘要 |
| 英文摘要 |
| Symbols |
| 第一章 绪论 |
| 1.1 基本概念和符号 |
| 1.2 关于图的因子的若干进展 |
| 1.3 关于分数因子的若干进展 |
| 第二章 图的(g,f)-因子存在的若干充分条件 |
| 2.1 图的独立数和图的(g,f)-因子的存在性的关系 |
| 2.1.1 预备知识和结果 |
| 2.1.2 主要定理的证明 |
| 2.2 关于图的联结数和图的Hamilton(g,f)-因子的存在性 |
| 2.2.1 预备知识和结果 |
| 2.2.2 定理的证明 |
| 第三章 关于一致图的若干结果 |
| 3.1 k一致图存在的一个度条件 |
| 3.1.1 预备知识和结果 |
| 3.1.2 引理 |
| 3.1.3 定理的证明 |
| 3.2 有关(m,n)-图和(g,f)一致图的关系 |
| 3.2.1 预备知识和结果 |
| 3.2.2 主要定理的证明 |
| 3.3 关于f一致图的有关结果 |
| 第四章 图的分数(g,f)-因子 |
| 4.1 图的独立数和图的分数f-因子存在性 |
| 4.1.1 预备知识和结果 |
| 4.1.2 主要定理的证明 |
| 4.2 有指定性质的分数(g,f)-因子存在性的各种条件 |
| 4.2.1 预备知识和结果 |
| 4.2.2 引理 |
| 4.2.3 主要定理的证明 |
| 第五章 关于图的连通因子的若干结果 |
| 5.1 图的联结数条件 |
| 5.1.1 预备知识和结果 |
| 5.1.2 主要定理的证明 |
| 5.2 图的独立数和度条件 |
| 参考文献 |
| 致谢 |
| 作者简介 |
| 学位论文评阅及答辩情况表 |
| 英文部分 |
| Chinese Abstract |
| English Abstract |
| Symbols |
| Chapter 1 Introduction |
| 1.1 Basic Definitions and Notations |
| 1.2 Introduction on Factors of Graphs |
| 1.3 Introduction on Fractional Factors of Graphs |
| Chapter 2 The Existence of (g,f)-Factors in Graphs |
| 2.1 Stability Number and the Existence of f-Factors in Graphs |
| 2.1.1 Preliminary and Results |
| 2.1.2 Proofs of Main Theorems |
| 2.2 On Binding Number and the Existence of Hamilton (g,f)-Factors in Graphs |
| 2.2.1 Preliminary and Results |
| 2.2.2 The Proof of Main Theorem |
| Chapter 3 Some Results on Uniform Graphs |
| 3.1 A Degree Condition for the Existence of k-Uniform Graph |
| 3.1.1 Preliminary |
| 3.1.2 The Lemmas |
| 3.1.3 The Proof of Theorem |
| 3.2 On the Relationship between (m,n)-Graphs and(g,f)-Uniform Graphs |
| 3.2.1 Preliminary and Results |
| 3.2.2 Proofs of Main Theorems |
| 3.3 Some Results on f-Uniform Graphs |
| Chapter 4 Fractional(g,f)-Factors of Graphs |
| 4.1 Stability Number and the Existence of Fractional f-Factors |
| 4.1.1 Preliminary and Results |
| 4.1.2 The proof of Main Theorem |
| 4.2 Various Conditions for the Existence of Fractional(g,f)-Factors with Prescribed Properties |
| 4.2.1 Preliminary and Results |
| 4.2.2 The Lemmas |
| 4.2.3 Proofs of Main Theorems |
| Chapter 5 Some Results on Connected Factors of Graphs |
| 5.1 The Binding Number Conditions |
| 5.1.1 Definitions and Preliminary Results |
| 5.1.2 Proofs of Main Theorems |
| 5.2 Stability Number and the Degree Condition |
| References |
| Acknowledgement |
| Curriculum Vitae |
| 学位论文评阅及答辩情况表 |
（4）无向De Bruijn网络的可靠性（论文提纲范文）
| 1 引言 |
| 2 超级限制制边连图 |
| 3 可可靠性分析 |
四、3限制边连通度与正则因子（论文参考文献）
- [1]彼得森对图因子理论的贡献[D]. 王函. 河北师范大学, 2015(11)
- [2]图参数与图的因子[D]. 刘红霞. 山东大学, 2010(08)
- [3]图的因子和分数因子[D]. 蔡建生. 山东大学, 2007(03)
- [4]无向De Bruijn网络的可靠性[J]. 欧见平,张福基. 工程数学学报, 2004(06)
- [5]3限制边连通度与正则因子[J]. 欧见平,张福基. 数学物理学报, 2003(06)