The GATE Grind

GATE 2014 CS (CS2) – Question 62

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Numerical answer

Find the number of distinct minimum spanning trees of the weighted graph shown.

Diagram for GATE 2014 CS (CS2) question 62

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 6 to 6

Explanation

The five weight1edges form a forest and are required by the weight ordering. Contract their components. The large left component joins the upper-right component through one of three weight2edges; the bridge to the small triangle is forced; its remaining component joins through one of two weight2edges. Thus **3×1×2=6MSTs**, all of equal minimum weight.