Spanning tree is an important field in both
mathematics and computer science. Mathematically, we define a spanning tree T of
an un-directed and connected graph G as a tree consisting of all the vertices
and all or some edges of the graph G.

**- Spanning tree is defined as a selection of some edges from G forming a tree such that every vertex is spanned by it.**

- This means that every vertex of graph G is present in the
spanning tree but there are no loops or cycles.

- Also, every bridge of the given
graph must be present in its spanning tree.

- We can even say that a maximal set
of the graph G’s edges containing no cycle or a minimal set of the graph G’s
vertices forms a spanning tree.

**- In the field of graph theory, it is common finding the MST or the minimum spanning tree for some weighted graph.**

- There are a
number of other optimization problems that require using the minimum spanning
trees and other types of spanning trees.

__The other types of spanning trees include the following:__
Ø Maximum
spanning tree

Ø An MST
spanning at least k number of vertices.

Ø An MST
having at the most k number of edges per vertex i.e., the degree constrained
spanning tree.

Ø Spanning
tree having the largest no. of leaves (this type of spanning tree bears a close
relation with the “smallest connected dominating set”).

Ø Spanning
tree with the fewest number of leaves (this spanning tree bears a close
relation with the “Hamiltonian path problem”).

Ø Minimum
diameter spanning tree.

Ø Minimum
dilation spanning tree.

- One characteristic property of the spanning trees
is that they do not have any cycles.

- This also means that if you add just an
edge to the tree, a cycle will be created.

**- We call this cycle as the fundamental cycle.**

- For each edge in the spanning there exists a distinct
fundamental cycle and therefore there arises a one – to – one correspondence
among the edges that are not present and the fundamental cycles.

- For a graph G
that is connected and has V vertices, there are V-1 edges in its spanning tree.

- Therefore, for a general graph composed of E edges, its spanning tree will have
E-V+1 number of fundamental cycles.

- For the cycle space of a given spanning tree
these fundamental cycles are used.

**- The notion of the fundamental cut set as well as of the fundamental cycle forms a dual.**

- If we delete even one edge from the spanning
tree, two disjoint sets will be formed of the vertices.

- The set of the edges
that if taken out from the graph G partitioning the vertices in to same
disjoint sets is defined as the fundamental cut set.

- For a given graph G there
are V-1 fundamental cut sets i.e., one corresponding to each spanning tree
edge.

- The fact that the edges of the cycles that do not appear in the spanning
tree but only in the cut sets of the edges can be used to establish the
relationship between the cycles and the cut sets.

## What is Spanning Forest?

- The sub-graph generalizing the
spanning tree concept is called the spanning forest.

**- A spanning forest can be defined as a sub-graph consisting in each of the connected component a spanning tree of the graph G or we can call it a maximal cycle free sub graph.**

- For counting the number of spanning trees for a complete graph the
formula used is known as the cayley’s formula.

## No comments:

Post a Comment