66 66 votes The number of distinct minimum spanning trees for the weighted graph below is _____ Algorithms gatecse-2014-set2 algorithms minimum-spanning-tree numerical-answers normal + – go_editor 21.1k views answer comment Share Follow Print See all 4 Comments 4 4 Comments reply vishalshrm539 commented Oct 16, 2018 reply Follow flag I guess, Kirchoff's theorem is used to find total no. of spanning Trees, not the MSTs? 14 14 replyShare ayushsomani commented Jan 11, 2020 reply Follow flag @vishalshrm539 And it should be unweighted graph too? 1 1 replyShare s_dr_13 commented Nov 2, 2020 reply Follow flag solve kar lega exam mein 9x9 matrix ?? 15 15 replyShare Sidd1425 commented Nov 7, 2024 reply Follow flag Cost of the MSTs is 11 0 0 replyShare Please log in or register to add a comment.
Best answer 98 98 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 6 6 Comments reply Show 3 previous comments talha hashim commented Jul 4, 2018 reply Follow flag nice explanation @Arjun sir 0 0 replyShare BabluNaren commented Dec 21, 2018 reply Follow flag I Think that the answer might be 9! we have 3 possibilities on the left and 3 on the right. 0 0 replyShare HitechGa commented Dec 1, 2020 reply Follow flag @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 0 replyShare Please log in or register to add a comment.
7 7 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 1 comment 1 1 comment reply pavansan commented Jan 6, 2025 reply Follow flag nice explaination 0 0 replyShare Please log in or register to add a comment.
4 4 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 0 reply Please log in or register to add a comment.
