The Research And Implementation Of Graph Coloring Software System

With the rapid development of information science and network technology,because of the intuitive graphics and strict logic of graph theory,it has received more and more attention and research in the majority of experts and scholars.Many problems can be transformed into the graph matching models,such as large-scale information communication,social network,big data collection and analysis,internet of things etc,all of that have complex networked and structured characteristics.Graph theory has the characteristics that can abstract and transform the complex structure problems into clear structures with vertex and edge,Take graph as a tool to solve these problems is a new and effective solution,and then abstract the method of graph coloring to be resolved.Therefore,the research and innovation of the graph coloring problem is very meaningful.Graph coloring problem is NP complete problem.When some classical intelligent algorithms such as genetic algorithm,particle swarm algorithm,neural network algorithm and so on are used to solve graph coloring problems,they can only solve single constraint condition coloring problems,such as normal vertex coloring and normal edge coloring,but there are no good results published for multi-constraint condition coloring problems such as total coloring,distinguishing coloring and so on.In this thesis,three coloring algorithms are designed and implemented for solving multi-constraint condition coloring problems,and then combined with part of the graph distinguishing coloring algorithms published to design and implement the graph coloring software system?GCSS?.It is a research platform for graphic scholars,enthusiasts and other researchers who use graph coloring technology to solve practical problems.Users only need to select the coloring method,the number of vertex,edge density and other parameters,the software platform will correctly give the five kinds of distinguishing coloring results of all simple connectivity graphs within limited vertices?100 vertice?.These results provide basic research datas for graphic scholars and enthusiasts,and help for scientific researchers who intend to use graph theory technology to solve combinatorial optimization issues such as computer communicating,course arranging,task scheduling and warehouse allocating.The main research work is as follows:?1?Introduce conjecture for vertex distinguishing edge chromatic number of K_p\E(k_1,m),designe and achieve the algorithm for proving conjecture.Describe the algorithm steps in detail,and test algorithm for the correctness.Based on this algorithm,we have tested all of K_p\E(k_1,m) graphs within 2000 vertices,the test results show that the conjecture is established.?2?Designe and achieve algorithm for vertex distinguishing equitable total coloring of random graph.The whole idea of the algorithm is to decompose the coloring problem into several sub-target problems according to the constraints,when all sub-targe problems are successfully sovled,the coloring is successful and the algorithm end.In this paper,the detail process and test cases of the algorithm are given,and the correctness and time complexity of the algorithm are analyzed.?3?Based on OpenMP technology,the parallel algorithm for arc coloring of random directed graph was designed and implemented.The algorithm searches coloring solution space parallelly through multi-thread,and thus reduce the time required for successful coloring,improve the efficiency of coloring.The experimental results show that the algorithm can effectively reduce coloring time.?4?Based on JNI technology to realize the combination of graph coloring algorithm and the Java platform,based on JGraph technology to realize results visualization,graph coloring software system was designed and implemented.It includes the following six functional modules: graph coloring introduction module,graph display module,graph generate module,graph coloring validation module,graph coloring algorithm module,graph coloring conjecture prove module.For the graph coloring algorithm module,which have contain the vast majority of graph coloring algorithms of graph coloring field,So the system can provide a comprehensive research platform for graph theory researchers,enthusiasts and other researchers who use graph coloring technology to solve practical problems.