The Research Of Algorithms For Distinguishing Coloring Of Graph

Graph coloring problem is an important research topic of graph theory. It has a goodapplication background both in theory and in engineering. Graph coloring problem belongs toNP complete problems. Some intelligent optimization algorithms such as Genetic Algorithms,Neural Networks, Simulated Annealing Algorithm have been widely used in solvingcombinatorial optimization and NP complete problem.However, with the scale of the problemexpanding, the running time of the algorithm will increase substantially and the convergencerate of the algorithm will also drop greatly.In this case, the efficiency of the algorithm will beaffected seriously.Currently,traditional intelligent optimization algorithms,which solve the graph coloringproblems, are mainly aimed at proper vertex(edge).From the open literatures that have beenpublished,there are few intelligent optimization algorithms to solve distinguishing coloring.Therefore,to solve problems of vertex-distinguishing edge coloring of graphs and vertex-distinguishing total coloring of non-regular graphs, new algorithms are designed according tothe characteristics of them and the experimental results show that the new algorithms are ideal.The main research works in this paper are as follows:(1)The application of classical algorithms (such as Genetic Algorithm, Neural Networksand Simulated Annealing Algorithm) in graph coloring is analysed, and the questions after theapplication of Genetic Algorithms in graph coloring are researched especially.The resultsshow that the efficiency of these algorithms for solving vertex-distinguishing edge coloring ofgraph is not good, on the other hand these algorithms are too general and short of aim forbeing used to solve vertex-distinguishing total coloring of non-regular graphs.(2)This paper has profoundly studied the concepts and critical technologies of graphcoloring, including:equitable coloring，￡)(々）-coloring,construction of probability function andconstruction of constraint function with coloring conditions.This paper focused on applicationof probability function in graph coloring,summarized and deepened the construction of theconstraint functions.(3)This paper designed a new vertex-distinguishing edge coloring algorithm of generalgraphs and tested it.The algorithm combined probability and graph coloring,and also used therandom function.lt got constraint function according to the features of vertex-distinguishingedge coloring and established the final objective function.This new algorithm has been testedin general graphs and complete graph, and achieved the expected experimental results.(4)This paper has designed and realized the D{if)-vertex-distinguishing total coloring algorithm for non-regular graphs whose maximum degree are greater than2and further testedit.According to the idea of algorithm,all vertices and edges to be colored are sorted by theirdegrees in descending order，and the greater degree it is，the topper priority to be colored thevertex and its incident edges may get.And this algorithm also simpliifed coloring process byintroducing constraint rules table creatively, therefore greatly improved its eiffciency.Thisalgorithm has been programmed in VC++environment with C language,and got the expectedresults for a short time, verifying that the algorithm has a much faster running speed and highconvergence speed.