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

thats correct

---

https://youtu.be/j6p85xzIm28?si=tXvOT2sAwC20P49E

---

If vertex 0 is not leaf node then sum = 1 + 1 + 2 + 3 = 7

Answer 1

Answer is (D) $10$. The edges of the spanning tree are: $0 - 1, 1 - 3, 3 - 4, 4 - 2$. Total Weight $= 10$
 

Comments

0 is connected to only one vertex.

And the minimum weight is 1 which is from 0 to other vertex.

---

easily solved

 

---

Minimum Spanning tree

N vertices

N-1 edges

In problem 5 vertices

We should take 5-1 (4 ) edges of low values

That is 1+2+3+4=10

Answer 2

To get Minimum Spanning Tree with 0 as leaf node, we must first remove node 0 from the graph. Then we must find MST for the remaining graph and then join 0 to the obtained MST with minimum weight edge. Well this was somewhat obvious.

But how to solve it in most efficient way? We should not draw the graph and then look for MST, it will take lot of time. Instead we should make use of the given weight matrix to find the MST, as shown below:

 As node 0 is removed, we won't consider 0th row and 0th column.

Now, list down edges in increasing order of their weight:

(3-4) => 2, (2-4) => 3, (1-3) => 4, (2,3) => 7 and so on..

To get MST, we must form edges in the above increasing order such that there is no cycle until all vertices are covered.

 Joining node 0 to the MST with minimum edge weight.

So minimum possible weight = 2+3+4+1 = 10

 

Comments

nice explanation

---

Node 2 is also becoming leaf node?

Answer 3

For finding minimum spanning tree with vertex 0 as a leaf node,first of all remove 0th row and 0th column and then get the MST of remaining graph and then connect the vertex 0 with the edge with minimum weight(we have two options as there are two 1s in 0th row).

So Answer is (d) i.e. 10

Answer 4

 

 vertex 0 is a leaf node in the tree T.

This line means , ki 0^th vertex hamesa as a leaf node hi hogi.

or agr vo leaf node to uska sirf 1 hi parent hoga.

 

to iska matab ye ki hame 0^th vertex ko sirf 1 edge se hi jodna he.

to is vajy se hamara answer 10 aa rha he .

 

or agr vahi ye tree ki jagh graph hota to hamara answer aata 7.

Comments

Tree ke jgh graph hone ki jrurt nhi h. Agr bs ye cond. Nhi hoti aur normal spanning tree bhi hota to bhi hm vertex 0 ke dono min. Edge 1 le skte the aur mst ka wt. 7 kr skte the.

---

Vahi soch raha hu ki min. toh 7 aa raha hai mera par answer 10 kyu hai

Now got it ki 0 ka ek hi parent hoga!   Thanks for help!

Answer 5

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

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.