# Spanning Trees And Connect Or Problems

Let G be a graph. A subgraph H of G is called a spanning subgraph of G if vertex set of H is same as the vertex set of G. Similarly, a spanning tree of a graph G is a spanning subgraph of G, that is a tree.

Theorem.

A graph G is connected if it has a spanning tree.

# Cayley's theorem

The complete graph K_{n} has n^{nâ€“2} different spanning trees.

# Kruskalâ€™s Algorithm

In this algorithm, choose an edge of G which has smallest weight among the edges of G which are not loops. This algorithm gives an acyclic subgraph T of G and theorem given below proves that T is a minimal spanning tree of G.

Following steps are required.

**Step 1 :** Choose e_{1}, an edge of G, such that weight of e_{1}, Ï‰(e_{1}) is as small as possible and e_{1} is not a loop.

**
Step 2 :** If edges e

_{1}, e

_{2}, .... e

_{i}have been chosen, then choose an edge e

_{i+1}not already chosen, such that

- induced subgraph G [(e
_{1},.....e_{i+1})] is acyclic, and - Ï‰(e
_{i+1}) is as small as possible.

**Step 3 :** If G has n vertices, stop after n-1 edges have been chosen. Otherwise repeat step 2.

Greedy Algorithms :

Greedy algorithms are essentially algorithms that proceed by selecting the choice that looks best at the moment.

Primâ€™s Algorithm :

Another algorithm used for finding a minimal spanning tree is Primâ€™s algorithm. It chooses a vertex first and chooses and edge with smallest weight incident on that vertex.

The algorithm involves following steps.

**Step 1 :** Choose any vertex v_{1} of G.

**
Step 2 :** Choose an edge e

_{1}=v

_{1}v

_{2}of G such that v

_{2}â‰ v

_{1}and e

_{1}

_{ }has smallest weight among the edges of G incident with v

_{1}.

**
Step 3 :** If edges e

_{1}, e

_{2}, ......., e

_{i}have been chosen involving end points v

_{1}, v

_{2}, .....v

_{i + 1}. Choose an edge v

_{i+1}

_{ }= v

_{j}v

_{k}with v

_{j}

_{ }âˆˆ {v

_{i}..........v

_{i + 1}} and v

_{k}

_{ }âˆ‰[v

_{1}, ....... v

_{i + 1}] such that

e

_{i + 1}

_{ }has smallest weight among the edges of G with precisely one end in [v

_{1}, ......... v

_{i + 1}].

**
Step 4 :** Stop after n â€“ 1 edges have been chosen. Otherwise go to step 3.