一般图的可区别着色算法研究

《一般图的可区别着色算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中图分类号：TP311密级：公开UDC：本校编号：硕士学位论文论文题目：一般图的可区别着色算法研究研究生姓名：张云寒学号：0211730学校指导教师姓名：李敬文职称：教授申请学位等级：工学硕士学位专业：计算机软件与理论论文提交日期：2014.06论文答辩日期：2014.05.31万方数据硕士学位论文一般图的可区别着色算法研究TheResearchofAlgorithmsforDistinguishingColoringsofGeneralGraph作者姓名：张云寒学科、专业：计算机软件与理论学号：0211730指导教师：李敬文教授完成日期：2

2、014.04兰州交通大学LanzhouJiaotongUniversity万方数据独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含获得兰州交通大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：签字日期：年月日学位论文版权使用授权书本学位论文作者完全了解兰州交通大学有关保留、使用学位论文的规定。特授权兰州交通大学可以将学位论文的全

3、部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：导师签名：签字日期：年月日签字日期：年月日万方数据兰州交通大学硕士学位论文摘要图着色作为图论中一个主要的研究领域，在工程上和理论上都具有很好的应用价值，比如一些典型的组合问题如最大支配集、加工调度，还有一些实际的问题如停车场的建立、商品的配送收集等都可以转化为图着色问题来研究。最近这些年，一些经典的智能优化算法如禁忌搜索算法、遗传算法、蚁群算

4、法等都被应用到了解决图的着色问题中来。但是这些算法大多针对的是图的正常点着色或将正常边着色或全着色转化为点着色来解决，使用它们来解决图的可区别着色的研究工作还做的很少。另外，随着图的规模不断增大，染色问题也变得更加复杂，这些算法的运行时间会明显增加，搜索性能及收敛性大幅下降。本文所作的主要研究工作就是设计新的算法，分别解决点可区别边染色、点可区别全染色、邻点可区别边染色、邻点可区别全染色四种染色问题，并且算法效率高、收敛性好，突破了传统经典算法的局限。本文的主要研究工作如下：(1)介绍古典染色概念如正常的点着色、边着色、全着色，还有在此基础上

5、产生的点可区别着色、邻点可区别着色的概念；并介绍经典优化算法如禁忌搜索算法、遗传算法的算法思想，及其在图着色问题中的应用，分析这些算法的的缺点和不足，以在本文的研究工作中避免或改进。(2)针对一般图进行点可区别染色算法的设计，主要有点可区别边染色算法设计和点可区别全染色算法设计。首先构建目标函数和算法的数据结构，根据点可区别边染色算法思想给出了算法步骤及流程图，之后对算法进行测试，并分析算法的正确性、收敛性；根据点可区别全染色算法思想给出了算法步骤和流程图，对算法进行测试，并分析了算法的正确性和空间复杂度；最后对两个算法进行总结。(3)针对一

6、般图进行邻点可区别染色算法的设计，主要有邻点可区别边染色算法设计和邻点可区别全染色算法设计。首先在点可区别边染色算法的基础上进行了改进，使之能够有效的解决邻点可区别边染色问题，并对算法进行测试，得到了很好的实验结果；根据邻点可区别全染色算法思想给出了算法步骤及流程图，之后对算法进行测试，并分析算法的时间复杂度；最后对两个算法进行总结。关键词：点可区别边染色；点可区别全染色；邻点可区别边染色；邻点可区别全染色论文类型：应用基础研究-I-万方数据一般图的可区别着色算法研究AbstractGraphcoloringproblemisanimport

7、antresearchfieldingraphtheory,andithastheimportanttheorysignificanceandstrongapplicationvalue.Itcanbeusedtosolveanumberoftypicalcombinatorialproblemssuchasmaximumdominatingsets,processingandscheduling,andsomepracticalproblemsliketheestablishmentoftheparkinglot,thedeliveryan

8、dcollectionofthegoods.Inrecentyears,someclassicalintelligentoptimizationalgorithms