Coupon Accepted Successfully!


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.


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


Cayley's theorem

The complete graph Kn has nn–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 e1, an edge of G, such that weight of e1, ω(e1) is as small as possible and e1 is not a loop.

Step 2 :
If edges e1, e2, .... ei have been chosen, then choose an edge ei+1 not already chosen, such that

  1. induced subgraph G [(e1,.....ei+1)] is acyclic, and
  2. ω(ei+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 v1 of G.

Step 2 :
Choose an edge e1=v1v2 of G such that v2  v1 and e1 has smallest weight among the edges of G incident with v1.

Step 3 :
If edges e1, e2, ......., ei have been chosen involving end points v1, v2, .....vi + 1. Choose an edge vi+1 = vjvk with vj  {vi ..........vi + 1} and vk [v1, ....... vi + 1] such that 
ei + 1 has smallest weight among the edges of G with precisely one end in [v1, ......... vi + 1].

Step 4 :
Stop after n – 1 edges have been chosen. Otherwise go to step 3.

Test Your Skills Now!
Take a Quiz now
Reviewer Name