The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+25 votes

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

asked in Algorithms by Veteran (115k points) | 3.6k views

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

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

2 Answers

+38 votes
Best answer

$6$ is the answer. 

$2\times3=6$ possibilities


answered by Veteran (396k points)
edited by
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 :)
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.
sir, is there any formula to find no of spanning tree?
nice explanation @Arjun sir
I Think that the answer might be 9! we have 3 possibilities on the left and 3 on the right.
+1 vote

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
answered by (441 points)

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,129 questions
53,252 answers
70,506 users