edited by
13,516 views
47 votes
47 votes

The number of distinct minimum spanning trees for the weighted graph below is _____

edited by

3 Answers

Best answer
69 votes
69 votes

$6$ is the answer. 

$2\times3=6$ possibilities

edited by
3 votes
3 votes

Below diagram shows a minimum spanning tree. Highlighted (in green) are the edges picked to make the MST.

MST2

In the right side of MST, we could either pick edge ‘a’ or ‘b’. In the left side, we could either pick ‘c’ or ‘d’ or ‘e’ in MST.


 

There are 2 options for one edge to be picked and 3 options for another edge to be picked. Therefore, total 2*3 possible MSTs.

 

 

https://www.geeksforgeeks.org/gate-gate-cs-2014-set-2-question-62/

2 votes
2 votes
3*2=6

Delete all 2 edges and try to form spanning tree but you cannt

Therefore there there are 3 choices for

Upper right section and 2 for bottom triangle
Answer:

Related questions

44 votes
44 votes
7 answers
2
27 votes
27 votes
5 answers
3
go_editor asked Sep 28, 2014
11,377 views
Consider the function func shown below: int func(int num) { int count = 0; while (num) { count++; num>>= 1; } return (count); }The value returned by func($435$) is ______...