The Research Of Algorithms For Coloring Of Kn\E(H) And Large-Scale Random Graphs

Graph theory is one of the most important research branches of discrete and combinatorial mathematics,and also is an important part of basic theory of computer science,and its research object is graph,it has important research value in computer theory,operations research and systems science.At present,the innovation of computer technology has become an important power of economic development and scientific research,which greatly promoted the rapid development of graph theory.Graph coloring originated in a classic question: "four color conjecture",it is one of main research direction of the graph theory,many practical problems are associated with the graph coloring,it has a good theoretical background and application value.In real life,a lot of problems such as traffic orientation,combinatorial optimization and computer communication etc.that can use graph coloring to solve.Since the modern times,many experts and scholars at home and abroad try to use the various tools and methods to study the graph coloring,series of concepts,theorem,inference and conjecture such as adjacent vertex distinguishing edge coloring,equitable coloring,weakening coloring of a graph etc.have been put forward and get the relevant theorem,inference and conjecture,as well as other new concepts.Graph coloring is a difficult problem,common intelligent algorithm such as genetic algorithm,simulated annealing algorithm,particle swarm optimization algorithm and the neural network are applied to solve the problem of graph coloring,but are generally limited to solve the coloring of single objective problem such as proper vertex coloring and proper edge coloring of graphs,and in the face of multi-objective optimization problem such as adjacent vertex distinguishing equitable total coloring,smart vertex distinguishing total coloring,the traditional intelligent optimization algorithm will mess up,its limitation is obvious.The coloring problem of the Kn \ E(H)graph is a very valuable subject.On the one hand,it is difficult to coloring by the traditional mathematical method,therefore,the computer algorithm is used to solve the coloring of Kn\E(H)is a whole new method,which can open a series of related coloring of graphs.On the other hand,in the past,for graph coloring algorithm,it is limited to smaller figure of vertices,for large-scale random graph coloring algorithm,it is difficult to achieve.This article design computer algorithm in view of the above problems to verify the correctness of the relevant theorem,inference and conjectures and provide basic research data support for related research.The main research work includes the following several part of the paper.(1)Design and complete the Kn\E(H)graph generation algorithm,and validates the validity of the graph,in preparation for the subsequent coloring algorithm.Implements the vertex distinguishing total coloring,adjacent vertex distinguishing total coloring algorithm for Kn\E(H)graph.through a large amount of experimental analysis,to verify the related theorem and conjectures.(2)It has designed and implemented large-scale random graph split algorithm and vertex distinguishing edge coloring algorithm for large-scale random graph,combine the sub-graph after coloring,so as to realize the large-scale random graph coloring.(3)There is a detail description of algorithm test,and also analyze the time complexity of the algorithm,it shows that the algorithm has the correctness and a good performance.