47 votes 47 votes The number of distinct minimum spanning trees for the weighted graph below is _____ Algorithms gatecse-2014-set2 algorithms spanning-tree numerical-answers normal + – go_editor asked Sep 28, 2014 • edited May 8, 2021 by gatecse go_editor 13.8k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply vishalshrm539 commented Oct 16, 2018 reply Follow Share I guess, Kirchoff's theorem is used to find total no. of spanning Trees, not the MSTs? 12 votes 12 votes ayushsomani commented Jan 11, 2020 reply Follow Share @vishalshrm539 And it should be unweighted graph too? 1 votes 1 votes s_dr_13 commented Nov 2, 2020 reply Follow Share solve kar lega exam mein 9x9 matrix ?? 10 votes 10 votes Please log in or register to add a comment.
Best answer 69 votes 69 votes $6$ is the answer. $2\times3=6$ possibilities Arjun answered Oct 18, 2014 • edited May 8, 2021 by gatecse Arjun comment Share Follow See all 6 Comments See all 6 6 Comments reply GATE_2016 commented Nov 13, 2015 reply Follow Share 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 :) 0 votes 0 votes Arjun commented Nov 13, 2015 reply Follow Share 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. 9 votes 9 votes Digvijay singh commented Feb 4, 2017 reply Follow Share sir, is there any formula to find no of spanning tree? 0 votes 0 votes talha hashim commented Jul 4, 2018 reply Follow Share nice explanation @Arjun sir 0 votes 0 votes BabluNaren commented Dec 21, 2018 reply Follow Share I Think that the answer might be 9! we have 3 possibilities on the left and 3 on the right. 0 votes 0 votes HitechGa commented Dec 1, 2020 reply Follow Share @Arjun, sir, why we considering the graph as labeled only. Since it is a numerical type question, we shall not get any clue as to what the question paper setter wants us to assume. If we assume the graph as unlabeled (since the nodes are not given labels explicitly) we might as well think about working with only the isomorphic structures, which gives the answer as $2$ for this above graph. When we should apply what strategy, please enlighten us... 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes Below diagram shows a minimum spanning tree. Highlighted (in green) are the edges picked to make the MST. 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/ Madhab answered Jan 20, 2020 Madhab comment Share Follow See all 0 reply Please log in or register to add a comment.
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 tocshark answered Jan 13, 2017 tocshark comment Share Follow See all 0 reply Please log in or register to add a comment.