Research On Algorithm Of Graphs Graceful Labeling And Its Application In PDF417 Codes Anti-counterfeiting

Graph theory is the basic science in the computer field and an important branch of combinatorial mathematics.All of the studies in graph theory take graph as the study object and operate graph.Such as graph coloring,graph labeling.Nowadays,the basic algorithms in machine learning and neural network in artificial intelligence are based on graph theory.The advent of the computer promotes the development of graph theory basic science greatly.As an important research area in graph theory,graph labeling has a good theory background and great application value.Many combinatorial optimization problems can be abstracted as graph labeling in the real world,we can analysis graph labeling using theory to solve the related problems.To label a graph is to find a mapping,essentially.Such as the graceful labeling,for a graph that |(1()| = ,|()| = ,if there is a injective 1): (1()→ {0,1,2,…,},such that the edge labels set equals {1)()| ∈ ()} ={1,2,…,} and edge labels satisfies 1)()= |1)()-1)()|,then is called graceful graph,and 1)is a graceful labeling of graph .Graceful labeling is a graph labeling proposed early.And it originates from Rosa’s “graceful tree conjecture”,which points out that all of the trees are graceful.Because of the uncertainty in a graph structure,the conjecture has not been proven yet.But the proposal of graceful tree conjecture set a foundation for further study.Lots of special graceful graphs are proven and some good conclusions have been obtained.However,the process of the proof is a traditional combinatorial construction method,which can prove a certain structure,regular graphs.It is a NP-hard problem to prove the gracefulness of random and general graphs.Traditional combinatorial construction method aims at special graphs and it has limitations.The regularity of graceful labeling is difficult to find generally.While computer algorithms can solve the random graph gracefulness.Unfortunately,this kind of literature is rare and there is no universal algorithm to solve it.In view of the problem,this paper designs and proposes algorithms of graceful labeling and odd-graceful labeling of graphs.Finally,combined the graph labeling and PDF417 code,this can be applied to anti-counterfeiting of products.The main research works are as follows:(1)Introduce the basic concepts,research status of graph labeling and the existing conclusions of graph labeling in graph theory.(2)The algorithm of generating all non-isomorphic graphs in finite points and the coding principle of g6 files are introduced.(3)Two new graceful labeling algorithms for graphs are proposed,which are “algorithms of searching graceful graphs based on graceful space” and “algorithms of judging graceful graphs based on adjacency matrix”.Both algorithms can solve the gracefulness of random graphs in finite points.By using algorithms,all graphs in 9 points,unicyclic graphs in 18 points and bicyclic graphs in 17 points are verified its gracefulness.And the relevant statistical data and many great conclusions are obtained.(4)The odd-graceful labeling of graph is to limit the edge labels set to an odd number range.This paper also implements odd-graceful labeling algorithm aims at random graphs.By using this algorithm,all graphs in 9 points are verified its odd-gracefulness.And some relevant conclusions and theorems are obtained.Accroding to the data analysis,within this range,if a graph does not contain any odd cycles,this graph is odd graceful.Therefore,a method for judging whether a graph contains odd cycles is also given in this paper.(5)The code principle of PDF417 is introduced.Combining the labeling algorithm and PDF417 code,this paper also introduces the idea of using graceful labeling algorithm to anticounterfeiting products.