The GATE Grind

GATE 2021 CS (CS1) – Question 27

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 1 mark · Numerical answer

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 ______.

Diagram for GATE 2021 CS (CS1) question 27

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 3

Explanation

Label the grid vertices $a,b,c$ (top row), $d,e,f$ (middle row), $g,h,i$ (bottom row).

**Weight-0.1 edges:** $a$–$b$, $b$–$c$, $d$–$e$, $h$–$i$, $d$–$g$, $e$–$h$, $f$–$i$.
These 7 edges contain no cycle, so Kruskal takes all of them. They form two components:
- $\{a,b,c\}$
- $\{d,e,f,g,h,i\}$ (joined by $d$–$e$, $d$–$g$, $e$–$h$, $h$–$i$, $f$–$i$).

**Connecting them:** a spanning tree on 9 vertices needs 8 edges, so exactly one weight-0.9 edge must join the two components. The weight-0.9 edges crossing between them are $a$–$d$, $b$–$e$ and $c$–$f$. The other 0.9 edges lie inside the big component and would create a cycle.

Any one of the 3 crossing edges gives a minimum spanning tree (total weight $7(0.1)+0.9$), so there are **3** MSTs.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →