Kruskal Method

Question  1:  Find a minimal spanning tree for the connected weighted graph using
(i) Kruskal's method

Ans :

Step - 1 : Choose the edge= a-f with minimum weight value = 3

Step - 2 : Choose the edge = b-c out of the not chosen edges with minimum weight value (= 4) among the remaining edges and not forming any cycle.

Step - 3 & 4 : Choose the edge = ab or ae out of the not chosen edges with minimum weight value ( = 5) among the remaining edges and not forming any cycle. Let us select both the edges as the number selected edges = 4 which is less than the n-1 = 5


Step - 5 : Choose the edge = ed out of the not chosen edges with weight value (= 7) among the remaining edges and not forming any cycle. The edge bf with minimum value among the remaining value can not be selected as it will form a cycle b-f-a.


Now all the vertices are traversed and this completes the formation of Minimal Spanning Tree.
Total Wt = w(bc+ab+af=ae+ed) = 5+4+3+5+7 = 24