随机图的色和可区别染色算法研究

发布时间：2018-11-10 17:31

【摘要】：现实生活中许多复杂的问题都可通过分类、抽象、简化的思想转化成图论问题进行研究解决,如最大支配集、加工调度、任务分配、排课表等典型的组合类问题,而图染色作为图论中一个重要的研究分支,是解决实际问题的一个重要途径。近些年来,一些经典的智能算法被用来研究和尝试解决图染色问题,如粒子群算法、遗传算法、神经网络算法等,但目前这些算法普遍仅应用于解决图的正常点染色和正常边染色,而对于图染色问题中多约束条件的染色问题,公开发表的文献中尚不多见,因此寻求新的智能算法来解决图的多约束条件染色问题是国内外图论研究者都感兴趣的一个重要课题。图的邻点色和可区别染色问题,在已公开发表的文献中对它们的研究都局限于如正则图、星图、完全图等的特殊图,尚无解决一般图的邻点色和可区别染色、点和可区别染色问题的方法。本文根据两种图的色和可区别染色的定义,分别设计了基于多目标优化的染色算法,对算法的正确性、收敛性和复杂度进行了分析,并通过大量的实例测试,得到了一些很有意义的结果。本文的具体工作如下:⑴介绍了一些基本染色概念及相关猜想,并同时给出有关内容的研究背景及目前国内外的研究动态。⑵介绍了两个经典的智能算法(粒子群算法、遗传算法)的基本思想、流程,及其在图染色中的应用,并对这些算法在解决图染色问题的性能上进行了分析。⑶给出了随机图的生成算法和生成有限点数所有伪非同构图的算法,详细描述了算法步骤,并分别对这两种算法进行了算法测试,为之后染色算法的研究提供了基础数据支持。⑷设计并实现了图的色和可区别染色问题中的邻点和可区别边染色、邻点和可区别全染色、点和可区别边染色和点和可区别全染色四个智能优化算法。四个算法的整体思路都是将其染色问题分解为多个特定功能模块的子问题,依次按序通过对子问题的逐步迭代调整直到子问题解决成功,之后以不改变前一子问题的成功状态为前提解决后一个子问题,当所有子问题都成功解决后,即代表该染色成功,算法结束。文中给出了算法的详细流程及测试案例,分析了算法的正确性、收敛性和时间复杂度,测试实例为7个点以内所有伪非同构图和1000个点以内边密度较小的1万个随机连通图,通过对实验结果的分析,表明算法具有较好的执行效率和不算高的时间复杂度,同时给出了若干有意义的经过验证的结论。
[Abstract]:In real life, many complex problems can be solved through classification, abstraction and simplification of ideas into graph theory problems, such as maximal dominating set, processing scheduling, task assignment, scheduling and other typical combinatorial class problems. As an important branch of graph theory, graph coloring is an important way to solve practical problems. In recent years, some classical intelligent algorithms have been used to study and try to solve graph coloring problems, such as particle swarm optimization algorithm, genetic algorithm, neural network algorithm and so on. However, these algorithms are generally only used to solve the problem of normal point coloring and normal edge coloring of graphs. However, there are few published literatures on the problem of multi-constraint coloring in graph coloring problems. Therefore, finding a new intelligent algorithm to solve the multi-constraint coloring problem of graphs is an important topic of interest to graph theorists both at home and abroad. The problems of adjacent vertex coloring and discernible coloring of graphs are confined to the special graphs such as regular graphs, star graphs, complete graphs, etc. In the published literatures, there is no solution to the adjacent coloring and distinguishing coloring of general graphs. The method of point and distinguishing coloring problem. According to the definition of color and distinguishing coloring of two kinds of graphs, this paper designs a coloring algorithm based on multi-objective optimization, and analyzes the correctness, convergence and complexity of the algorithm. Some meaningful results have been obtained. The specific work of this paper is as follows: 1. Some basic coloring concepts and related conjectures are introduced, and the research background and current research trends at home and abroad are also given. 2 two classical intelligent algorithms (particle swarm optimization algorithm) are introduced. The basic idea, flow, and application of genetic algorithm in graph coloring, The performance of these algorithms in solving the problem of graph coloring is analyzed. 3 the generating algorithm of random graph and the algorithm of generating all pseudo-nonisomorphic graphs with finite number of points are given, and the steps of the algorithm are described in detail. The two algorithms are tested respectively, which provides basic data support for the research of later coloring algorithms. 4. The design and implementation of adjacent points and distinguishing edge coloring, adjacent points and differentiable total coloring in the chromatic and discernible coloring problem of graphs are carried out. Point and distinguishing edge coloring and point and differentiable total coloring are four intelligent optimization algorithms. The whole idea of the four algorithms is to decompose the coloring problem into subproblems of several specific function modules, and then adjust the subproblems step by step through the iterative adjustment of the sub-problems in order until the sub-problems are solved successfully. After that, the successful state of the former sub-problem is not changed as the premise to solve the latter sub-problem. When all the sub-problems are solved successfully, the coloring is successful, and the algorithm ends. In this paper, the detailed flow and test cases of the algorithm are given, and the correctness, convergence and time complexity of the algorithm are analyzed. The test examples are all pseudo-nonisomorphic graphs within 7 points and 10,000 random connected graphs with less edge density within 1000 points. Through the analysis of the experimental results, it is shown that the algorithm has good execution efficiency and not high time complexity. At the same time, some meaningful and verified conclusions are given.
【学位授予单位】：兰州交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5

【参考文献】