Consider the following graph: Which one of the following cannot be the…
2025
Consider the following graph:
Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskals algorithm ?
- A.
(a-b), (d-f), (b-f), (d-c), (d-e)
- B.
(a-b), (d-f), (d-c), (b-f), (d-e)
- C.
(d-f), (a-b), (d-c), (b-f), (d-e)
- D.
(d-f), (a-b), (b-f), (d-e), (d-c)
Attempted by 59 students.
Show answer & explanation
Correct answer: D
Kruskal's algorithm constructs a Minimum Spanning Tree (MST) by sorting all edges in non-decreasing order of their weights and adding them one by one, provided they do not form a cycle with the edges already selected. The critical rule is that lighter edges must always be considered before heavier ones.
In Option D,
(d-f), (a-b), (b-f), (d-e), (d-c)
(d-f)[wt: 1],(a-b)[wt: 1] -> Valid order for weight 1.(b-f)[wt: 2] -> Valid weight 2 edge.(d-e)[wt: 3] -> Violation! Kruskal's algorithm is processing a weight 3 edge(d-e)before processing the remaining weight 2 edge(d-c).Since
(d-c)does not form a cycle at that stage, it must be considered before any weight 3 edge.Result: Invalid sequence.