The Research Of Algorithms For Distinguishing Colorings Of General Graph

Graph coloring problem is an important research field in graph theory, and it has theimportant theory significance and strong application value.It can be used to solve a number oftypical combinatorial problems such as maximum dominating sets, processing andscheduling,and some practical problems like the establishment of the parking lot, the deliveryand collection of the goods. In recent years, some classical intelligent optimization algorithmssuch as tabu search algorithm, genetic algorithm and ant colony algorithm are applied to workout the graph coloring problem.But most of these algorithms are specific to the propervertex,edge or total colorings problem,and the research about distinguishing colorings is notthat rich. In addition, as the graph scale getting larger and larger, coloring problem would bemore and more complex.The running time of above algorithms may increase significantly,and their search performance and convergence has declined dramatically. In this thesis, themain research is to design new algorithms, respectively to solve vertex distinguishing edgecolorings, vertex distinguishing total colorings, adjacent vertex distinguishing edgecolorings,adjacent vertex distinguishing total colorings. And the algorithms have highefficiency, good convergence, break the limitation of the classical algorithms.In this thesis,the main research work is as follows:(1) Some classical concepts such as proper vertex colorings,proper edge colorings andtotal colorings, and the vertex-distinguishing colorings and adjacent-vertex-distinguishingcolorings which come from the proper colorings. And classical optimization algorithms suchas tabu search and genetic algorithm are introduced, including their applications in graphcoloring problem, and the analysis of their shortcomings and the insufficiency, in order toavoid or improve them in this paper.(2) This thesis designs new vertex-distinguishing colorings algorithms of generalgraphs,including vertex distinguishing edge colorings and vertex distinguishing totalcolorings. Firstly it builds an object function and data structure,gives steps and flow chartaccording to the thought of vertex distinguishing edge colorings algorithm,analyzes itscorrectness and convergence after testing. Secondly according to the vertex distinguishingtotal colorings algorithm thought the paper gives steps and flow chart and test thisalgorithm,analyzes the correctness and space complexity.Finally,summarizes this twoalgorithms.(3) This thesis designs new adjacent-vertex-distinguishing colorings algorithms ofgeneral graphs,including adjacent vertex distinguishing edge colorings and adjacent vertexdistinguishing total colorings. Firstly the paper improves the vertex distinguishing edgecolorings algorithm, gets a new algorithm to work out the adjacent vertex distinguishing edge colorings problems effectively,and achieves the expected experimental results after testing.Secondly according to the adjacent vertex distinguishing total colorings algorithm thought thepaper gives steps and flow chart and test this algorithm,analyzes the time complexity.Finally,summarizes this two algorithms.