3.4k views

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

+3

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

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

$6$ is the answer.

$2\times3=6$ possibilities

edited
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 :)
+5
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

1
2