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.7k 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 Show 3 previous comments 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.