• REVIEW OF MINIMUM SPANNING TREE IN AN UNDIRECTED GRAPH

S. N. BANASODE, Y. M. UMATHAR*

Abstract


A Minimum spanning tree of a weighted graph is a tree having all vertices of a given graph with weight less than or equal to the weight of all such possible spanning trees from the given graph. In this paper we propose new method and corresponding algorithm to construct a minimum spanning tree of a weighted graph. This new approach is based on Edge Elimination Method. In this method we eliminate an edge with highest weight in each of the smallest cycle of the weighted graph until no cycle is remained in the graph with care that graph is not disconnected at any stage. Once such a graph (tree) is obtained it is the required minimum spanning tree in an undirected weighted graph.


Keywords


Graphs, Weighted graph, Tree, minimum spanning tree

Full Text:

PDF


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 Unported License.
© 2010-2018 International Journal of Mathematical Archive (IJMA)
Copyright Agreement & Authorship Responsibility
Web Counter