关于图的独立圈和2-因子问题的研究

来源 :河南师范大学 | 被引量 : 0次 | 上传用户:zsjhmya
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图论的研究始于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-圈的最小度条件.  
其他文献
本文考虑了一类非线性系统全局有限时间内输出镇定和一类非线性系统的实用输出跟踪问题.首先,研究了一类线性化不可控不可观的非线性系统全局有限时间内的输出镇定,运用改进
学位
众所周知,在确定性条件下,奇异线性连续Hamilton系统生成的最小算子H0是一个对称算子,即稠定的Hermite算子,它的伴随算子等于其在相关的Hilbert空间的相应的最大算子H.如果确定性
给出了二阶椭圆问题混合元格式的一种新的稳定化方法。对于低阶元空间,其不满足二阶椭圆问题混合元格式的LBB条件,但由于其实际计算中的简单性和高效性,在工程应用中非常普遍
在无穷维哈密顿系统的有限维不变环的存在性方面,比如非线性哈密顿偏微分方程的有限维不变环的存在性,已经取得了丰富的成果.目前主要有两种方法用于研究非线性偏微分方程的周