in Algorithms edited by
3,036 views
23 votes

Consider a weighted undirected graph with vertex set $V = \{n1, n2, n3, n4, n5, n6 \}$ and edge set $E = \{(n1,n2,2), (n1,n3,8), (n1,n6,3), (n2,n4,4), (n2,n5,12), (n3,n4,7), (n4,n5,9), (n4,n6,4)\}$.

The third value in each tuple represents the weight of the edge specified in the tuple.

  1. List the edges of a minimum spanning tree of the graph.
  2. How many distinct minimum spanning trees does this graph have?
  3. Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?
  4. Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning tree of a graph?
in Algorithms edited by
3k views

1 comment

Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?

Does this talk about any MST of any graph possible?

In that case, shouldn't this MST make the given statement false? Please help :(

Same can be argued for Option D.

0

Subscribe to GO Classes for GATE CSE 2022

3 Answers

25 votes
 
Best answer
  1. Edges with weights: $2,3,4,7,9$

$\text{Minimum Spanning Tree}$
  1. Number of distinct minimum spanning tree: $2 (2^{\text{nd}}$ with a different edge of weight $4)$
  2. Yes
  3. Yes 
edited by

6 Comments

Although question is simple but it will be good if you can add some explanation for other options for justification.
3

Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?

What does "minimum" mean here? Does it mean a "value" or a specific edge with the minimum value? 

0

@jayendra, hi sir, how is the answer for c) and d) yes? for c), the minimum weight edge is 2 which is present in both the spanning tree's, so it's not unique. for d), the maximum weight edge is 9 which is also present in both the spanning tree's, so it's also not unique. According to this, answer should be no for c) and d). Am i missing something here, please reply. 

0

What I think is, in this complex statement. Both options C and D are Correct(YES).

OPTION C: YES

  1. Construct a particular MST.
  2. make a set of all weights in MST i.e. {2,3,4,7,9}
  3. min wt=2, has occurred only once in this set i.e. unique(This is what they are asking).
  4. repeat above over all MSTs.(i.e. min wt=2 is unique in all MSTs).

(I dont think that they are comparing between two diff sets/MSTs).

    

        

1
Can any one tell me the meaning of option c n d @jayendra
1
edited by

@srahulda

Minimum and maximum edge weights are unique(min=2 and max=9) in the 2 possible MSTs. (we don't have more than 1 minimum/maximum edges)

3
9 votes

Minimum spanning tree:

1 comment

Please add this image in your first answer. It will make answer more elegant.
0
0 votes

The number of vertices in the graph is 6. So the number of edges in the MST will be 5.

A) {(n1,n2,2),(n1,n6,3),(n2,n4,4),(n3,n4,7),(n4,n5,9)} and {(n1,n2,2),(n1,n6,3),(n3,n4,7),(n4,n5,9),(n4,n6,4)}

B) Number of distinct minimum spanning trees is 2.

C) Yes. It’s 2.

D) Yes. It’s 9.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------

Assumption:

C)Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of the graph?

If we consider the gate question to be correct: options C and  D will be False. Because of duplicate edge weights.

Related questions