The Research Of Algorithms For Coloring Of Random Directed Graph

Graph coloring problem is an important research subject in graph theory field, whether in theory or in practice, it has widely used. For example, some typical combinatorial problem such as processing scheduling, maximum dominating set and school timetabling problem,parking problem in practice all can be transformed into the coloring problem of graph to research and solve. So far, in the coloring field of graph, the majority of the study is directed at undirected graph. Because of the specificity and complexity of the undirected graph, the coloring research was very rare or even blank in this field. So, this thesis will focus on the discussion and research for the coloring of directed graph.The coloring problem of undirected graph is a NP complete problem, right now, it has the sequential algorithm, the bionic algorithm and other intelligent algorithms can solve this problem. But these methods can only deal with some simple coloring problem, such as the problem of the proper vertex coloring of undirected graph, the problem of the proper edge coloring of undirected graph and so on. In application, we can transform the physical problem into a undirected graph, and use the method of the proper vertex coloring of undirected graph or the method of the proper edge coloring of undirected graph to solve this problem.Moreover, these algorithms usually work in the surface field about the coloring of undirected graph, but cannot give a good solution for deeply coloring problem of undirected graph, let alone in the directed graph field. In this thesis, firstly, we give some coloring definition of directed graph, and then, according to these definition, we design effective algorithm to achieve it. The work in this thesis are groundbreaking, mainly includes the following aspects:(1) For coloring of undirected graph, firstly, we classify the coloring problem according to specific situation; secondly, introduce some basic concepts about the coloring of undirected graph, such as the proper vertex coloring of undirected graph, the proper edge coloring of undirected graph, the proper total coloring of undirected graph, and based on these concepts,we introduce the concept about vertex distinguishing coloring and adjacent vertex distinguishing coloring; thirdly, we take Genetic algorithm as the representative of classical intelligent optimization algorithms, introduce its application in the coloring problem of undirected graph, and summarize advantages and disadvantages of Genetic algorithm in solving the coloring problem of undirected graph, to provide issues and references for the research on the coloring problem of directed graph.(2) We give four coloring concepts about directed graph. Firstly, we understand and grasp macroscopically the concepts about coloring of directed graph. Secondly, we combine with the specific condition of coloring to give the research about coloring of directed graph,we focus on proper arc coloring, proper total coloring,equitable arc coloring and equitable total coloring of a random directed graph. Then, we also give some related conjecture value.(3) According to the coloring definitions of random directed graph, we design algorithms for proper arc coloring, proper total coloring,equitable arc coloring and equitable total coloring of random directed graph. For each algorithm, firstly, we design the corresponding constraint function and total objective function according to coloring condition of afore-mentioned algorithm; secondly we use the corresponding algorithmic thinking to describe algorithm steps and flow chart; thirdly, we select some test data to do the test for the four algorithms, analyze the correctness of algorithm, effectiveness of algorithm, time complexity and the test results about algorithm; finally, we summarize the algorithm.