The Research Of Algorithm For Smarandachely Vertex Distinguishing Coloring Of Random Graphs

Many practical problems can be created by drawing graph of model and solve it byGraph Theory, there are many NP-hard problem in graph theory, make this area become atesting ground for a popular heuristic algorithm. In recent years, graph algorithms monographendless. Graph coloring problem (Graph Coloring Problem, abbreviated GCP) can be seen asNP-hard problem in graph theory in a family group. Classic graph coloring problem refers tovertex coloring problem in a narrow point, in1889the author Tait mentioned edge coloringconcept, in which he pointed out the problem with the four-color theorem and3-connectedplanar cubic graph are equivalent problem and gives that the number of upper bound is relatedto the of G, after that, Vizing presented and proved a generalized upper bound, that is, forany simple graph, edge coloring number does not exceed the maximum degree plus1. Manyresearchers have designed many domestic exact or heuristic algorithm based on this theory,and committed to ensure improved efficiency of the algorithm on the premise of this sector.Stained with multiple constraints in the1960s-total coloring problem, respectively, byM. Behzad and Vizing independently raised. As the technology of computer hardware andsoftware continues to update, the design of total coloring algorithm gradually become feasibleand will soon be taken seriously. Based on the idea of total coloring problem, part of theresearch will tends to add constraints in the existing problems. In1993, AC Burris and RHSchelp proposed the concept of vertex distinguishing edge coloring, and gives an guess ofupper bound. In2002, based on the vertex of distinguishing edge coloring, Zhang Zhongfuproposed adjacent vertex distinguishing edge coloring, after that, Zhang continue to increasebinding conditions,and proposed adjacent vertex distinguishing total coloring concept in2004, while give the color number of adjacent vertex distinguishing of some special graph, to2008, and made a vertex of distinguishing total coloring concept, summarizes the results of alarge number of experiments and propose the coloring upper of this issue, after that furtherraised Smarandachely coloring series, including Smarandachely adjacent vertexdistinguishing edge coloring, Smarandachely adjacent vertex distinguishing total coloring,Smarandachely vertex distinguishing edge coloring and Smarandachely point distinguishingtotal coloring concepts and related upper bound guess. In this paper, for any simple connectedgraph,designed four algorithms connected Smarandachely, and the algorithm is analyzed andtested, through in-depth analysis of the test results, obtained some interesting conclusions.The main work is as follows:(1) The main understanding of graph coloring especially relevant theoretical backgroundand domestic dynamics of Smarandachely coloring. Learning a lot of literature about thegraph coloring, especially study a large number of algorithms and Heuristic Algorithm that can solve the graph coloring problem, such as New Graph Coloring Problem GeneticAlgorithm、 Neural Networks Model of Graph Uniform Coloring Problem、Vertex-distinguishing Edge-coloring by A.C.Burris and so on. Comparison and analysis of thecharacteristics of these algorithms in the literature, its essence to its dregs, andimplementation of the proposed algorithm provides a solid theoretical foundation.(2) On the basis of the above study, for random graphs designed four heuristicalgorithms, solved four kinds Smarandachely coloring problems; Analysis the algorithm fromthree aspects of correctness, convergence and time complexity; Designed test program, suchas less than8points all graphs and special graphs testing, and analysis the test results.Through the above work and got some interesting results, not only provide a useful referencefor the research of graph coloring guess, but also provide a research tools for the graphcoloring applied to solve practical problems.