Skip to content
GATEiit

GATE CSE 2021 Set 1 Q27: Number of minimum spanning trees of a 3×3 grid graph

Question

Consider the following undirected graph with edge weights as shown:

The number of minimum-weight spanning trees of the graph is ________.

Nine vertices in a 3 by 3 grid joined by horizontal and vertical edges of weight 0.1 or 0.9: top row edges 0.1 and 0.1; middle row edges 0.1 and 0.9; bottom row edges 0.9 and 0.1; top-to-middle vertical edges all 0.9; middle-to-bottom vertical edges all 0.1
Tap the figure to enlarge

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 3 (official GATE 2021 final answer key)

Concept used: Kruskal's algorithm: count the ways of choosing among equal-weight edges that close no cycle.

First step: Add all 0.1 edges first: they form two components (the top row, and the bottom two rows). Then count the 0.9 edges that can join them.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2021 Set 1 questions →