Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



Given the graph below one of the following edges cannot be added in that order to find a minimum spanning tree algorithm.


I. $a-b$
II. $d-f$
III. $b-f$
IV. $d-c$
V. $d-e$

Choose the correct answer from the options given below:






Solution

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.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...