随机图的均匀染色算法研究

发布时间：2017-10-19 12:38

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

  更多相关文章： 随机图 图染色 均匀边染色 均匀全染色

【摘要】：图染色问题是一种典型的组合优化问题,现实生活中的很多问题如加工调度、任务分配、负载平衡等都可以用图染色的方法来解决。近些年来,随着计算机技术的发展和解决实际问题的需要,一些经典的智能算法被用来研究和尝试解决图染色问题,如蚁群算法、遗传算法、神经网络等,但限于染色问题的多样性和复杂性,目前这些算法普遍应用于解决图的正常点染色和正常边染色,而对于图染色问题中多约束条件的染色问题,公开发表的文献中尚不多见,因此寻求新的智能算法来解决图的多约束条件染色问题是一个具有理论和实际意义的课题。图的均匀染色是指图中任意两个色类的颜色个数最大相差1,在解决生产调度、任务分配和负载均衡等问题方面有很好的应用,从已公开发表的文献看,有关图的均匀染色算法的成果少见。本文所做的核心工作就是根据四种均匀染色的定义,分别设计并实现了四种均匀染色算法,以及为了测试算法而设计的随机图生成算法,同时给出对上述算法的分析过程,最后利用设计的测试图集对算法进行了全面测试,通过对大量测试结果的分析给出了几个有意义的结论。本文主要工作如下:(1)从随机图染色的角度切入,根据具体的情况将染色问题进行分类;介绍一些图的基础染色概念,如正常边染色、全染色和在此基础上衍生出的点可区别染色和邻点可区别染色的概念;以遗传算法和模拟退火算法作为经典智能算法的代表,介绍其在图染色问题中的应用,同时总结遗传算法和模拟退火算法在解决图染色问题中的优点和不足,为研究解决图的均匀染色问题提供思路和参考。(2)设计并实现四种均匀染色算法。根据图的均匀边染色、均匀全染色、点可区别均匀边染色和邻点可区别均匀边染色的定义,设计了四种算法,每种算法的基本思想是将目标问题分解成几个子问题,设计相应的子约束函数,然后根据这些子约束函数进行迭代调整,逐步解决每个子问题,最终使得总目标函数的值为0,染色成功,算法结束。文中给出了针对算法的正确性、有效性和时间复杂度的分析过程。(3)设计了两类测试图集对算法进行测试,一类为7个点以内的所有图,一类为15个点以内的特殊图。通过对测试结果的分析,得到了有意义的结论。基于正常均匀边染色算法对无线传感器网络广播调度进行时隙分配,得到了较为理想的结果。
【关键词】：随机图 图染色 均匀边染色 均匀全染色
【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要4-5
• Abstract5-10
• 1 绪论10-14
• 1.1 引言10-11
• 1.2 研究背景、目的及意义11-12
• 1.3 本文的主要工作12
• 1.4 本文的组织结构12-14
• 2 图染色相关概念及经典算法概述14-22
• 2.1 引言14
• 2.2 图染色基本定义和猜想14-16
• 2.3 遗传算法在图染色中的应用16-19
• 2.3.1 遗传算法的基本思想16
• 2.3.2 遗传算法的基本步骤16
• 2.3.3 遗传算法的图染色中的应用16-19
• 2.4 模拟退火算法19-21
• 2.4.1 模拟退火算法的基本思想19
• 2.4.2 模拟退火算法的基本步骤19-20
• 2.4.3 模拟退火算法在图染色中的应用20-21
• 2.5 本章小结21-22
• 3 图的生成算法22-32
• 3.1 引言22
• 3.2 随机图的生成算法22-25
• 3.2.1 随机图的定义和模型22
• 3.2.2 算法描述及流程图22-24
• 3.2.3 算法测试24-25
• 3.3 生成有限点数所有图算法25-31
• 3.3.1 定义主要数据结构及生成树25-26
• 3.3.2 算法描述及流程图26-29
• 3.3.3 算法测试29-31
• 3.3.4 实验结果31
• 3.4 本章小结31-32
• 4 随机图的正常均匀边染色及正常均匀全算法32-55
• 4.1 引言32
• 4.2 正常均匀边染色算法32-43
• 4.2.1 正常均匀边染色的相关定义和猜想32
• 4.2.2 目标函数的构建32-33
• 4.2.3 主要数据结构的定义33-34
• 4.2.4 正常均匀边染色算法描述及流程图34-36
• 4.2.5 算法测试36-41
• 4.2.6 算法分析41-42
• 4.2.7 实验结果42-43
• 4.3 正常均匀全染色算法43-53
• 4.3.1 正常均匀全染色的相关定义和猜想43-44
• 4.3.2 目标函数的构建44-45
• 4.3.3 正常均匀全染色算法描述及流程图45-47
• 4.3.4 算法测试47-50
• 4.3.5 算法分析50-52
• 4.3.6 实验结果52-53
• 4.4 本章小结53-55
• 5 随机图的可区别均匀边染色算法55-75
• 5.1 引言55
• 5.2 邻点可区别均匀边染色算法55-64
• 5.2.1 邻点可区别均匀边染色的相关定义和猜想55
• 5.2.2 目标函数的构建55-56
• 5.2.3 邻点可区别均匀边染色算法描述及流程图56-59
• 5.2.4 算法测试59-62
• 5.2.5 算法分析62-63
• 5.2.6 实验结果63-64
• 5.3 点可区别均匀边染色算法64-74
• 5.3.1 点可区别均匀边染色的相关定义和猜想64-65
• 5.3.2 目标函数的构建65
• 5.3.3 点可区别均匀边染色算法描述及流程图65-67
• 5.3.4 算法测试67-71
• 5.3.5 算法分析71-72
• 5.3.6 实验结果72-74
• 5.4 本章小结74-75
• 6 基于均匀边染色的无线传感网络广播调度算法75-79
• 6.1 引言75-76
• 6.2 TDMA时隙分配76
• 6.3 均匀边染色算法解决广播调度问题76-78
• 6.3.1 步骤描述77
• 6.3.2 算法结果及分析77-78
• 6.4 本章小结78-79
• 结论79-80
• 致谢80-81
• 参考文献81-84
• 攻读学位期间的研究成果84

