图的若干不完备可区别染色算法研究

发布时间：2017-08-21 10:06

  本文关键词：图的若干不完备可区别染色算法研究

  更多相关文章： 不完备可区别染色 邻点可区别E-全染色 邻点可区别V-全染色 邻点可区别I-全染色 邻点可区别VI-全染色

【摘要】：本学位论文主要考虑图的不完备可区别染色问题。图染色是图论中一个非常重要的研究方向,在实际问题中有着很好的应用,排课表问题、任务分配问题、集成电路布线等都可以从图染色的角度来解决。可以说,图染色为一些实际问题的解决提供了一种新的思路和方法。由于实际问题的复杂性,单一的点染色或者边染色并不能完全满足问题的要求,研究者们便提出了各种各样的染色问题,如点(邻点)可区别染色、均匀染色、可约染色等,并得到了很多有价值的理论成果,而不完备可区别染色便是由于实际问题的需要,在正常可区别染色基础上的弱化。由于图的染色问题是一个NP-完全问题,目前解决图染色问题的算法主要依赖于智能算法,但只限于解决特殊图的点染色或者边染色,不能解决全染色和可区别染色问题,而现实中的很多问题所转化的图都具有一定的随机性,所以寻求针对任意一个图的高效的染色算法已成为图论研究者的一个重要的课题。对于不完备可区别染色,已发表的文献中虽然得到了一些理论成果,却没有可行的染色算法,而算法的实现对相关问题的研究具有较高的实际意义。所以,本文根据不完备可区别染色的染色要求,设计出了针对任意一个简单连通图的染色算法,通过大量的测试分析,算法具有较高的染色效率。本文的工作如下:(1)介绍了与本文有关的一些基本染色概念及猜想,同时给出本文有关内容的研究背景、国内外研究动态等。(2)介绍了粒子群算法、遗传算法的基本思想、流程,及其在图染色中的应用,并对这些算法在解决图染色问题的性能上进行了分析。(3)针对任意简单连通图设计了四种不完备邻点可区别全染色算法,包括一种基于正常点染色的邻点可区别E-全染色算法,和三种基于正常边染色的算法,分别为邻点可区别V-全染色算法、邻点可区别I-全染色算法和邻点可区别VI-全染色算法。前者采用先顶点染色再边染色的方法,而后者采用先边染色再顶点染色的方法。其中,算法中设计的边染色方法,可以解决任意一个图的正常边染色问题,而且根据染色条件的变化还可以解决其它基于正常边染色的全染色或可区别染色问题。文中给出了算法的详细流程及测试,并对算法的正确性、收敛性和时间复杂度进行了分析,最后对算法做了总结。
【关键词】：不完备可区别染色 邻点可区别E-全染色 邻点可区别V-全染色 邻点可区别I-全染色 邻点可区别VI-全染色
【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• Abstract5-9
• 1 绪论9-12
• 1.1 引言9
• 1.2 研究背景9-10
• 1.3 本文的研究内容及组织10-12
• 2 经典优化算法在图染色中的应用12-20
• 2.1 引言12
• 2.2 图染色相关定义及猜想12-14
• 2.3 粒子群算法在图染色中的应用14-17
• 2.3.1 粒子群算法的基本思想14-16
• 2.3.2 粒子群算法在图染色中的应用16-17
• 2.3.3 粒子群算法总结17
• 2.4 遗传算法在图染色中的应用17-19
• 2.5 本章小结19-20
• 3 图的邻点可区别E-全染色算法20-31
• 3.1 引言20
• 3.2 邻点可区别E-全染色算法设计20-25
• 3.2.1 约束函数设计20-21
• 3.2.2 算法步骤及流程图21-25
• 3.3 算法测试25-28
• 3.4 算法分析28-29
• 3.5 算法总结29-31
• 4 图的邻点可区别V-，I-，，VI-全染色算法31-57
• 4.1 引言31
• 4.2 邻点可区别V-全染色算法设计31-39
• 4.2.1 约束函数设计31-32
• 4.2.2 算法步骤及流程图32-36
• 4.2.3 算法测试36-39
• 4.3 邻点可区别I-全染色算法设计39-46
• 4.3.1 约束函数设计40-41
• 4.3.2 算法描述及流程图41-43
• 4.3.3 算法测试43-46
• 4.4 邻点可区别VI-全染色算法设计46-54
• 4.4.1 约束函数设计46-47
• 4.4.2 算法描述及流程图47-48
• 4.4.3 算法测试48-54
• 4.5 算法分析54-56
• 4.6 算法总结56-57
• 结论57-59
• 致谢59-60
• 参考文献60-63
• 攻读学位期间的研究成果及参加的科研项目63

【共引文献】

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

1 王涛;赵宜宾;李德明;;路与路联图的邻强边染色和均匀邻强边染色(英文)[J];安徽大学学报(自然科学版);2012年01期

2 朱恩强;吕新忠;张玉红;;关于C_m·C_n,C_m·S_n和C_m·K_n的邻点可区别全色数[J];江西师范大学学报(自然科学版);2008年04期

3 李宜义;张卫平;;图染色思想在库存管理中的一种应用研究[J];电脑知识与技术;2011年26期

4 强会英;张忠辅;;部分图笛卡儿积图的邻点可区别VE-全染色[J];兰州理工大学学报;2009年05期

5 WOODALL Douglas R;;Adjacent strong edge colorings and total colorings of regular graphs[J];Science in China(Series A:Mathematics);2009年05期

6 辛小青;王治文;陈祥恩;姚兵;;点不交的m个C_3的并的点可区别全染色[J];吉林大学学报(理学版);2012年02期

7 孔令峰;苏文龙;罗海鹏;黎贞崇;何建东;;图P_(u,v)(n)的邻强边染色[J];计算机应用研究;2008年06期

8 强会英;张忠辅;;一些联图的邻点可区别-边全染色[J];兰州大学学报(自然科学版);2009年06期

9 强会英;张忠辅;;若干图广义Mycielski图的点边邻点可区别的全染色[J];兰州交通大学学报;2008年06期

10 王鸿杰;王治文;朱恩强;文飞;;关于C_m×K_n的邻点可区别全色数[J];兰州交通大学学报;2010年01期

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

1 刘彬;图的点可区别染色、列表染色和线性染色[D];山东大学;2010年

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

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

1 文飞;若干图类的Smarandachely邻点全染色[D];兰州交通大学;2011年

2 孙婷婷;图的点可区别的边染色及点可区别的全染色[D];重庆大学;2008年

3 周薇;若干图的关联着色与邻点可区别关联着色研究[D];山东科技大学;2009年

4 张琛;关于图的邻点可区别全染色的一些结果[D];西北师范大学;2008年

5 张义瑛;平面图邻接点区分边染色的一个结果[D];南京师范大学;2013年

6 严丞超;平面图的邻点可区别边染色[D];浙江师范大学;2013年

7 薛国梁;字典积图及其Mycielski图的邻点可区别的边染色与全染色[D];西北民族大学;2013年

8 李华龙;平面图的邻和可区别全染色[D];山东大学;2014年

9 王倩;随机图的Smarandachely点可区别染色算法研究[D];兰州交通大学;2014年

10 杨超;关于具有一个或多个可区分约束条件的图着色研究[D];西北师范大学;2014年

本文编号：712246