The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
3.6k views

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$
asked in Algorithms by Veteran (101k points)
edited by | 3.6k views
+8
Another way to solve this:

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

Source:g4g
+6

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

Just do one more optimization for getting quick answer in some cases. Instead of drawing complete graph, look weight matrix pick min value(which is not forming cycle with already included vertices). Repeat this process until all edges are covered.  

0
The answer could have been 7 had the condition that vertex 0 is leaf wouldn't have been there.
+1
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 ...

4 Answers

+26 votes
Best answer

2010-Q50-51

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

answered by Junior (865 points)
edited by
–3
no ans is B
0
Ans is (d)   10
0
bt 0 is the leaf node
0
what is the roll of this line in this question: "vertex 0 is a leaf node in the tree T"??? what is the meaning of this??
+3

^

|

|______ In a tree, leaf node can have only one adjacent node (its parent in the tree).

            //Try few examples to convince yourself that this indeed is true.

Given, vertex 0 is a leaf node => it can be connected to either V1 or V2 or V3 or V4 (i.e. not more than one neighbor node) , in any MST formed.

Eg:  V0         (or)             V0                                        (but not)           V0

      |                                      \                                                              |     \

      |                                         \                                                           |         \

      |                                             \                                                       |             \

     V1                                           V3                                                   V1             V3

and so on ...

Now keeping above condition in mind, try to find the possible MST's.

0
If o is leaf node then we remove the o th row and column then I get min. weight of spanning tree 7 it's possible
0
Why we are not considering 0-3 node with weight 1?
+10 votes

As 0 is the leaf therefore

In both the cases weight is=1+4+2+3=10

answered by Active (3k points)
edited by
0
The link is broken..
0
now see
+6 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
answered by (107 points)
0 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

 

answered by (169 points)
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,529 questions
46,674 answers
139,821 comments
57,589 users