Approximate Algorithm For The Maximum Weakly Proper Tree In Edge-colored Graphs

Graph Coloring Problem is one of the most widely studied problems in graph theory,and it is also an important and basic problem.Many problems in real life can be regarded as graph colored problem.The edge colored of a graph is that each edge of a graph is given a color.The proper edge colored of a graph means that the adjacent edges are colored differently after each edge is colored.In this paper,we study the problem of the maximum weakly proper tree in edge colored graphs: given a vertex r,we find a weakly proper tree T,which has the maximum number of vertices with r as the root node.The tree T with fixed root r is said to be weakly proper if every path in T,from the root r to any leaf,is a proper one,but the adjacent edges of the tree vertices can have the same color.This problem has been proved to be NP hard.In this paper,a polynomial time approximation algorithm for solving this problem is designed and implemented by computer programming.In the first chapter,this paper introduces the basic concepts of combinatorial optimization problem and edge colored problem.The approximate algorithm and computational complexity are also introduced.Then,we summarize the maximum proper tree problem and the maximum weakly proper tree problem in edge colored graphs at home and abroad.Finally,the structure of the full text is described.In chapter two,we focus on the problem of the maximum weakly proper tree when the color number is c = 2 and an approximate algorithm is designed based on greedy idea.The worst-case ratio of the approximate algorithm is theoretically analyzed,and the worst-case ratio of the algorithm is obtained to be 2.Finally,a tight example of the approximation algorithm and its analysis are proposed.In the third chapter,we use Python programming language to implement the algorithm,and ten examples are randomly generated for each pair of s = 10,n = 200;s = 20,n = 400;s = 20,n = 600.Each pair of S,n randomly generates 10 examples,and the numerical experiments of the greedy algorithm GA for the maximum weakly proper tree in edge colored graphs are implemented by comparing 10 examples.The fourth chapter briefly summarizes the main content of this paper.