GATE 2020 CS – Question 59
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
- GATE 2019 CS Q48
- GATE 2018 CS Q40
- GATE 2018 CS Q57
- GATE 2015 CS (CS1) Q51
- GATE 2015 CS (CS1) Q63
- GATE 2016 CS (CS1) Q21
All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →