GATE CSE 2010 | Question: 50

Question

Consider a complete undirected graph with vertex set $\{0, 1, 2, 3, 4\}$. Entry $W_{ij}$ in the matrix $W$ below is the weight of the edge $\{i, j\}$

$$W=\begin{pmatrix} 0 & 1 & 8 & 1 & 4 \\ 1 & 0 & 12 & 4 & 9 \\ 8 & 12 & 0 & 7 & 3 \\ 1 & 4 & 7 & 0 & 2 \\ 4 & 9 & 3 & 2 & 0 \end{pmatrix}$$

What is the minimum possible weight of a spanning tree $T$ in this graph such that vertex $0$ is a leaf node in the tree $T$?

• A. $7$
• B. $8$
• C. $9$
• D. $10$

Comments

Another approach

1) create mst with 0 included

2) now remove 0 (if it is not leaf node already  by removing most weighted  edge until it becomes leaf node i.e. it becomes degree 1) .

3) add the removed vertex with min edge other than removed edge

---

If 0 leaf condition is not given,

then,   (0,1) (0,3) (3,4) (4,2)   cost = 7

If 0 is leaf then two MST’s possible,

1.  (0,1) (1,3) (3,4) (4,2)        cost =10
2.  (0,3) (3,1) (3,4) (4,2)        cost =10

---

here when we make the min cost tree of cost 7 then here the node 0 will become internal node in our MST not the leaf node so that we will consider this mst as min cost bcoz in question they mentioned that the node 0 should become leaf node in mst 

so that we try to get another mst which will cost 10 so it is our answer

also look pooja mam comment

Puja Mishra

 commented Jan 11, 2018

Take 0 as destination ... then solve it in bottom up approach ... take those nodes which hav minimum value ... If there r multiple minimum values ... consider both .... Then u will get path ... 0-1-3-4-2 = 1+4+2+3 = 10 ... hence option D ...

---

Answer 1

One possible traversal be like this also-

2--->4--->3--->1--->0 having weights 3, 2, 4, 1 respectively and 0 is at last position means 'at leaf' as mentioned in the question.

So, total weight is 3+2+4+1 = 10 answer.

Answer 2

$V_0$ is supposed to be the leaf.

In a tree, a leaf has degree 1. Hence, we can choose exactly one edge for $V_0$

Obviously, we'll choose any of the two edges with weight 1. (Blue colour — select either one.)

Then, apply Kruskal; we'd choose only minimum weight edges, ie, 2, 3 and 4. (Red colour)

Weight = $1+2+3+4=10$

Comments

Why you chose $4$. According to your logic now $V_0$ will have $2$ edges. One with weight $1$ and other with weight $4$. Isn't it??

---

That's not the correct explanation.

One way is to choose all the edges leaving the $0^{th}$ column and rows and then adding the minimum weight in the resultant tree.

---

Yeah, thanks for pointing that out. I circled the wrong 4.

The 4 corresponding to $V_1$ should be encircled.

Answer 3

Apply kruskal :

Take first minimum : 1, either 01 or 03, doesn’t matter

Say, I take 01, now 0 to anything or anything to 0 is not possible because 0 is leaf, ignore such weights now.

Take next minimum : 2 (34)

Next : 3 (24)

Next : 4 (13)

Done ! You got the MST.

1+2+3+4 = 10

Answer 4

here when we make the min cost tree of cost 7 then here the node 0 will become internal node not the leaf node so that we will consider this mst as min cost bcoz in question they mentioned that the node 0 will become leaf node in mst 

so that we try to get another mst which will cost 10 so it is our answer