论文部分内容阅读
图论的研究始于200多年前,第一篇关于图论的文章是1736年由Euler发表的,他利用图的方法解决了哥尼斯堡(K(o)nigsberg)七桥问题.之后,图论在科学界异军突起,活跃非凡.图论中有很多著名的问题,如哈密顿问题,四色问题,中国邮递员问题等.并且,应用图论在解决化学,计算机科学,生物学等学科问题时已显示出极大的优越性.图论作为离散数学的一个重要分支,受到了各方面的普遍重视.
本文考虑简单、无向有限图,这些图不包含环以及重边.哈密顿圈问题是图论中非常著名的问题之一.图中过每个顶点的圈,称为图的哈密顿圈.设G表示一个简单图,图G的k个独立圈是指G中k个顶点不相交的圈.图G的一个2-因子是指图G的一个2-正则生成子图,其中2-因子的每一个连通分支都是一个圈.一个哈密顿圈可以看成是仅有一个分支的2-因子.图的独立圈和2-因子问题是图的因子理论中非常重要的一部分,也是图的哈密顿圈理论的推广和延伸.它是非常有趣的一类问题,其理论研究已逐渐成熟与完善,并且在计算机科学与网络通讯设计中都有重要的应用.
运用分类讨论,树形图以及穿脱原理等方法,本文研究了在一般的简单图以及均衡二部图中,含指定个数的独立圈和2-因子问题,具有指定性质的独立圈和2-因子问题以及含指定长度的独立圈和2-因子问题.主要分为三个章节:第一章介绍了图的一些基本概念,独立圈和2-因子问题的研究历史、发展状况以及主要结论.第二章利用二部图的一些性质,对均衡二部图中的独立圈和2-因子问题做了研究.证明了对于均衡二部图的一个含k+1个独立圈的2-因子来说,当满足一定的最小度条件时,4-圈的个数至少是k并且其中每个独立圈都含有两条指定的边,以及给出了在含指定顶点的k个独立圈中,恰好含s个4-圈和k-s个6-圈的最小度条件.第三章对一般简单图中的独立圈和2-因子问题做了研究.首先给出了在图的k个独立圈中,恰好含s个K3和k-s个K4的最小度条件.又给出了在图的一个含k+1个独立圈的2-因子中,恰好含s个3-圈和k-s个4-圈的最小度条件.