The undirected graph on vertices 0,…,4 has weight matrix W=pmatrix0&1&8&1&4\\1&0&12&4&9\\8&12&0&7&3\\1&4&7&0&2\\4&9&3&2&0pmatrix. Find the minimum spanning-tree weight subject to vertex 0 being a leaf.

GATE 2010 CS (CS1) – Question 60

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

The undirected graph on vertices 0,…,4 has weight matrix $$W=\begin{pmatrix}0&1&8&1&4\\1&0&12&4&9\\8&12&0&7&3\\1&4&7&0&2\\4&9&3&2&0\end{pmatrix}.$$ Find the minimum spanning-tree weight subject to vertex 0 being a leaf.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) 10

Explanation

With vertex zero a leaf, removing it must leave a spanning tree on vertices one through four. Their MST uses edges 3–4 of weight two, 2–4 of weight three, and 1–3 of weight four, totalling nine. Attach vertex zero by a cheapest incident edge of weight one. Total ten, D.

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

GATE 2010 CS (CS1) Q61 – The undirected graph on vertices 0,…,4 has weight matrix…
GATE 2015 CS (CS2) Q47 – Match algorithms 1 Dijkstra shortest path, 2 Floyd–Warshall all-pairs shortest paths, 3…
GATE 2015 CS (CS3) Q55 – A connected undirected graph has 100 vertices and 300 edges. Its minimum spanning-tree…
GATE 2021 CS (CS2) Q11 – G is connected, undirected and weighted. S1: Some minimum-weight edge of G is present in…
GATE 2021 CS (CS2) Q56 – For the directed graph shown, which statements hold?
GATE 2021 CS (CS2) Q65 – In the DAG shown with source s, a path’s quality is the product of its edge weights. A…

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