Research On Vertex Sum Reducible Coloring Algorithm Of Random Graph

As an interdisciplinary subject of mathematics and information science,graph theory takes graph as its research object,abstracts real problems into graphs,and is widely used in various fields,such as matrix operation,task scheduling,network communication,goods storage,frequency allocation,etc.Graph coloring is one of the important directions of graph theory.It also transfers the practical problems in life into graph theory model,and the problems can be solved by graph coloring according to certain rules.At present,a large number of scholars have done a lot of discussion and research on graph coloring,specific methods have been found for various kinds of coloring problems,which mainly based on the search solution space and the objective function.The coloring algorithm based on search solution space generally is used to solves vertex coloring,edge coloring and total coloring;the coloring algorithm based on objective function solves adjacent vertex sum distinguishing coloring,vertex distinguishing coloring,strong edge coloring and vertex reducible coloring with more constraints.These two kinds of graph coloring algorithms only aim at some special graph coloring or special graph sets(W_n、K_n、K_n,n、C₃^（n）、mC_n、D（G）、S_n+F_n、W_n+F_n、M_n（C_p）)to obtain related results.But with the increasing of coloring conditions,the traditional coloring algorithm will not be able to solve the new coloring,it is necessary to find a new coloring algorithm to solve it.Therefore,in this thesis,we study the three problems of vertex sum reducible edge coloring,vertex sum reducible total coloring,adjacent vertex sum reducible edge coloring of random graphs,propose specific solutions to these three problems,and design related vertex sum reducible coloring algorithms.The main research work of this paper is as follows:（1）This thesis introduces the related concepts of graph coloring,the research status of（adjacent）vertex reducible edge（total）coloring,（adjacent）vertex sum reducible edge（total）coloring,and the differences between the research methods of vertex sum reducible coloring and traditional graph coloring.（2）A vertex sum reducible edge coloring algorithm based on step-by-step optimization is designed and completed.Firstly,the algorithm is based on the definition of vertex sum reducible edge coloring and the idea of gradual optimization.Secondly,the algorithm is implemented to obtain the vertex sum reducible edge coloring matrix and maximum coloring number of 12205208 non isomorphic graphs within 10 vertices,522957 non isomorphic graphs within 19 vertices,unicyclic graphs and bicyclic graphs within 15 vertices.The statistical results are analyzed to obtain the vertex sum reducible edge coloring conclusions and conjectures of some graphs.In addition,in order to optimize the vertex sum reducible edge coloring algorithm,two other vertex sum reducible edge coloring algorithms are designed,which are rule-based vertex sum reducible edge coloring algorithm and equation based vertex sum reducible edge coloring algorithm.Through the test of these three algorithms and the comparison of the result set,it is concluded that the algorithm based on the step-by-step optimization is better than the other two algorithms in performance and complexity.（3）Designing and implementing the vertex sum reducible total coloring algorithm and the adjacent vertex sum reducible edge coloring algorithm.The two algorithms are used to process the graph data set,and the two kinds of vertex sum reducible coloring of 12205208 random graphs within 10 vertices and special graphs within 12 vertices are obtained.Finally,some theorems of join graph and special graph are proved by result set analysis.