The Research Of Algorithms For Sum Distinguishing Coloring Of Random Graph

In real life, many complex problems can be studied and fixed by classification, abstract,simplified thought into graph theory problems, such as some typical combination problems,including maximum dominating sets, processing and debugging, task allocation, course arrangement table in practice etc. As an important research branch of graph theory, Graph Coloring is an important way to solve the problem of graph theory. In recent years, some of the classic intelligent algorithms are used to study and solve graph coloring problems, such as particle swarm algorithm, genetic algorithm, neural network algorithm etc. But at present,these algorithms generally be used to solve normal edge coloring and normal total coloring,and in the open literatures they are infrequently used to solve the graph coloring problems with multi-constrained conditions. Therefore, it has become an important and interested subject to find a new intelligent algorithm to solve the problem of graph coloring with multi-constrained conditions for Researchers at home and abroad.For the neighbor sum distinguishing coloring of graph, the study of the problems in the published papers are limited to special graphs, such as regular graphs, charts, complete graphs etc and still can not solve the neighbor sum distinguishing coloring of general graph.So far,There is no relevant research published on the point of the sum distinguishing coloring of graph. According to the definition of these two kinds of sum distinguishing coloring problems,the corresponding algorithm which is based on multi-objective optimization is designed in this paper, and the accuracy, convergence and time complexity of the algorithm are analyzed,and some useful results are acquired by lots of test.The main research work is as follows:(1) Introduce some basic concepts and conjectures of the colorings, and give a survey of the research background,the domestic and foreign research trends.(2) Introduce two classical algorithms, including the basic idea,process and application in particle swarm algorithm and genetic algorithm and analyse the performance of algorithm in solving the graph coloring problem.(3) Give the generating algorithm of random graphs and all non isomorphic graph algorithm for generating finite point number. Describe the algorithm steps in detail, test these two algorithms. These provide the basic data support for the study of post dyeing algorithm.(4) Designe and achieve the four intelligent algorithms in sum distinguishing coloring of graph which are neighbor sum distinguishing edge coloring algorithm, neighbor sum distinguishing total coloring algorithm, sum distinguishing edge coloring algorithm and sum distinguishing total coloring algorithm. The whole idea of the four algorithms are as follows:the coloring problem is decomposed into sub problems of a number of specific functional modules. Iterate according to the functions gradually, and make the sub problems be solved.Take the success of the previous sub problem as premise to solve a sub problem, when all the sub problems are successfully solved, which represents the success of the coloring,the algorithm ends. The detailed flow and testing of the algorithm are given, and the accuracy,convergence and time complexity of the algorithm are analyzed, the test cases are non-isomorphism graphs within 7 vertexs and 10000 random connected graphs under the condition of smaller edge density within 1000 vertexs. The results showed that these algorithms have high efficiency and not high time complexity, and several conclusions have been given.