 Open Access
 Total Downloads : 674
 Authors : Aquila Khanam, Dr. Minita Mathew
 Paper ID : IJERTV1IS10238
 Volume & Issue : Volume 01, Issue 10 (December 2012)
 Published (First Online): 28122012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Minimum Spanning Tree Of Undirected Graphs
Aquila Khanam,
PESIT, BSC
ABSTRACT
This paper presents an approach to finding the minimum spanning tree for simple undirected graphs and undirected multigraphs. The algorithm involves choosing the minimum edge that connects each disjoint component of the graph, until a single component is formed. This single component is the minimum spanning tree of the given graph. The approach we take is a slight modification to Sollins algorithm.

Introduction
The minimum spanning tree of an undirected graph is an acyclic graph (tree) of minimum weight that connects all the vertices of the graph.
One may use minimum spanning trees or MSTs to set up communication links between cities with minimum cost or minimum length. Similarly, MSTs may be used to set up communication networks, telephone line networks, computer networks or piping in a flow network. Due to the various uses of MSTs in everyday problems, efficient algorithms that can solve graphs with a large number of vertices are required. Traditionally, Prim's and Kruskal's algorithms have been used to create minimum spanning trees, and do so efficiently. Their predecessor is Borvka's (or Sollin's) algorithm, which is where the MST algorithm in this paper is derived from.
Prims algorithm involves dividing the vertices of a graph into two sets – visited and unvisited, with the initial visited vertex being arbitrarily chosen as the starting vertex. On each iteration, the minimum edge connecting an unvisited vertex to a visited vertex is added to the tree. The final tree T formed, that spans the vertices of the graph is a minimum spanning tree.
Dr. Minita Mathew
Associate Professor, PESIT BSC
In Kruskals algorithm, each edge of the graph G is examined in ascending order of weight, and if the chosen edge does not form a cycle in the tree T, it is added to T. The process continues until n1 edges have been added.
In this MST algorithm, each disjoint component of the spanning tree is connected by adding the minimum edge between any two components to the tree. The algorithm starts with taking all the vertices of the graph as disjoint components and examines each component to determine the minimum edge incident on that component. Effectively, this algorithm continues until only one final component remains, and in the worst case, each iteration halves the number of disjoint components remaining. This selection process also applies to multigraphs, as only one minimum edge will be chosen between two components that have multiple edges connecting them. The final single component is the required minimum spanning tree.
In this paper, we give a proof as well as a pseudo code for our algorithm and illustrate it with an example.

