论文部分内容阅读
有关于图的因子的问题一直是图论中的热点课题之一,具有重要理论意义.许多学者都对因子理论进行了深入的探讨和研究,并且已有相当丰富的研究成果.图的2-因子理论在实际生活中的应用也越来越广泛,例如交通、计算机网络等实际问题.随着网络的逐渐发达,对图的2-因子理论应用也越来越频繁,因而对2-因子理论的研究也是图论研究的一个重要领域.在图的分数因子方面的研究也是最近几年才提出的.学者们在匹配理论的基础上提出了因子、分数因子的概念. 本文主要研究了均衡二部图中的2-因子,给出了2-因子存在的几个限制条件.本文一共分五章. 第一章阐述了图论及因子理论,特别是2-因子理论的一些基本结果和研究现状. 第二章主要对均衡二部图中2-因子的存在性进行了探讨,并给出了几个在均衡二部图中2-因子存在的条件. 第三章主要研究了二部图中一个与韧度有关的参数和2-因子存在性的关系. 第四章给出了均衡二部图中存在分数2-因子的一个充分必要条件. 第五章对文章进行总结论述. 本文主要结果如下: 引理2.2.6设G是n2阶的均衡二部图,M为G的任一完美匹配,n4>,且δ≥(G) n,则G中存在顶点不交的两个M-圈+22 C,2C.1 定理2.2.7设G是n2阶的均衡二部图,n44k>?其中k≥2是整数,且δ≥(G) n+ k2?(1)2,则对G的每个完美匹配M,G中存在一个恰含k个分支的M-2-因子. 引理2.2.8设s2>,G=(YX是一个n2阶的均衡二部图,n≥ sk,,)σ1 G,1()≥1(1)1n?+.如果G包含k个顶点不交的长至少为s2的圈,则G s?V∪=(i C k1 i)包含一条Hamilton-路. 定理2.2.9设s2>,G=(YX是一个n2阶的均衡二部图,n≥ sk,,)σ1 G,1()≥1(1)1n?+.如果G包含k个顶点不交的长至少为s2的圈,则G有一个至少包s含k个顶点不交的长至少为s2的圈的2-因子. 引理3.2.1设G=(YX是一个二部图,)(Gt′≤1.), n2?定理3.2.2设G=(YX是一个连通的均衡二部图,且),| GV= n2.当)(Gt′>(|) n时,二部图G存在1-因子. 定理3.2.3设G=(YX是一个均衡二部图,对任意的T? X或Y,1r≤2,且)(Gt′=1,),则二部图G存在2-因子.其中1r=||1R,1R={d x(|T x),=,1 x∈T N)}(. 定理4.2.1设G=(YX是一个均衡二部图,G有分数2-因子当且仅当任意的S X?,),T Y?,有 定理4.2.2设G=(YX是一个均衡二部图,a,b为两个非负整数,且a≤b.如果),对任意的S X?,T Y?,有 则G存在[,]a b-因子.