UGC NET CSE | November 2017 | Part 2 | Question: 5

Question

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

• A. AD, AE, AG, GC, GB, BF
• B. GC, GB, BF, GA, AD, AE
• C. GC, AD, GB, GA, BF, AE
• D. AD, AG, GC, AE, GB, BF

Comments

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.

---

Done ✅

Answer 1

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.

Answer 2

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

Add edge E1

Add edge E2

Add edge E3

Add edge E4

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

Add edge E6

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

Add edge E9

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

Comments

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.