Marks: 10 M

Year: Dec 2014

A minimum spanning tree can be defined as a spanning tree with weight less than or equal to the weight of every other spanning tree.

Let us find the minimum spanning tree for the given graph.

Step 1: Remove all loops

Here as no loops are present, we skip this step.

Step 2: Remove all Parallel edges (i.e edges having multiple values)

If so eliminate the edge with highest value and keep the one with least value intact. Here since such edges are not present, we skip this step.

Step 3: Sort the edges according to minimum weights.

Step 4: Construct minimum spanning tree.

Here we go from top to bottom of the above table by joining the given edges. An edge is discarded is it results in a cycle formation.

After this, all successive edges will form a cycle. So the above graph is minimum spanning tree. And the cost is 105.

(Note.: No. of edges in MST =No. of nodes n graph-1)