The Research Of Algorithms For Equitable Coloring Of Random Graphs

Coloring problem is a typical combinatorial optimization problem. In real life, many problems such as machining scheduling, task allocation, load balancing and so on can be solved by graph coloring. In recent years, with the development of computer technology and the need to solve practical problems, some classical intelligent algorithms are used to study and try to solve graph coloring problems, such as ant colony optimization, genetic algorithm,neural network and so on. Due to the diversity and complexity of the problem, these algorithms are generally used to solve the normal vertex and normal edge coloring of graphs.For the coloring problem with multiple constraints, there are few published literatures. So it is a theoretical and practical topic to explore new intelligent algorithms to solve the coloring problem with multiple constraints of graphs.Equitable coloring of graph is that the sizes of its color classes are differed by at most one. Equitable coloring can be used to solve some problems such as scheduling, partitioning and load balancing. From published literatures, the results of the equitable coloring algorithm are rare. The main work is to design and implement four equitable coloring algorithms according to the definition of four equitable coloring, and the random graph generation algorithm designed to test the coloring algorithms. At the same time, the analysis process of the above algorithms is given. Finally, using the test graphs, algorithm has been fully tested.Through the analysis of a large number of test results, several meaningful conclusions are given. The main research work is as follows.(1) From the view of random graph coloring, the coloring problem is classified according to the specific situation. Some basic concepts of graph coloring are introduce, such as the normal edge or total coloring of random graphs and the vertex or adjacent distinguishing coloring which can be derived from the mentioned concepts in the preceding. The applications of the classic intelligent algorithms, such as genetic algorithm and simulated annealing algorithm in the graph coloring problem are introduced. The advantages and disadvantages of genetic algorithm and simulated annealing algorithm are summarized in solving graph coloring problem. And the ideas and references are provided to solve the problem of equitable coloring of random graph.(2) Four equitable coloring algorithms are designed and implemented. According to the relevant definitions of the normal equitable edge coloring, normal equitable total coloring,vertex distinguishing equitable edge coloring and adjacent vertex distinguishing equitable edge coloring, four equitable coloring algorithms are designed. For every kinds of equitable coloring algorithm, the basic idea is to target decomposition of the problem into several sub problems. And the corresponding sub constraint functions are designed. Then according to theconstraint functions, the iterative adjustment is carried out, and each sub problem is solved step by step. Each sub problem is solved step by step. Finally, the value of the total objective function is 0 and the coloring algorithms are successful. The correctness, validity and time complexity of the algorithms are given.(3) To test the algorithm, two types of test graphs are designed, a class of 7vertices for all graphs, a class of 15 vertices for special graphs. Through the analysis of the test results,meaningful conclusions are obtained. Ideal timeslots allocated to WSN broadcast schedule can be got based on the proper equitable edge-coloring algorithm.