The Research Of Algorithms For Chemical Graph Theory And Large-scale Graph Coloring

Graph theory is an important branch of mathematics,and it is also the basis of basic subjects such as computers.It is based on graphs,Many problems in reality can be abstracted as graphs,which can be solved by the application problems of graph theory,such as the problem of traveling around the world proposed by the famous mathematician Hamilton,traveling salesman problems,and Sudoku games;In engineering,resource distribution and scheduling problems and combinatorial optimization problems,Communications channel allocation,circuit layout issues,These problems can be solved by using the knowledge of graph theory.With the development of society and the advancement of science and technology,the study of graph theory is not limited to mathematical reasoning and proof,but it is intertwined with many disciplines.In recent years,graph theory research has made great progress.It has been widely used in computer science,communications networks,information science,artificial intelligence,image processing,physics,and chemistry,and it also has achieved many important research results.A common application of graph theory is the field of organic chemistry.As early as half a century ago,when Gunthard and Primas studied the Huckel theory in chemistry,they proposed the 'which graphs were determined by the spectrum?',The solution of this problem involves Graph's Spectral Theory.It is mainly about whether the graph is uniquely determined by the spectrum by the quantitative characteristics of the graph matrix,otherwise to find the same spectrum couple.then,the famous mathematical chemist Gutman proposed the theory of energy of graph,which is the theory of studying the relevant properties of chemical molecules by spectra.In this paper,we design the algorithm to obtain the cospectral graph of two special graphs and the Non-Complete Laplacian borderenergetic Graph with given points.The graph coloring problem is an important research field of graph theory,and it has a strong application.The traditional coloring is using mathematical methods,With the gradual development of the computer,it is a big leap in the graph coloring problem that using computer to design algorithm to achieve the coloring.For example,traditional intelligent algorithms:genetic algorithms,particle swarm optimization algorithms,neural networks are all applied to graph coloring problems,but these intelligent algorithms generally can only solve single target problem.Although some new coloring algorithms have emerged in recent years,they can only achieve the small-scale graph coloring.With the development of society,the large-scale graph emerges in order to meet daily research needs.At this time,the existing algorithms can not meet the demand.In this paper,an algorithm is designed for this problem to obtained the Adjacent Vertex Distinguishing Total Coloring Of large-scale Graphs.After large number of experiments,the exact conclusions have been drawn,which laid the foundation for the development of graph theory.This paper includes three major parts,and the main content of this paper is as follows:(1)The first part introduces the basic concepts and related theories of graph theory and graph coloring,and the application of graph theory in the field of chemistry,such as the problem of fractional heterogeneity and graph energy.At the same time,summarizing the advantages and disadvantages of the existing research methods.(2)In the second part contains two types.In the first type,the algorithms of two kinds of special graphs(?-shape tree and star tree)are generated and the same spectrum.The specific idea is:the first step is to input the number of vertices and generate connected graphs according to the basic rules.Then according to the needs of this article to design rules and judgment functions and generate ?-shape tree and star tree,The second step is to design a spectrum algorithm,and to obtain the spectrum of ?-shape tree and star tree,and then compare them,finally obtain the structure of graph with the same spectrum.The second type gives the generation algorithm for all graphs under a fixed order and the Laplacian energy solution algorithm.The specific idea is to generate all graphs of a given order.Then design the Laplacian energy algorithm and calculate the energy of all graphs,finally find out the graph needed in this paper.The two kinds of algorithms provide basic research data for other disciplines,especially in the field of chemistry.(3)In the third part.Designed and implemented the generation and segmentation algorithm of large-scale graph.Adjacent Vertex Distinguishing Total Coloring algorithm,At the same time,the sub-algorithms such as the Normal Total Coloring algorithm and the coloring conflict adjustment algorithm are designed.The specific idea is to generate a random connected graph,Then divide the large graph into multiple subgraphs according to the partition rule,and then coloring,Finally,ensure that the colors of adjacent vertices,the colors of adjacent edges,the colors of adjacent vertices and edges,and the color sets of adjacent vertices are different.In this paper,a large number of experiments verify the correctness of the algorithm and obtain a certain number of results.