随机图的可约染色算法研究

发布时间：2018-01-24 05:51

本文关键词： 随机图图染色点可约染色邻点可约染色　出处：《兰州交通大学》2015年硕士论文　论文类型：学位论文

【摘要】：现实生活中有很多实际问题是将某种对象的集合按照一定的规则进行分类的,而图染色问题恰好是按照某种规则对图中的顶点、边等元素进行分类的,所以很多实际问题都可以抽象成图,并利用图染色的方法解决。图染色问题是图论研究领域的主要方向,国内外的专家学者们已经做了大量的研究工作来寻求解决各种染色问题的具体方法。常见的有经典的智能算法,如遗传算法、模拟退火算法等。对于较小规模的图来说,使用这些算法来解决图染色问题时可以得到最优解或次优解。但是当要求解的图的规模增大时,算法的时间复杂度及算法的效率都会受到很大影响。另外,这些算法只能用来解决点染色、边染色这2个基本的染色问题,对于本文要研究的染色条件稍微复杂的可约染色,这些算法是解决不了的,所以需要寻求新的算法来解决。对于图的可约染色问题,在已公开发表的文献中只是给出了相关的定义,或是针对特殊图如星扇轮等给出了一些有用的结论,具体解决问题的方法目前还没有。所以本文针对随机图(无向简单连通图)的点可约边染色、点可约全染色、邻点可约边染色、邻点可约全染色4个问题,提出了相应的解决方案。本文的主要研究工作有以下几个方面。(1)介绍了图论及图染色的发展过程,给出了本文的研究目的及意义。(2)介绍了经典的智能算法在图染色中的应用,分析了这些算法的优点及不足。(3)针对随机图,设计了4个启发式多目标优化算法,分别实现了点可约边染色、点可约全染色、邻点可约边染色、邻点可约全染色问题。对于点可约染色,其基本思想是将目标问题分解成几个子问题,设计相应的子约束函数,然后根据这些子约束函数进行迭代调整,逐步解决每个子问题,最终使得图中度数相同的所有顶点其色集合相同,此时总目标函数的值为0,染色成功,算法结束。相比点可约染色,邻点可约染色算法的基本思想是通过逐步迭代调整使得图中度数相同且相邻的顶点其色集合相同。文中首先对算法都进行了详细的描述;其次分别对4个算法进行了测试,同时也给出了部分实验的结果;再次从正确性、收敛性(单调性、有界性)以及时间复杂度3个方面对算法进行了详细分析,得到算法的时间复杂度为O(n3);最后对4个算法进行了总结。
[Abstract]:In real life, there are many practical problems in classifying the set of certain objects according to certain rules, while the problem of graph coloring happens to classify the vertex and edge elements in a graph according to some rules. So many practical problems can be abstracted and solved by the method of graph coloring, which is the main direction of graph theory research. Experts and scholars at home and abroad have done a lot of research to find specific solutions to various dyeing problems. Classical intelligent algorithms such as genetic algorithms are common. For smaller graphs, the optimal solution or suboptimal solution can be obtained by using these algorithms to solve the graph coloring problem. However, when the size of the graph required for the solution increases. The time complexity and efficiency of the algorithm will be greatly affected. In addition, these algorithms can only be used to solve the two basic coloring problems: point coloring and edge coloring. For the reducible coloring with slightly complicated coloring conditions, these algorithms cannot be solved, so we need to find new algorithms to solve the problem of reducible coloring of graphs. In the published literature, only the relevant definitions are given, or some useful conclusions are given for special graphs such as star fan wheels. At present, there are no specific solutions to the problem, so this paper deals with four problems: vertex reducible edge coloring, vertex reducible total coloring, adjacent point reducible edge coloring and adjacent point reducible total coloring for random graphs (undirected simple connected graphs). The main research work in this paper is as follows: (1) the development process of graph theory and graph coloring is introduced. The purpose and significance of this paper are given. (2) the application of classical intelligent algorithms in graph coloring is introduced, and the advantages and disadvantages of these algorithms are analyzed. Four heuristic multi-objective optimization algorithms are designed to realize the problem of point-reducible edge coloring, point-reducible total coloring, adjacent point-reducible edge coloring and adjacent point-reducible total coloring respectively. The basic idea is to decompose the objective problem into several sub-problems, design the corresponding sub-constraint functions, and then iteratively adjust them according to these sub-constraint functions to solve each sub-problem step by step. Finally, all the vertices with the same degree in the graph have the same chromatic set, the total objective function is 0, the coloring is successful, and the algorithm ends. The basic idea of the adjacent point reducible coloring algorithm is to adjust the degree of the graph to the same degree and the adjacent vertices to the same chromatic set by iterating step by step. Firstly, the algorithm is described in detail. Secondly, four algorithms are tested, and some experimental results are given. Thirdly, the algorithm is analyzed in detail from three aspects: correctness, convergence (monotonicity, boundedness) and time complexity. Finally, four algorithms are summarized.
【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】