论文部分内容阅读
本文里所涉及的图假如没有特殊声明则均为简单的、无向的有限图。在图G中,我们用V(G)表示图G的顶点的集合,用E(G)表示图G的边的集合。在G=G(V(G),E(G)),对于任意ν∈V(G),我们用d(v,C)表示的是顶点v在图C中的度数,用δ(G)记做图G的最小度。对于图G中的路P和圈C,Pi表示一条顶点数目为i,长度为|V(P)|-1的路。Ci表示顶点数目为i,长度为|V(C)|的圈。用Pi=(p1,p2,p3,p4,…,pi)表示路Pi,其中A表示路的顶点。Ci=(c1,c2,c3,c4,…,c1)表示圈Ci,其中ci表示路的顶点。|E(P,Q)|表示图P和图Q之间的连边的数目。
G的一个哈密顿圈是图G的包含G中所有顶点的一个罔。如果G′(∈)G使得V(G)=V(G'),则称G'为G的支撑子图,而G的k-因子是指G的一个k-正则支撑子图,也就是G的一个2-因子就是G的一个2-正则支撑子图,易知2-因子的每一个连通分支分别是一个圈,G的一个哈密顿圈就是图G的一个2-因子。
图的路和圈问题是图论中一个十分重要而且活跃的研究课题,有大量的实际问题可以归结为图的路和圈问题。图论中三大著名难题之一的Hamilton问题本质上也是图的路和圈问题。国内外许多学者对此问题作了大量的研究工作。而图论中的2-因子问题是非常重要的一部分,也是图的哈密顿圈理论的推广和延伸和推广。在这些日益成熟的理论中,对2-因子问题的研究主要集中以下几个方而:图中含指定个数的2-因子和路P或者图中含有指定长度的2-因子和路的数目;图中含指定长度的2-因子的数目等等。
全文共分三章。
第一章主要介绍了图论的发展历史,让更多的人能够了解图论所讲解的主要内容,能够有兴趣的去主动接触图论。
第二章主要介绍了本文要用到的图论中的基本概念,以时间顺序介绍了2-因子理论中的主要结论,这样在理解本文时能够有一个整体的印象,并且能够知道本文所做出的结论意义。
而第三章是定理证明的部分,在第一节中,主要的工作是证明了六个引理,第二节是定理证明部分,在这一节中,穿插利用前面的引理,最终证明了主定理;而在第三节中,主要提出了可以进一步讨论的问题,这些问题是从本文中讨论的问题拓展延伸出来的,可以作为下一个研究的课题。
本文的核心部分主要是讨论了这样的一个问题:定理3.8设G是个简单图,其中|V(G)|=5κ,δ(G)≥3κ,则G有κ-1个5-圈和一条5-路。
而本文讨论的问题主要是来源于El-Zahar猜想,此猜想在n1=n2=…=nκ=5的时候能够得出G中包含κ个独立的5-圈,而本文得到的结果是G有κ-1个5-圈和一条5-路。
猜想3.8设G是一个简单图,其顶点数n=n1+n2+…+nk(ni≥3)。如果δ(G)≥「n1/2]+「n2/2]+…+「nk/2],那么G中包含κ个独立圈C1,C2,…,Ck,其长度分别为n1,n2,…,nk。