The Research Of Algorithm For Strong Vertex-distinguishing Total Coloring

Graph coloring problem is a classic difficult problem of graph theory. It is a fundamental problem in scientific computation and engineering design. In fact, several classes of reallife problems such as examination timetabling and frequency assignment can be modeled as Graph Coloring Problem extensions. One of graph edge coloring and graph total coloring problem, as well as whole graph chromatic number problem can be converted to graph vertex coloring to deal with problem. Because graph coloring problem belongs to NP complete problems, it can not get the optimal solution in polynomial time. Now there are some special algorithms such as Genetic Algorithm, Neural Network and Simulated Annealing Algorithms are effective ways to solve NP-complete problem. However, in the case of larger scale, especially in the studying of strong vertex-distinguishing total coloring for complete graph, they will show some of the inevitable shortcomings. The main research works in this article are as follows:(1) Studying and analysising special algorithms (such as Genetic Algorithms, Neuual Networks and Simulated Annealing Algorithms) based on the proper K-vertex coloring, and applied to the strong vertex-distinguishing total coloring on complete graph on complete graph, then analysises a series of questions as well as the consequences after the application .The results indicate that these algorithms are not suited on this problem.(2) Combining the feature of complete graph and strong vertex-distinguishing total coloring, it puts the required coloring divided into two parts: overcolor and propercolor when getting the chromatic number of complete graph on strong vertex-distinguishing total coloring. And the focus of the algorithm is coloring overcolor. This article studies the coloring thought of overcolor and skillfully achieves it. Describing the algorithm at .net environment using VB language, it gets the expected results on any point of strong vertex-distinguishing in short time.The experimental results verify that the algorithm has a faster speed and higher convergence rate. Algorithm can also be modified to get the coloring ruselts on complete graph, such as adjacent vertex-distinguishing edge coloring, adjacent vertex-distinguishing total coloring, vertex-distinguishing edge coloring, vertex-distinguishing total coloring,etc...(3) Analysis of the characteristics of road and circle, reasoning by the circle strong vertex-distinguishing total coloring of the chromatic number, this paper designed an algorithm at.Net environment verifying and getting 12 points within 5 colors results, which in a short time can not be completed using hand-dyed.