论文部分内容阅读
本文考虑的图若无特殊声明均为简单、无向有限图,对于图G,用V(G)和E(G)分别表示图G的顶点集合和边集合,则G=G(V(G),E(G)),对于任意v∈V(G),用dG(v)表示顶点v在G中的度数.用δ(G)即min{dG(v)|v∈V(G)}表示图G的最小度,在不引起混淆的情况下简记为δ。如果G中每个顶点的度均相等,则称G为正则图,用|G|=|V(G)|即G的顶点数表示G的阶数,并定义图G中两个不相邻的顶点的最小度之和为:
σ2(G)=min{dG(x)+dG(y)|x,y∈V(G),x≠y,xy(?)E(G)}.(当G是一个完全图时,定义σ2(G)=∞).
对于二部图G,用V1和V2来表示G的两个部分的顶点集合,当|V1|=|V2|时,称G为均衡二部图,并定义
δ1,1(G)=min{dG(x)+dG(y)|x∈V1,y∈V2},
σ1,1(G)=min{dG(x)+dG(y)|x∈V1,y∈V2,xy(?)E(G)}.
(当G是完全二部图时,定义σ1,1=∞).
对于图G中的路P和圈C,分别用l(P)=|V(P)|-1,l(C)=|V(C)|表示路和圈的长度。G的包含G中所有顶点的一个圈称为G的一个哈密顿圈,如果存在G'(?)G使得V(G)=V(G'),则称G'为G的支撑子图,而G的一个1-正则支撑子图就是G的一个1-因子,通常也称1-因子为完美匹配或完美对集.显然G的一个1-因子就是覆盖G中所有顶点的一个边集合.而G的一个2-因子就是G的一个2-正则支撑子图,易知2-因子的每一个连通分支分别是一个圈,而图G的k个独立圈是指G中k个顶点不相交的圈,不难看出2-因子问题与图的独立圈问题有着密切的联系,它们不仅是图的因子理论中非常重要的一部分,也是图的哈密顿圈理论的推广和延伸.其理论研究日益成熟和完善,而且在计算机科学、通信网络设计等领域都有重要的应用.
关于图的独立圈、2-因子理论的研究主要集中在以下几个方面:图中含指定个数的独立圈和2-因子的问题;图中含指定长度的独立圈和2-因子的问题;图中含具有指定性质的独立圈和2-因子的问题等等.
本文的创新之处在于证明的给出过程,采用分层讨论的方法.全文共分三章.第一章简单介绍了图论的基本概念,独立圈,2-因子理论的历史和发展状况及一些已有的相关结论,这一章是后面三章的基础.
第二章讨论了图中包含指定长度的独立圈问题,证明了:定理2.2.1.若|G|=4k,k≥5,σ2(G)≥4k-3,则G包含k-1个点不相交的4-圈,
第三章讨论了二部图中含独立圈的问题,证明了:定理3.1.1.G=(V1,V2;E)是二部图,|V1|=|V2|=3k,k是一个正整数,如果σi,i(G)≥4k-1,那么G包含k-2个6-圈和一个12-圈,并且它们互相独立,