The Research Of Algorithms For D(β) Colorings Of Random Graph

Graph theory is a main research area in discrete mathematics. There are many problems in real life which can be abstracted into a chart and can be solved by using knowledge of graph theory. Graph coloring is an important research direction in graph theory, there are many problems about combinational optimization, processing schedule and the biggest dominating set etc. in theory and engineering. Thus, the graph coloring has been widely studied by experts and scholars both at home and abroad, and obtained a lot of valuable research results.Graph coloring problem is NP-complete problem, right now, the bionic algorithm and intelligent optimization algorithm such as Genetic Algorithm, Simulated Annealing Algorithm, Neural Network are main methods to solve this problem. However, these traditional intelligent algorithms are confined to solve the two basic coloring problems containing the normal vertex coloring and normal edge coloring. For the D(β)- vertex distinguishing coloring whose coloring conditions is more complex, there is not a found an algorithm in public. The paper is aim at designing a new algorithm to solve this problem.In 2006, Prof. Zhang et al. presented the concepts of D(β)- vertex distinguishing edge coloring and the D(β)- vertex distinguishing total coloring definition and related conjectures. After that, some useful conclusions about special graphs such as road, stars, fans, wheels, and complete graph, etc. also are obtained, but there is no solution for the general graph. So the new algorithm for random graphs is put forward to solve D(β)- vertex distinguishing edge coloring and D(β)- vertex distinguishing total coloring. The main research works are given as follows.(1) Design and implement the algorithm about generating random graph and all nonisomorphic graphs of limited points. Then obtain the series the results by respectively testing these two algorithms, which prepare for testing of coloring algorithm.(2) Design and implement two heuristic multi-objective optimization algorithms for any simple connected graph to achieve D(β)- vertex distinguishing edge coloring and D(β)- vertex distinguishing total coloring. According to the definition, multiple constraint conditions of coloring are designed into the sub objective functions, and the value of the total objective function is designed as the sum of the sub objective function values. Each sub objective function is iteratively operated, and the optimal solution is gradually obtained. At this time, coloring success. The correctness, convergence and complexity of the algorithm are analyzed.(3) A detailed testing scheme is designed, and a large number of results are obtained. Through the analysis of the experimental results, two important conclusions are obtained. At the same time, it also shows that the two coloring algorithms have good execution efficiency.