The Research Of Algorithms And Application Of Felicitous Labelling Of Graphs

Many problems can be abstracted as graph theory problems in reality.The things or phenomena are represented as points,and the connections between things or phenomena is abstracted as edges.The topological structure of relations between things is represented by a graph,and then it can be changed as a graph problem.The origin of graph theory can be traced back to the EULER's study of the seven bridges of Gnisburg in 1736.Due to the rapid development of electronic computers in modern times,graph theory has also developed rapidly,and has formed an important branch of mathematics.As one of the important problems in graph theory,the graph labelling problem belongs to a branch of graph theory and is also one of the topics of combinatorial mathematics research.It was originated from the beautiful conjecture.Although the conjecture of the graceful tree has not been completely proved or denied so far,it also has laid the foundation for the subsequent development of graph labelling.Graph labelling refers to the distribution of integers on vertices or edges or both under certain conditions between the vertice and edges.Since the graph labelling was proposed,many researchers have studied it and expanded the content of it,and it also has obtained a lot of research results currently.At present,the graph labelling are divided into four major categories: graceful labelling,harmonious labelling,magic labelling,and other labelling types.The main difference between these four types of labelling is the relationships between vertice and edges.And the felicitous labelling is one type of the harmonious labelling.At present,the main research method for the graph labelling problem is that using traditional combinational methods to prove it,and this type of method usually can prove the labelling of a class of graphs.However,the diversity of graphs makes most of the graphs have no rules to follow.Therefore,it is difficult to verify the labelling of random graphs.Through the study of related literature,it is found that the publicly published literature on felicitous labelling is also proved by using the traditional methods,such as circle graphs,complete graphs,trees,and several types of union graphs and so on.Therefore,the computer algorithm of the graph labelling has certain research value.On the one hand,it is very difficult to use traditional methods to obtain the labelling of random graphs.Hence it is a very effective measure to label random graphs by computer algorithm;on the other hand,the number of graphs within finite vertice is very large and it is difficult to obtain the labelling of all graphs by hands,and computer algorithms can solve this problem.By analyzing the constraint conditions of the felicitous labelling and its labelling features,this paper designs the algorithms for felicitous labelling of the graph,and also studies its practical application.The main research work of this paper is as follows:(1)Introducing the research status of graph labelling,related concepts and the two main labelling algorithm ideas of the graph lablelling,explaining the two labelling ideas,and also analyzing the advantages and disadvantages of the algorithm.(2)Two algorithms are designed and completed: the algorithm of constructing felicitous graphs based on felicitous space and the felicitous labelling verification algorithm of random graphs.Firstly,the correctness of the algorithm is verified by using the known theorem.Then the distribution of felicitous graphs of all graphs within 9 points and the distribution of felicitous graphs of unicyclic graphs within 18 points are obtained by combining these two algorithms.Through the experimental results of the algorithm,the relevant conclusions are obtained.(3)Set-ordered felicitous labeling algorithms for tree and complete bipartite graphs is designed and implemented.The set-order felicitous labelling of all the tree within 18 points was achieved.According to the test results,the conclusion of the set-order felicitous labelling of the trees was obtained.In addition,the law of the set-ordered felicitous labelling of the complete bipartite graph is summarized.(4)The concept of the graph labelling was introduced into the graphical password by using the easy-to-memorize feature of graphs plus numbers,a graphical password based on the graph labelling was constructed,and this type of graphical password is also evaluated.