Research Of Spanning Tree On Uncertain Graph

Graph theory that is a branch of mathematics plays an important role in computer science. With the time for the era of big data, the scale of graph data will be more and more, so the efficiency of graph algorithms is very important to solve graph problems.We may encounter many unexpected situations in practical problems, for example,machine fault and instability of signal transmission, in the end, the actual data will be uncertain, so the uncertain graph has become a very popular field of study. In this paper,we research the spanning tree algorithms on uncertain graph, we separate the content into the following four sections:(1) Because the edge on uncertain graph exists uncertainty, the definition of classic minimum spanning tree can not be apply to uncertain graph, so we put forward the concept of optimal spanning tree. it’s mainly to add an optimized definition of the probability based on the definition of the minimum spanning tree, then, we use the greedy idea and design the optimal spanning tree algorithm on uncertain graph.(2) In order to find the top-k optimal MST on uncertain graph, we designed the top-k minimum spanning tree algorithm and proposed two optimized algorithms based on disjoint-set and heuristic search respectively. When the K value is small, the algorithm based on heuristic search is better than the algorithm based on disjoint-set. At last,we analyze the reliability of the minimum spanning tree on uncertain graph.(3) We analyze the reliability of the minimum spanning tree on uncertain graph. The reliability is defined as the sum of existence probability of implicated graphs that contain the minimum spanning tree, after that, we classify all implicated graph based on edge partition, the implicated graphs in the same class have the same MST. At last, we get the reliability of the uncertain graph through calculating the existence probability of implicated graphs that have the same class.(4) In uncertain graph, we put forward the definition of the optimal arborescence, and design an optimal arborescence algorithm. At last, we combine with the idea of the top-k minimum spanning tree algorithm and the property of the optimal arborescence and design top-k minimum arborescence query algorithm.Finally, we carry out experiments to verify our researches in spanning tree on uncertain graph, the experiment results show that the efficiency of designed algorithm agrees with theoretical analysis, and get exactly the solution of the problems.