Use Kruskals algorithm to find a minimal spanning tree You d

Use Kruskal’s algorithm to find a minimal spanning tree. You do not need to draw the tree, but do list the edges (as an ordered pair) in the order in which they are chosen

Thanks

Solution

To find the minimal spanning tree, we have to first sort all the edges in non decreasing order of weight and also the number of edges in minimal spanning tree will be (9-1) = 8 (Because the original graph has 9 vertices):

Now we will pick up all the edges one by one and see if this forms a cycle with the spanning tree formed so far.If cycle is not formed then we include that edge otherwise discard.

1) Pick I-H .No cycle is formed .include this edge

2)Pick H-G. We get I-H\\G..No cycle is formed.Include this edge

3)Pick F-E. We get I-H\\G F/E. No cycle is formed. Include this edge

4) Pick I-G.Since I-H\\G forms a cycle with this edge so we discard it

5) Pick G-A.We get I-H\\G\\A F/A. No cycle is formed so include this edge.

6) Pick D-C.We get I-H\\G\\A F/A D|C. No cycle is formed so include this edge

7) Pick B-C.We get I-H\\G\\A F/A B-C|D. No cysle is formed so include this edge

8) Pick A-B. We get I-H\\G\\A/B-C|D F/E.No cycle is formed so include this edge

9) Pick H-E.We get I-H-E/F H\\G\\A/B-C|D No cycle is formed so include this edge

And now we have got 8 edges so we will stop here.The ordered pair of these 8 edges are given by:

(I,H) (H,G) (F,E) (G,A) (D,C) (B,C) (A,B) (H,E)