1,508 views

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

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

where is tree??
Where is graph????
Incomplete question.

Edge weight of BD is not given.

@abhishekmehta4u If edge weight is not given and it is not in any of the options, we may safely assume that BD is having infinite weight.

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.

In the given graph edge weight of $\text{BD}$ is not given. But if we see the options, $\text{BD}$ is not in any of them and so we can assume its weight is infinity (or a large value).

The smallest edge weight is $2$ and any of an edge with weight $2$ can be picked by Kruskal’s algorithm which are $\text{AD}$ or $\text{GC}.$ These $2$ edges are not in a cycle and so both must be the first two edges selected by Kruskal’s algorithm. Only option C satisfies.

by

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}}$

@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.

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

edited

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

anyway i'll try to give you reference

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

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

no option matches with this order.

1 vote