The GATE Grind

GATE 2020 CS – Question 59

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

Consider a graph $G=(V,E)$, where $V=\{v_1,v_2,\dots,v_{100}\}$, $E=\{(v_i,v_j)\mid 1\le i<j\le 100\}$, and weight of the edge $(v_i,v_j)$ is $|i-j|$. The weight of minimum spanning tree of $G$ is ______.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 99 to 99

Explanation

$G$ is the complete graph on 100 vertices with weight $|i-j|$ on edge $(v_i,v_j)$.

The lightest edges are those with $|i-j|=1$: $(v_1,v_2),(v_2,v_3),\dots,(v_{99},v_{100})$. There are 99 of them and they form a path through **all** 100 vertices, which is a spanning tree. Every edge in it has weight 1, and a spanning tree needs exactly 99 edges, so no spanning tree can be cheaper.

MST weight $=99\times1=\mathbf{99}$.

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

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