edited by
23,604 views
43 votes
43 votes

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

  1. $7$
  2. $8$
  3. $9$
  4. $10$
edited by

8 Answers

Best answer
42 votes
42 votes

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

27 votes
27 votes

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

 

10 votes
10 votes
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
4 votes
4 votes

 

 vertex 0 is a leaf node in the tree T.

This line means , ki 0th 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 0th 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.

Answer:

Related questions

37 votes
37 votes
5 answers
1
26 votes
26 votes
4 answers
2