The Research Of Algorithms For Strongly Distinguishing Coloring Of Graph Based On Multi-objective Optimization

Graph coloring problem is one of the classic problems in graph theory,also a branch of graph theory and a basic problem in scientific computing and engineering design.There are many problems can be transformed into the graph coloring problems to solve in the real world,such as scheduling games,network communication,arranging schedule,storing material problems,wireless communication channel allocation,designing printed circuit board and index register allocation and so on,the solution of these problems involves the graph coloring theory,so the graph coloring problem is one of the most interesting fields in graph theory.With the development of the requirements of practical problems such as transportation,computer network communication,military,production management,and the evolution of the shortcomings and limitations of classical intelligent optimization algorithms in real life,we have more and more demands of achieving the coloring results quickly and accurately and applying them to reality.The strongly distinguishing coloring of graph is a multi-conditional constrained coloring,which adds a constraint on the basis of the distinguishing total coloring,so that the color set contains more elements.It includes two kinds of coloring concepts: adjacent vertex strongly distinguishing total coloring,vertex strongly distinguishing total coloring.At present,the study of strongly distinguishable total coloring problem in published papers are limited to special graphs such as circle graphs,wheel graphs,complete graphs and trees and so on,and there is no feasible solution for the study of strongly distinguishing coloring of the general random graphs.Based on the idea of multi-objective optimization,we have designed the algorithms of strongly distinguishing coloring which are based on multi-objective optimization in this dissertation.The algorithm optimizes step by step by setting all kinds of multi-objective functions,so that the final objective function to get the Pareto optimal solution,and realizes the local optimization to the whole optimization.we also have designed the algorithm of all the spanning trees within the finite vertices and the algorithm of the generation of all simple connected graphs,which lay the foundation for the research of various coloring algorithms and the result sets test.The main work of this dissertation is as follows:(1)Introduce the basic concepts of graph theory and graph coloring theory,the related concepts of multi-objective optimization problem,the basic idea of genetic algorithm and the algorithm implementation process to solve the normal edge coloring.At the same time,the advantages and disadvantages are analyzed and summarized.(2)Two generating algorithms of random graphs are given.The first is that inputing the number of vertices and connecting edges randomly in accordance with the rules to generatethe simple connected graph algorithm.The second is based on spanning tree to generate all the non pseudo-isomorphic graphs algorithm within the finite vertices.Therefore,the second algorithm contains the spanning tree algorithm.Two generating algorithms of random graphs provide basic research datas for the result sets tests,statistics of a variety of coloring algorithm and the proof of correlation lemmas,conjectures,which also lay a good foundation for the study of all kinds of coloring algorithms.(3)The adjacent vertex strongly distinguishing total coloring algorithm,vertex strongly distinguishing total coloring algorithm which are based on multi-objective optimization,a series of coloring sub-algorithms such as two kinds of normal edge coloring algorithms,vertex coloring algorithm,color set adjustment algorithm are designed and realized.The ultimate goal of the strongly distinguishing total coloring algorithm is to ensure that the color sets of the vertices are different.In addition to the vertex color,the associated edges colors of vertex,the colors of the adjacent vertex are also added,so the difficulty of the color set adjustment becomes larger.Therefore,we have designed more detailed adjustment rules of strong color set,and corresponding process evaluation function to generate new pre-coloring groups in time so that search the optimal solution more quickly.Improve the efficiency of the algorithm without increasing the time complexity of the algorithm.(4)In this dissertation,the test result sets are all the non pseudo-isomorphic graphs within 7 vertices,the special graphs within 15 vertices,all the spanning trees within 14 vertices,and the part of random connected graphs within 1000 vertices.And we have given a number of meaningful conclusions and conjectures through the analysis of a lot of experimental results sets.