|
Graph theory is one of the most developing branches of
mathematics that is widely usedin computer science. It also
has applications in social sciences, linguistic, physicalsciences,
communication engineering and has an important role in switching
theory,artificial intelligence, formal languages, computer
graphics, operating systems, compilerwriting, information
organization, and retrieval. Graphs, especially trees and
binarytrees are widely used in the representation of data
structure.
A Spanning Tree is a tree of a connected graph G, which
touches all vertices of the graph. Enumeration of spanning
tree in undirected simple connected graphs is animportant
issue in many engineering and scientific problems. Many
problems in thisfield can be formulated in terms of graph.
Applying graph theory it is easy to solve mostof the problems
in the fields like networking and circuit analysis. In this
paper we have discussed one of the most important graph theoretical
problems, namely generation ofall spanning trees of a simple
connected graph. The spanning trees generated by this algorithm
are all distinct, i.e., there is no possibility of generation
duplicate spanning trees and also prohibited to generate
all the non-tree subgraphs.
A tree has n – 1 edges and we can generate all n –
1 edge combinations, filtering subsetsand allowing only
trees to pass. A preferable and efficient algorithm is one
thatgenerates only trees. So, there is no need for testing
combinations that generate circuits. Though the proposed
algorithm requires testing of circuits, the number is lesscompared
to the existing algorithm of Rakshit et al. (1981). Therefore,
this algorithm ismore efficient in terms of generation of
all spanning trees. Here, in this paper, we first calculate
the degree of each node and then identify the reference
vertex whose summation of degree of adjacent nodes is higher
in respect of the other vertices in thegraph. This method
will drastically reduce circuit testing for almost the same
number of edges combinations.
A typical instant is 12 vertices graph with 27 edges. The
number of combinations is ofthe order of 20 crores in Brute-force
method. Our algorithm reduces it to 5 lakhs; a 400:1reduction
in combination testing. However, we observe that only 20%
of the combinations are spanning trees. Obviously, our achievement
is in the morning.We proceed remembering that the morning
shows the day.
|
