GATE 2021 CS – Question 27
Consider the following undirected graph (a 3x3 grid of vertices, 12 edges) with edge weights: top row horizontal edges 0.1, 0.1; second row horizontal 0.1, 0.9; bottom row horizontal 0.9, 0.1; left column vertical edges 0.9, 0.1; middle column vertical 0.9, 0.1; right column vertical 0.9, 0.1. The number of minimum-weight spanning trees of the graph is ______.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 3
Explanation
Take all 0.1 edges that form no cycle, then add the fewest 0.9 edges to connect the components. Counting the choices of 0.9 edges that connect the components without a cycle gives 3 MSTs.