Research On Total Coloring And Related Algorithms Application For Two Kinds Of Regular Bipartite Graphs

Graph theory is the most important component of combinatorial mathematics and discrete mathematics.It is inextricably linked with other branches of mathematics,such as matrix theory,probability theory and topology,and it is the theoretical cornerstone of computer science,operations research and systems science.The study of graph theory is not only of great significance in theory,but also has a wide range of applications in practical life.It is often used to solve the problems of information science,computer science,network theory and other disciplines,as well as physics,chemistry,management and other disciplines.In the important research scope of graph theory,the research work of this thesis mainly focuses on the graph coloring and related algorithms.By combining computer search and mathematical proof,the equitable total coloring number of Fibonacci graphs and the total coloring number of Kn (?) del graphs are calculated,and the practical applications of coloring and related algorithms are studied.Main achievements are as follows:1、In the aspect of equitable total coloring,the problem of equitable total coloring of Fibonacci graphs are studied.We proved that the equitable total coloring number for Fibonacci graph FΔ,n is Δ+1 when Δ=3,n(mod 4)=0,Δ=4 and n≠12,14 andΔ=5 and n≠16,and the equitable total coloring number for Fibonacci graph FΔ,n isΔ+2 when Δ=3 and n(mod 8)=2,6,Δ=4 and n=12,14,and Δ=5 and n=16.2、In the aspect of total coloring,on the basis of computer search,the total coloring problem of Kn(?)del graph is studied by adding an edge.The method is that on the basis of 4-total coloring of W3,n,the total coloring of WΔ,n is studied by adding an edge with a new color,and then judging whether the coloring of the vertices at both ends of this edge meets the requirements of total coloring.It mainly proved that the total coloring number for Kn(?)del graph WΔ,n is Δ+1 when Δ≥3 and n(mod 8)=0,4,6.3、In the practical applications of coloring and its related algorithms,greedy,backtracking and branch bound techniques are applied to optimal path planning.The multi-objective optimal path for mobile robot navigation formed using Dijkstra shortest path algorithm based on greedy technology after the different needs of mobile robots are fully considered,the corresponding optimization objectives are formulated,various factors affecting the optimal path are quantified according to the objectives.In the process of solving the multi-objective optimal path planning problem,the Dijkstra shortest path algorithm is extended by using the subdivision graph,and the computational complexity of the extended Dijkstra shortest path algorithm is reduced by using backtracking and branch bound strategies,Thus it to provide a more accurate and flexible optimal route for the multi-objective based mobile robot navigation system.