Project ForgeConsider a graph G = (V,E), where V = {v₁, v₂, ..., v₁₀₀}, E = {(vᵢ,vⱼ) | 1 ≤ i < j ≤ 100}, and weight of the edge (vᵢ,vⱼ) is |i−j|. The weight of minimum spanning tree of G is ____.
Explanation
G is a complete graph on 100 vertices where edge (vᵢ,vⱼ) has weight |i−j|. The cheapest possible edges are the 99 'consecutive' edges (vᵢ,vᵢ₊₁), each of weight exactly 1, and connecting every consecutive pair forms a spanning path (hence a spanning tree) using only weight-1 edges — no spanning tree can do better since it needs at least 99 edges total and no edge has weight less than 1. MST weight = 99 × 1 = 99.
Source: GATE CS 2020 (2020)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.