【参考文献】

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

1 彭煜q;;浅谈无线传感器网络中的数据隐私保护技术[J];科技展望;2016年13期

2 岳鹏;王柯;郑杰;;一种基于优先级的TDMA时隙接入算法[J];无线互联科技;2016年04期

3 李敬文;张云寒;陈志鹏;孙亮;;图的点可区别边染色算法研究[J];计算机应用研究;2014年03期

4 冯珊珊;张月琴;郭旭敏;;基于改进图着色理论的聚类算法[J];计算机工程与设计;2013年05期

5 李敬文;于自强;;基于立方体染色的排课表模型[J];计算机工程;2010年24期

6 马刚;马少仙;张忠辅;;一些联图的均匀全染色[J];应用数学学报;2010年04期

7 邓宇;汪黎;晏小波;王桂彬;唐滔;;基于超完美图着色的存储分配算法[J];计算机科学;2008年09期

8 马刚;马少仙;张忠辅;;关于W_m∨S_n的均匀全染色[J];数学研究;2007年03期

9 文军,李冰,王清蓉,杜文;机场停机位分配问题的图着色模型及其算法[J];系统工程理论方法应用;2005年02期

10 ;On adjacent-vertex-distinguishing total coloring of graphs[J];Science in China,Ser.A;2005年03期

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

1 张佳丽;关于图的若干染色问题的研究[D];中国矿业大学;2014年

2 王聪;基于图谱理论在图弱染色方面的算法研究[D];兰州交通大学;2014年

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

4 桂浩;图的均匀点染色与均匀全染色[D];浙江师范大学;2014年

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

，

本文编号：1061167