+1 vote
1.4k views

5. 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 choosen is ?

(1) AD, AE, AG, GC, GB, BF

(2) GC, GB, BF, GA, AD, AE

(3) GC, AD, GB, GA, BF, AE

(4) AD, AG, GC, AE, GB, BF

retagged | 1.4k views
0
Where is graph????
0
Incomplete question.

Edge weight of BD is not given.

+1 vote

Kruskal's algorithm is an algorithm that finds a minimum spanning tree for a connected weighted graph. It finds a safe edge to add to the growing forest by finding, of all the edges that connects any two trees in the forest, an edge $(u,v)$ of least weight. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

The given graph is

We can see that $DB's$ weight is not given.

We know that, for any weighted graph, if the weight of an certain edge isn't given, then the weight'll be $1$(default)

Edge No. Vertex Pair Edge Weight
E1 (B,D) 1
E2 (G,C) 2
E3 (A,D) 2
E4 (B,G) 3
E5 (A,G) 3
E6 (A,E) 4
E7 (D,G) 4
E8 (B,C) 4
E9 (B,F) 4
E10 (D,E) 5
E11 (C,F) 5
E12 (A,C) 6

Graph

Edge E5 will not counted, as it'll create cycle.

Edge E7,E8 will not counted, as it'll create a cycle.

Edge E10, E11, E12 will not connected, they'll make a cycle.

∴ $\color{green}{\text{Total Cost}}= 1+2+2+3+4+4$

$\qquad\qquad = \color{gold}{16}$

$\color{violet}{\text{The List of the edges of the tree in the order in which they are choosen is}}$ $\color{maroon}{\text{BD, GC, AD, BG, AE, BF}}$

by Boss (15.4k points)
edited
0
@Sukanya Das
"We know that, for any weighted graph, if the weight of an certain edge isn't given, then the weight'll be 1(default)"

I have never heard of such a thing , neither read it in any standard text
could you give some reference please.
0

Sukanya Das Why do we need the value of the value of BD?

0

Rameesh, when i  studied graph theory, i learnt that from my our college professor.

anyway i'll try to give you reference

0

pankaj_vir , to find MST , we need the weight of every edges.

0

Sukanya Das, I know that, but nothing is written anywhere that if no weight is given take 1

0
no option matches with this order.