Halin图消圈数及点染色问题的研究

发布时间：2017-11-15 17:01

  本文关键词：Halin图消圈数及点染色问题的研究

  更多相关文章： 图 Halin图 近正则Halin图 最小消圈集 消圈数 点色数

【摘要】：图论知识在电路的设计和计算机操作系统中预防出现死循环等一系列实际问题中的应用引发了对通过去掉图中的一些点(当然也去掉了与这些点相连的边),从而破掉图中所有圈的问题的研究,也就是对消圈数问题的研究.图的最大诱导森林,图的独立数(最大独立集的阶数)等问题都与消圈数有密切关系,所以这一问题的研究在图论中起着十分重要的作用.要想更好的了解图的性质与结构,从研究图的消圈数入手不失为一个好的突破口.著名的四色猜想被提出来后,引发了人们对图的染色问题的研究,被染色的对象逐渐地变得越来越广泛,出现了点染色,边染色,面染色,全染色,强边染色等等.图的染色问题具有很重要的理论和实际应用价值,是图论一个重要的研究方向.图的染色问题,处理的是涉及任务分配之类的问题.编排课表问题,物品存放问题,时间表问题,网络电路的设计等均属于图的染色问题的范畴.虽然以上这两个问题很重要,但在对一般图的研究上举步维艰,人们更多时候是去研究一些特殊的图类并取得了一些进展.根据Tutte关于3-连通图的结构定理：每一个3-连通图都可由某个轮图(也是Halin图)经过顶点分裂逐步得到,由此可以看出Halin图在图的结构研究中的地位和作用.本文首先研究得到了近正则Halin图G的消圈数的上,下界；接下来构造得到了两类特殊的Halin图,用以证明我们得到的消圈数的上,下界是紧的,接着得到了最大度为k或最小度为k的Halin图的消圈数所满足的界；本文还研究了另外两类近4-正则Halin图的消圈数并确定了这两者的各一个最小消圈集；在最后,本文还对Halin图的点染色问题进行了研究,给出了点色数定理[1]的一种新证明.
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】

中国期刊全文数据库 前10条

1 赵小强;;高考中一类染色问题的推广与应用[J];数学爱好者(高考版);2008年12期

2 刘西峰;;两次捆绑快速解决有关染色问题[J];中学教学参考;2009年26期

3 郭建华;;染色问题解题策略例说[J];青苹果;2009年06期

4 卢建立;任凤霞;;3×n方格染色问题的两个新结果[J];数学通报;2011年12期

5 麦安婵;两类图的全染色问题[J];榆林高等专科学校学报;2002年04期

6 刘蓉;;排列组合中的染色问题[J];科技信息;2011年10期

7 卢建立;任凤霞;马美琳;;项链的若干染色问题[J];科技导报;2012年07期

8 卢家华;吴康;;3×n方格染色问题的再研究[J];数学通报;2014年01期

9 林育青;关于图的染色问题[J];广西大学学报(自然科学版);2000年01期

10 王绍文;;图的染色问题综述[J];北京机械工业学院学报;1995年02期

中国博士学位论文全文数据库 前7条

1 李善海;设计的染色及其相关问题的研究[D];上海交通大学;2006年

2 陈敏;运用权转移方法研究图的若干染色问题[D];苏州大学;2011年

3 侯建锋;图上有限制条件的几类染色问题的研究[D];山东大学;2009年

4 胡小兰;极值和染色问题的一些新结果[D];南京大学;2015年

5 董爱君;图的几类染色问题[D];山东大学;2012年

6 梁作松;图的团横贯与团染色[D];上海大学;2013年

7 于永;图的[r，s，，t；f]-染色及（p，1）-全标号问题[D];山东大学;2012年

中国硕士学位论文全文数据库 前10条

1 朱俊俏;关于图的点可区别染色问题[D];浙江师范大学;2009年

2 王瑞琦;图边单射染色问题的复杂性及算法研究[D];南京师范大学;2014年

3 朱恩强;若干图类的新染色问题[D];兰州交通大学;2010年

4 王辉;满足某些特殊条件的平面图边染色问题研究[D];山东大学;2010年

5 尹琳娟;图论染色问题应用研究[D];西安电子科技大学;2009年

6 刘君;图的染色[D];兰州大学;2006年

7 胡义;高效的图染色近似型求解算法[D];华中科技大学;2011年

8 吴倩;图的若干染色问题研究[D];浙江师范大学;2012年

9 吴玉蝶;图的k-重染色问题[D];浙江师范大学;2011年

10 任冠峰;图的k-重染色问题[D];浙江师范大学;2009年

本文编号：1190515