I. $a-b$
II. $d-f$
III. $b-f$
IV. $d-c$
V. $d-e$
Choose the correct answer from the options given below:
Using Kruskal's algorithm, edges are selected in increasing order of weight.
From the graph:
$a-b = 1$
$d-f = 1$
$b-f = 2$
$d-c = 2$
$d-e = 3$
So, the valid order must follow:
Weight $1$ edges first:
$I, II$ in any order
Then weight $2$ edges:
$III, IV$ in any order
Then weight $3$ edge:
$V$
Now check option (c):
II, I, III, V, IV
Here, edge $V = d-e$ has weight $3$, but edge $IV = d-c$ has weight $2$.
So, selecting $V$ before $IV$ violates Kruskal's increasing weight rule.
Therefore, this order cannot be used.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.