A new verification algorithm for minmum spanning tree based on reduction and merge technology

The minimum spanning tree(MST) of a graph defines the cheapest subset of edges that keeps the graph in one connected component which is a classic problem in operational research(OR) with important applications in a number of applications, both as a stand-alone problem and as a subproblem in a more complex. The problem considered here is that of determining whether a given spanning tree of a graph is a minimum spanning tree. It is of great importance while the graph subjects to some discrete changes, such as additions or deletions of edges or vertexes and the cost variation of edges. Unlike the algorithms presented by Tarjan, Komloacutes and other people, the verification algorithm presented here is a liner time and fully employs the properties of the problem to remove the pendant vertexes (vertexes of degree 1) and specify the edges must be in MST. Then by vertexes merge technology creates a reduced graph and spanning tree. The problem of verifying the new spanning tree is a minimum spanning tree of the new graph is equal to the original problem. The algorithm is simple and practical. Finally in order to demonstrate the principle and the process of the algorithm an example is also presented.