What is Spanning Tree?
https://www.computersprofessor.com/2016/12/what-is-spanning-tree.html
Spanning tree:
A spanning tree for an
undirected graph G is a graph consisting of all the nodes of ‘G’ together with
enough edges from G such that
1.There is a path b/w each pair of nodes in ‘t’.
2. There
are no simple cycles in tree.
3. If a
graph G=(V, E) contains n nodes then the spanning tree for the graph has (n –
1) edges.
The number of edges that
must be removed from a graph to form a spanning tree is m- n+1
m edges
n edges
m-n+1
=6-5+1
=2
Here 2 edges are removed.
1.
H is a tree.
2. H contains all the vertices of G spanning trees are important because of
there following reasons.
a.
Spanning tree is very important on designing efficient rooting algorithm.
b.
Spanning tree have wide applications in many such as network designing.