Terminology
Graph: A graph is an ordered pair G = (V,E), where V is the vertex set whose elements are the vertices, or nodes of the graph. This set is often denoted V(G) or just V. E is the edge set whose elements are the edges, or connections between vertices, of the graph. This set is often denoted as E(G) or just E. If the graph is undirected, individual edges are unordered pairs {u,v}, where u and v are vertices in V. If the graph is directed, edges are ordered pairs (u,v).
Example of a Graph
[2]Minimum Spanning Tree: A spanning tree with the smallest possible weight among all spanning trees for a given graph.[4]
[5] 
Algorithm
Tree: A tree is a type of connected graph. A directed graph is a tree if it is connected, has no cycles and all vertices have at most one parent. An undirected graph is considered a tree if it is connected, has vertices one more than the number of edges. Such a graph is acyclic
Example of a tree[3]
Spanning Tree: For a graph G = (V,E), a spanning tree T
= (V,E) is a tree that contains all the vertices of G, and whose set of edges is a subset of the edges of G (E E).
We consider all the vertices of the graph as disjoint components. First to each vertex we identify the edge with minimum weight on it. Ties are broken arbitrarily. These selected edges become the required edges of our minimum spanning tree. In the next stage we are left with several connected components. We then select the edge with the minimum weight between two components. The process is continued till we get a connected component. This selection process also applies to multigraphs, as only one minimum edge will be chosen between two components. We claim the tree S thus obtained is a minimal spanning tree.
3.1. Proof
S is a spanning graph because the algorithm ensures that all the vertices of G are present. Since the algorithm stops when there is one connected component, the graph G is also connected. Further since we either do not add edges whose vertices are already in S, or only add edges from the vertices of one component to the vertices of the other component, cycles are not formed. Hence S is a spanning tree. We now show that the spanning tree formed by this algorithm and the minimum spanning tree (MST) T obtained by any other standard algorithm like Prims or Kruskals have the same weight.
Weighted Trees: A weighted tree associates a label
Let e1 , e2 ,en be the edges of S as added by the
(weight) with every edge in the graph. We denote the
algorithm. Suppose the edge ek
u, v differs from that
weight of an edge e as wt(e). The weight of a tree wt(T) is the sum of the weights of the edges.
in T. Let P be the path between u and v in T, and let e be the edge by which u is connected to T. Consider T ek . This will create a cycle C in T. Since the algorithm has
picked up ek , it means that ek
is the edge with the least
the least edge between each component must be added to
weight incident on either u or v. Without loss of generality
the tree. If the number of components is 1, go to step
while (components>1)
let us assume ek is the edge of least weight incident on u. {
Then wt(e) wt( ek ). Therefore, delete e from the tree
min = 99; for(i=0;i<n;i++)
and replace it by ek . Continuing this process we can {
replace every edge that is present in T and not present in S by an edge present in S which is of less than equal to weight. Hence wt(S) wt(T). Since T is a minimum spanning tree. Then wt(S) = wt(T), as T is a minimum
spanning tree and the weight of S cannot be less than the weight of T. Therefore, the weight of S must be equal to the weight of T. Hence, S is a minimum spanning tree.
The same proof holds for a multigraph, as only the least edge for a pair of components is picked up by the algorithm during each iteration. A tie is broken arbitrarily, as it does not affect the weight of the minimum spanning tree.

Pseudo Code
for(j=0;j<n;j++)
(visited[j]==0 && min>G[i][j])
min = G[i][j]; u = i;
v = j;
if (visited[i] == 1)
{
{
if
{
}
The algorithm is as follows: }
1
Start }
}

For a component u in the graph add the minimum edge e incident on it to it's minimum spanning tree, S.

If the number of components in the graph is greater than 1,
connect[v][u] = 1; buildVisited(u);
}
repeat step 1. Otherwise, if there is only one component, it is required minimum spanning tree, S, of the graph G.

End
Pseudo Code
main()
}
7 End
Systemout.println(weight);

Start

Input the number of vertices

Initialize variables
int i,j=0,min,u=0,v=0, components=n;

Find the edges incident on each vertex that are of minimum weight
for(i=0;i<n;i++)
findMin(G,i);

Build an array of all the vertices connected to vertex 1. buildVisited(0);

If the number of components is greater than 1, it means that the minimum spanning tree has not been formed, and
findMin()

Start

Initialize the variables int j,min=99,pos=0;

Find the minimum edge incident on each vertex and add those edges to the tree
for(j=0;j<n;j++)
{
if(min>X[i][j])
{
min = X[i][j]; pos = j;
}

End
}
connect[i][pos] = 1;
}
buildVisited(u)

Start

Declare local variables int i;

Set the source vertex u as visited visited[u] = 1

For each unvisited vertex connected to the source vertex, connect the least edge, and recursively find the least edge connected to this vertex as the source
for(i=0;i<n;i++)
{

Conclusion
0)
}


End
if (connect[i][u] == 1 && visited[i] ==
{
components–; System.out.println(i+" – "+u); weight += G[i][u]; buildVisited(i);
}
The Minimum spanning tree algorithm has been designed and tested to have a complexity of O(n2), which is comparable to Prims algorithm in its adjacency matrix implementation. The applications of MSTs vary over numerous fields; from circuit designto minimize the number of wires used to connect pins; to biotechreducing data storage in sequencing amino acids in a protein; to image registration with Renyi entropy or to connect islands with a minimum number of bridges or group of locations with a minimum number of roads.

References

http://en.wikibooks.org/wiki/Graph_Theory/Definitions
5. Illustration

(http://mjwilcox.net/index/wp content/uploads/2011/04/undirected_graph_example1.gif)

(http://en.wikipedia.org/wiki/Tree_(graph_theory))

(parallel.ru/info/reference/hpccgloss.html)