The Gateway to Computer Science Excellence
+30 votes
4.4k views

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

in Algorithms by Veteran (105k points) | 4.4k views
+3

One can use Kirchof's theorem to get distinct minimum spanning trees .....

+7
I guess, Kirchoff's theorem is used to find total no. of spanning Trees, not the MSTs?
0

@vishalshrm539

And it should be unweighted graph too? 

3 Answers

+49 votes
Best answer

$6$ is the answer. 

$2\times3=6$ possibilities

 

by Veteran (431k points)
edited by
0
Sir,could you explain? actually i want to know if there is any shortcut for finding total number of minimum spanning trees of a Graph.
The steps i have taken to answer this question
1.I used krushkal's algorithm for finding all the minimum spanning trees.
2..Then i counted all the total no of minimum spanning trees.
But that is a lengthy process & takes some time..So i want to know.. is there any other method for fining it easily? Waiting for your Reply :)
+7
Consider any cycle in a MST- the maximum weighted edge won't be in MST- if there are multiple edges of same max. weight- we get multiple MSTs. This property can be used, though not straight forward.
0
sir, is there any formula to find no of spanning tree?
0
nice explanation @Arjun sir
0
I Think that the answer might be 9! we have 3 possibilities on the left and 3 on the right.
+1 vote
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
by (457 points)
0 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/

ago by Loyal (5.8k 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
50,737 questions
57,324 answers
198,405 comments
105,169 users