Skip to content
GATEiit

GATE CSE 2024 Session 2 Q59: Count the minimum spanning trees of a weighted graph

Question

The number of distinct minimum-weight spanning trees of the following graph is _________

Weighted graph on vertices a, b, c, d, e, f, g: a–b 1, a–f 1, c–d 1, d–e 1, b–c 3, f–e 3, and weight-2 edges a–g, b–g, f–g, c–g, d–g, e–g
Tap the figure to enlarge

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 9 (official GATE 2024 final answer key)

Concept used: Kruskal's algorithm: count the independent choices among equal-weight edges.

First step: Take all four weight-1 edges, giving components {a,b,f}\{a, b, f\}, {c,d,e}\{c, d, e\} and {g}\{g\}; then count ways to join gg to each using weight-2 edges.

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 2024 Session 2 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2024 Session 2 questions →