随机有向图的染色算法研究

发布时间：2017-09-11 08:12

  本文关键词：随机有向图的染色算法研究

  更多相关文章： 随机有向图 正常弧染色 正常全染色 均匀弧染色 均匀全染色

【摘要】：图的染色问题一直是图论领域中的一个重要研究课题,无论在理论上还是在实际中都有着广泛的应用,例如一些典型的组合问题如加工调度、最大支配集等问题,实际中如停车场、学校排课表等问题都可以转化为图的染色问题来研究解决。到目前为止,在图染色领域中,研究大都针对无向图来展开,而对于有向图,因其自身的复杂性和特殊性,染色研究则涉及较少,甚至为空白。因此,本文将着重针对有向图的染色问题进行探讨和研究。无向图的染色问题是NP完全问题,目前解决该问题的算法类型主要有顺序算法、仿生算法和其他智能算法等。这些算法大都被广泛应用于处理一些较为简单的染色问题,如无向图的正常点染色问题、正常边染色问题等。在应用中,我们可以先将一些实际问题转化为无向图,然后再利用无向图的正常点染色或正常边染色方法将其解决。另外,这些算法较多应用在无向图染色的表层领域,对于无向图更深入的染色问题,则不能给出很好的解决办法。在有向图的染色领域内,上述算法更是尚未涉猎。本文所做的主要工作就是首先给出几种有向图的染色定义,然后设计出有效的算法来解决这些定义所对应的有向图的染色问题。本文所做的工作是具有开创性的,主要包括以下几个方面:(1)从无向图染色的角度切入,根据具体的情况将染色问题进行分类;介绍一些无向图的基础染色概念,如无向图的正常点染色、边染色、全染色和在此基础上衍生出的点可区别染色和邻点可区别染色的概念;以遗传算法作为经典智能算法的代表,介绍其在无向图染色问题中的应用,同时总结遗传算法在解决无向图染色问题中的优点和不足,为研究解决有向图的染色问题提供思路和参考。(2)给出有向图的四种染色概念。首先对有向图的染色问题从整体上有个宏观的了解和把握,其次再结合具体的染色条件重点研究和讨论随机有向图的正常弧染色、正常全染色、均匀弧染色以及均匀全染色的相关理论,同时给出相关猜想值。(3)根据相关定义,针对随机有向图进行正常弧染色、正常全染色、均匀弧染色以及均匀全染色算法的设计。对于每种算法,首先根据相关的染色条件,设计出对应的约束函数和总目标函数,其次依据相应的算法思想给出算法步骤和流程图,并对算法进行测试,分析算法的正确性、有效性、时间复杂度及其测试结果,最后对算法进行总结。
【关键词】：随机有向图 正常弧染色 正常全染色 均匀弧染色 均匀全染色
【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要4-5
• Abstract5-9
• 1 绪论9-14
• 1.1 引言9
• 1.2 研究背景、目的及意义9-11
• 1.3 本文的主要工作11-12
• 1.4 本文的组织12-14
• 2 图染色理论及其算法14-25
• 2.1 引言14
• 2.2 图染色基本理论概述14-19
• 2.2.1 图的相关概念14-17
• 2.2.2 经典染色17
• 2.2.3 多条件染色17-19
• 2.3 有向图染色19-20
• 2.4 遗传算法在图染色方面的应用分析20-24
• 2.4.1 遗传算法综述20-22
• 2.4.2 遗传算法在图染色中的应用22-24
• 2.4.3 遗传算法总结24
• 2.5 本章小结24-25
• 3 随机有向图的正常弧染色及正常全染色算法25-52
• 3.1 引言25
• 3.2 随机有向图的正常弧染色算法25-42
• 3.2.1 随机有向图的正常弧染色定义及其猜想25
• 3.2.2 目标函数的构建25-26
• 3.2.3 数据结构的定义26-27
• 3.2.4 算法描述及流程图27-31
• 3.2.5 算法测试31-38
• 3.2.6 算法分析38-41
• 3.2.7 算法总结41-42
• 3.3 随机有向图的正常全染色算法42-52
• 3.3.1 随机有向图的正常全染色定义及其猜想42
• 3.3.2 目标函数的构建42-43
• 3.3.3 数据结构定义、算法描述及其流程图43-44
• 3.3.4 算法测试44-49
• 3.3.5 算法分析49-51
• 3.3.6 算法总结51-52
• 4 随机有向图的均匀弧染色及均匀全染色算法52-68
• 4.1 引言52
• 4.2 随机有向图的均匀弧染色算法52-60
• 4.2.1 随机有向图的均匀弧染色定义及其猜想52
• 4.2.2 目标函数的构建52-53
• 4.2.3 数据结构定义53
• 4.2.4 算法步骤描述及其流程图53-55
• 4.2.5 算法测试及算法分析55-59
• 4.2.6 算法总结59-60
• 4.3 随机有向图的均匀全染色算法60-68
• 4.3.1 随机有向图的均匀全染色定义及其猜想60
• 4.3.2 目标函数的构建60
• 4.3.3 数据结构定义、算法步骤描述及其流程图60-63
• 4.3.4 算法测试及算法分析63-67
• 4.3.5 算法总结67-68
• 结论68-69
• 致谢69-70
• 参考文献70-72
• 攻读学位期间的研究成果72

【共引文献】

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

1 田京京;;幂图P_n~k的邻点可区别全色数和邻点可区别-VE全色数[J];科学技术与工程;2010年15期

2 ;Equitable Total Coloring of F_n ∨ W_n[J];Acta Mathematicae Applicatae Sinica;2009年01期

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

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

2 王慧娟;可嵌入图的染色问题[D];山东大学;2014年

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

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

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

3 杨芳;几类图的点可区别正常边染色和全染色[D];西北师范大学;2014年

，

本文编号：829578