9 votes 9 votes How many distinct minimum weight spanning trees does the following undirected, weighted graph have ? $1$ $2$ $4$ $6$ $8$ Algorithms tifr2018 algorithms minimum-spanning-tree + – Arjun asked Dec 10, 2017 • recategorized Nov 21, 2022 by Lakshman Bhaiya Arjun 2.6k views answer comment Share Follow See 1 comment See all 1 1 comment reply hs_yadav commented Dec 10, 2017 reply Follow Share option C...... 4 2 votes 2 votes Please log in or register to add a comment.
Best answer 10 votes 10 votes Minimum Weight Spanning Trees of the given graph are $4$ Minimum Weight Spanning Trees each having cost of $14$ Hence, option (C) is the correct answer Ashwani Kumar 2 answered Dec 11, 2017 • edited Jun 20, 2019 by ajaysoni1924 Ashwani Kumar 2 comment Share Follow See all 4 Comments See all 4 4 Comments reply Rameez Raza commented Dec 11, 2017 reply Follow Share it should be 4 0 votes 0 votes Mahmood Hussain commented Dec 7, 2019 reply Follow Share Is there any standard way (any standard formula) to calculate the number of spanning trees in an unweighted undirected graph? 0 votes 0 votes pritishc commented Jan 8, 2020 reply Follow Share There is, but it's very time consuming. It's known as Kirchoff's theorem. You first write down the incidence matrix $B$ of the graph, find its transpose $B^T$, then multiply the two to get the Laplacian matrix $L = B.B^T$. Then you find the determinant of $L$ and that is the number of MSTs in the graph. So you are looking at -: 1. Transpose operation. 2. Matrix multiplication operation ($B$ can be quite big if the number of nodes is large). 3. Finding the determinant of a large matrix (if $B$ was large), which means reducing to row echelon form and multiplying diagonal elements. Easier is to just use combinatorics. As you keep adding edges to your MST, you will find that -: 1. Edges of weight 1 and 2 here must be added - they are non-negotiable, as they are of least weight and adding them does not form a cycle. 2. Edges of weight 3 must not be added - they would form a cycle. 3. Edges of weight 4 and 5 are both two in number and any one must be added - so here you can use counting. 2 choices for each, so $2 * 2 = 4$. Therefore 4 MSTs. 3 votes 3 votes s_dr_13 commented Jul 21, 2020 reply Follow Share @Ashwani Kumar 2 How did you write these images what software did you use ? BTW your answer was very beautfiul 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes option C $4$ minimum spanning trees are possible $2$ choices for edges with weight $5$ (any one can be chosen) $2$ choices for edges with weight $4$ (any one can be chosen) Manoja Rajalakshmi A answered Dec 10, 2017 • edited Dec 6, 2018 by Manoja Rajalakshmi A Manoja Rajalakshmi A comment Share Follow See all 0 reply Please log in or register to add a comment.