| Graph theory originated from the classic problem of the Seven Bridges of Konigsberg.It is a discipline that blends information technology with mathematics.Graph theory transforms many complex abstract problems in the real world into a graphical representation.Graphs consist of vertexs and edges,where vertexs represent objects and edges represent their relationships.By studying graphs,various attributes and relationships can be discovered,such as connectivity,maximum flow,matching,and more.Ultimately,these concepts can be applied to multiple fields such as shortest paths,connected components,signal communication,complex networks,and more.Graph labeling is an important area of research in graph theory,closely related to fields such as graph coloring and optimization.The origin of this field can be traced back to Rosa’s "Conjecture of Graceful Trees," which provided a basis for the later development of graph labeling theory.Since then,many scholars have proposed new labeling concepts based on graceful trees,such as magic labeling and happy labeling,discovering many labeling theorems.However,most of these theorems are aimed at special types of graphs,such as cycle graphs and star graphs,and traditional mathematical research methods are used,making it difficult to conduct in-depth studies on random graphs.Graph coloring is another important branch of graph theory,which studies the problem of coloring the vertexs of a graph.The earliest related conjecture can be traced back to 1852,when the South African mathematician Francis Guthrie proposed the famous Four Color Conjecture.The proof of this conjecture took more than a century and was finally demonstrated by mathematicians Kenneth Appel and Wolfgang Haken in 1976.Subsequently,as more and more scholars became involved in researching graph coloring,various classifications were introduced to address different coloring problems,such as magic coloring,total coloring,distinguishing coloring,and reducible coloring.However,there is still a relative lack of algorithmic research to solve coloring problems.Therefore,using computers to solve labeling and coloring problems in graph theory has become a new direction of research.Based on the previous research results of scholars,this article conducts research on problems such as adjacent vertex reducible total labeling,vertex magic edge coloring,and vertex clustering magic total coloring in random graphs.To solve these problems,this article proposes corresponding solutions and designs related labeling and coloring algorithms.Arrange the main research work as follows:(1)This paper introduces the relevant concepts and research background of graph labeling and coloring,and introduces the basic knowledge related to adjacent vertex reducible total labeling,vertex magic edge coloring,and vertex clustering magic total coloring.(2)A new algorithm for adjacent vertex reducible total labeling is designed and implemented.This paper introduces the concept of adjacent vertex reducible total labeling,which is developed based on the adjacent vertex reducible edge labeling.Using a cyclic iterative optimization method,the algorithm labels random graphs with up to ten vertices and verifies whether these graphs have AVRTL.Finally,through analysis and summarization of the experimental results,labeling theorems for some special graphs and connected graphs are obtained..(3)Designed and implemented algorithms for vertex magic edge coloring and vertex clustering magic total coloring,and applied these algorithms to a dataset of graphs.By processing these graphs,the coloring patterns of random graphs with up to ten vertices and some special graphs were obtained,and their theorems were proven..(4)The vertex clustering magic total coloring algorithm is based on vertex classification magic total coloring,vertex magic total coloring,and clustering coefficient in complex networks.When applied to urban bus networks,it can effectively improve the allocation of urban transportation resources and commuting efficiency. |
PDF Full Text Request