# Articles

**1. Introduction**:

Many practical applications, particularly in communication networks and transportation networks can be formulated as optimization of minimum spanning tree problem [2]. The goal in optimization of minimum spanning tree is to find a solution that is appropriate for a particular application. When studying or many other problems, one often makes an assumption of general position: for minimum spanning trees, one can infinitesimally perturb the edge weights so that all are distinct, in this way picking out a unique solution. There are several algorithms exists for generation of Minimum Spanning Tree. Otakar Boruvka describe an algorithm for finding a Minimum Spanning Tree in a graph for which all the edge weights are distinct [2]. In the year 1957 Computer Scientist C. Prim's discovered another algorithm that finds a minimum spanning tree for a connected weighted graph [2]. This algorithm continuously increases the size of a tree starting with a single vertex until its span all the vertices. This algorithm was actually discovered in 1930 by mathematician Vojtech Jarnik. Joseph Kruskal describe a minimum spanning tree algorithm where total weight of all the edges in the tree is minimized [2]. Edsger Dijkstra in the year 1959 discovered a minimum spanning tree algorithm that solved the single source shortest path problem for a directed graph with non-negative edge weights [2]. Here, in this paper we describe and analyzed some minimum spanning tree algorithms with renovated idea. Here, in this paper we applied new algorithm for testing of circuits in the way of generation of Minimum Spanning Tree and obtained better result [1].

**2.**:

*Definitions*2.1 Spanning Subgraph:

Spanning subgraph is a subgraph of a graph G containing all the vertices of the graph G.

2.2 Tree:

A Tree is a subgraph of a graph G without any cycle or self loop.

2.3 Spanning Tree:

A Spanning Tree of a graph G is a spanning subgraph that is itself a tree.

2.4 . Minimum Spanning Tree:

A minimum Spanning Tree is a Spanning Tree of a weighted graph with minimum total edge weight.

**3.**:

*Cycle Tester*3.1 Cycle Property:

i) Let T be a minimum spanning tree of a weighted graph G

ii) Let e be an of g that is not in T and let C be the cycle formed by e with minimum spanning tree T.

iii) For every edge f of cycle C, weight(f) " weight(e).

3.2 Proof:

i) By contradiction

ii) If weight(f) > weight(e) we can get a spanning tree of smaller weight by replacing e with f.

3.3 Description of Cycle Testing Algorithm:

The Cycle Generator is an implementation of algorithm for finding a set of cycles of a finite undirected graph from its adjacency matrix.

The input parameters to the Cycle Testing method are:

i) A modified form of adjacency matrix, called A.

ii) The number of vertices of the graph, called n.

iii) The number of edges of the graph, called e

The output show the combination is cycle or not.

3.4 Algorithm for Testing of Cycles:

This algorithm ascertains us whether edges combinations of minimum spanning tree form a circuit or not [2].

**Step 1**: From the combination of edges and incidence matrix, obtain degree of each node contributed by the edges under consideration.

**Step 2**: Test whether at least two nodes of degree one? If not, go to step 6. Otherwise continue.

**Step 3**: Test whether at least three nodes of degree more than one? If not go to step 5.

**Step 4**: Delete pendant edges, if exists of n-1 edges and modify the degree of the nodes accordingly and go to step 2. Otherwise go to step 6.

**Step 5**: Edge combinations are tree.

**Step 6**: Stop.

**4.**:

*Algorithms*4.1.1 Boruvka's Algorithm:

Boruvka's Algorithm begins with examining each vertex and adding the edges of minimum weight from that vertex to another vertex in the graph, except those edges already added. This process will be continued until all the vertices will not include in the minimum spanning tree.

4.1.2 Pseudocode of Boruvkas Algorithm:

Ø
Begin
with a connected graph G containing edges of distinct weight, and an empty set
of edges T

Ø
While
the vertices of G connected by T are disjoint

§
Begin
with an empty set of edges E

§
For
each component

·
Begins
with an empty set of edges S

·
For
each vertex in the component

o
Add
the edge of minimum weight from the vertex in the component to another vertex
in a disjoint component to S

·
Add
the minimum weight edge in S to E

§
Add
the resulting set of edges E to T.

Ø
The
resulting set of edges T is the minimum spanning tree of G.

4.1.3 Algorithm of Boruvka:

1. Algorithm BoruvkaMST(G)

2. _{
}
*T* ← *V* // the vertices of graph G

3. while T has fewer than n-1 edges do

4. for each connected
component C in T do

5. let edge e be the minimum weight edge from C to another
component in T

6. if e is not already in C then

7. add edge e to T

8. return T

4.2.1 Prim-Jarnik
Algorithm:

Prim-Jarnik
algorithm finds a minimum spanning for a connected weighted graph. It finds a
subset of edges that form a tree and includes every vertex of the graph. This
algorithm continuously increases the size of the tree starting with a single
vertex until it spans all the vertices.

4.2.2 Pseudocode of Prim-Jarnik Algorithm:

Ø Pick an arbitrary vertex v_{a} and grow minimum spanning tree starting from v_{a}.

Ø Store each vertex v a label d(v) = the smallest weight of an edge connecting v to a
vertex in the cloud.

Ø At each step

§
We
add to the cloud the vertex u outside the cloud with the smallest distance
label

§
We
update the labels of the vertices adjacent to u.

Ø A primary queue stores the vertices
outside the cloud

§
Key:
distance

§
Element: vertex

Ø Locator based methods

§
Insert
(k, e) return a locator

§
Replace
key (l, k) changes the key of an item.

Ø Store three labels with each vertex

§
Distance

§
Parent
edge in minimum spanning tree

§
Locator
in priority queue.

4.2.3
Algorithm
of Prim-Jarnik:

1.
Algorithm
PrimJarnikMST(G)

2.
_{} *Q* ← new heap based
priority queue

3.
_{}*s* ← a vertex og G

4.
for
all *v* *G*, vertices()

5.
if
v = s

6.
setDistance(v, 0)

7.
else

8.
setDistance(v, ∞)

4.3.1
Kruskal
Algorithm:

Kruskals
Algorithm finds a minimum spanning tree for a connected weighted graph. It
finds a subset of edges that forms a tree that includes every vertex, where
total weight of all the edges in the tree is minimized. For non connected
graph, it finds a minimun spanning forest.

4.3.2 Pseudocode of Kruskal Algorithm:

Ø A priority queue stores the edges
outside the cloud

§
Key:
weight

§
Element:
edge

Ø At the end of the algorithm

§
We
are left with one cloud that encompasses the Minimum Spanning Tree

§
A
tree T is our Minimum Spanning Tree.

4.3.3 Algorithm of Kruskal:

1. Algorithm KruskalMST(G)

2.
for
each vertex v in G do

3. Define an elementary cloud C(v) ← {v}_{}

4.
Initialized a priority queue Q to contain all
edges in G, using the weight as keys.

5.
Define a tree *T* ← _{}

6.
while
T has fewer than n-1 edges do

7. (*u, v*) ← *Q*.removeMin()

8.
Let
C(v) be the Cloud containing v, and let C(u) be the
Cloud containing u.

9.
if *C*(*v*) ≠ *C*(*u*) then

10.
Add
edge (v, u) to T

11. Merge Cloud C(v) and Cloud C(u) into
one Cloud, that is, union of C(v) and C(v)

12. return tree T

*Source: Ubiquity Volume 9, Issue 7 (February 19, 2008 - February 25, 2008)*

COMMENTS