Consider the graph given below.

Use Kruskal's algorithm to find a minimal spanning tree for the graph. The list of the edges of the tree in the order in which they are chosen is

(3)

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

(1), (2), (3), (4)

No worries! We‘ve got your back. Try BYJU‘S free classes today!

(1) (2)

No worries! We‘ve got your back. Try BYJU‘S free classes today!

(1), (2), (3)

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

The correct option is A (3)
Step1: In Kruskal's algorithm, edges must be included in the increasing order of their weights without forming cycle.

Increasing order of weights are:

$A D = G C \leq A G = G B \leq B C = B F = G D = A E \leq E D = C F \leq A C .$

$S o, s e l e c t G C, A D, A G, G B, B F, A E$

Suggest Corrections

Similar questions

Δ A B C

¯ G A + ¯ G B + ¯ G C =

\vec{G A} + \vec{G B} + \vec{G C} .

3 (G A^{2} + G B^{2} + G C^{2}) = B C^{2} + C A^{2} + A B^{2}

O A^{2} + O B^{2} + O C^{2} = G A^{2} + G B^{2} + G C^{2}

G

Δ A B C

\to G A + \to G B + \to G C

Join BYJU'S Learning Program