图可区别染色算法的研究

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

1、独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含获得兰趔童道太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者繇烁彬、签字蹴矽哆年多月∥～曰学位论文版权使用授权书本学位论文作者完全了解兰趔童逼太堂有关保留、使用学位论文的规定。特授权兰趔童通太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，

2、并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适用本授权说明)学位论文作者签名：签字日期：≯侈年如如新躲矽≯2么月步日签字日期：别弓年歹月∥日兰州交通大学硕士学位论文摘要图的染色问题是图论中一个重要的研究课题，在理论和工程上都具有良好的应用背景。图的染色问题是NP完全问题，虽然现有的一些经典智能优化算法如遗传算法、神经网络算法、模拟退火算法等都被广泛地应用于解决组合优化和NP完全问题。但是随着染色问题规模的不断增大，算

3、法运行的时间会大幅度增加，收敛速度也会大幅度下降，严重影响算法的效率。目前，传统的解决图染色问题优化算法主要是针对正常的点(边)，从己发表的公开文献看很少有解决可区别染色的智能优化算法。所以，本文针对一般图的点可区别边染色和非正则图的点可区别全染色的特点分别设计新的算法，并且对算法进行测试验证，取得了较为理想的实验结果。本文的主要研究工作如下：(1)分析了一些经典算法(遗传算法、神经网络算法、模拟退火算法)在图染色问题中的应用，重点研究了在应用遗传算法解决图染色问题时出现的问题。结果表明，一方面这些算法对

4、于解决图的点可区别边染色的效率不高，另一方面这些算法对于解决非正则图的点可区别全染色针对性不强。(2)深刻研究了图染色的相关概念和关键技术，具体包括：均匀染色、图的D(f1)染色、概率函数及染色条件约束函数的构建，重点阐述概率函数在图染色上的应用，同时对染色条件约束函数的构建进行了总结和深化。(3)针对一般图设计了一种新型的点可区别边染色算法，并对算法进行了测试验证。本算法把概率思想和图染色相结合，同时应用到了随机函数，根据点可区别边染色的特点得到约束函数，确立最终目标函数。分别以一般图和完全图为研究对象

5、，对这种新型的算法进行了测试，取得了预期的实验结果。(4)针对最大度大于2的非正则图，设计和实现了图的D(f1)一点可区别全染色算法，并对算法进行了测试验证。在对最大度大于2的非正则图的D(p)一点可区别全染色算法设计中，按照度从大Nd,的顺序对所有待染色的顶点和边进行划分，对度较大的顶点及其关联边优先进行染色，并创造性地应用约束规则表对染色过程进行了简化，极大地提高了算法的效率。在vC++环境下用C语言对这个算法进行编程，短时间内得到了预期的实验结果，验证了算法有较快的运行速度和较高的收敛速度。关键词：

6、经典算法；概率函数；一般图；点可区别边染色；点可区别全染色论文类型：应用基础研究图的可区别染色算法研究AbstractGraphcoloringproblemisanimportantresearchtopicofgraphtheory．Ithasagoodapplicationbackgroundbothintheoryandinengineering．GraphcoloringproblembelongstoNPcompleteproblems．Someintelligentoptimizationa

7、lgorithmssuchasGeneticAlgorithms，NepalNetworks，SimulatedAnnealingAlgorithmhavebeenwidelyusedinsolvingcombinatorialoptimizationandNPcompleteproblem．However,withthescaleoftheproblemexpanding，therunningtimeofthealgorithmwillincreasesubstantiallyandtheconverg

8、encerateofthealgorithmwillalsodropgreatly．Inthiscase，theefficiencyofthealgorithmwillbeaffectedseriously．Currently，traditionalintelligentoptimizationalgorithms，whichsolvethegraphcoloringproblems，aremainlyaimedatprope