The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
2.8k views

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

asked in Algorithms by Veteran (101k points) | 2.8k views
+3

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

2 Answers

+33 votes
Best answer

$6$ is the answer. 

$2\times3=6$ possibilities

 

answered by Veteran (357k 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 :)
+4
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 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
answered by (395 points)


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

39,440 questions
46,623 answers
139,377 comments
57,026 users