GATE CS 2011 Q54 — Minimum Spanning Trees

To find the cost of the Minimum Spanning Tree (MST) for a graph with $n$ nodes, we can analyze the structure of the MST using Kruskal's algorithm.

For any node $v_i$, it is connected to $v_j$ if and only if $0 < |i-j| \le 2$, with edge weight $i+j$. Sorting the edges by weight, the lowest-weight edges that do not form a cycle are selected:

• The edge $(v_1, v_2)$ with weight $1 + 2 = 3$.
• For each $i$ from $3$ to $n$, the edge $(v_{i-2}, v_i)$ with weight $(i-2) + i = 2i - 2$.

These $n-1$ edges connect all nodes without cycles (the odd-indexed nodes form one path, the even-indexed nodes form another, and they are joined by the edge $(v_1, v_2)$).

The total cost of this MST is:

Letting $j = i-1$, the summation becomes:

Alternative Method (Substitution):

For $n = 4$:

• The edges are $(v_1, v_2)$ [wt 3], $(v_1, v_3)$ [wt 4], $(v_2, v_3)$ [wt 5], $(v_2, v_4)$ [wt 6], and $(v_3, v_4)$ [wt 7].
• The MST selects edges $(v_1, v_2)$, $(v_1, v_3)$, and $(v_2, v_4)$ with total cost $3 + 4 + 6 = 13$.

Substituting $n = 4$ into the options:

• Option A: $\frac{1}{12}(11(16) - 5(4)) = 13$
• Option B: $4^2 - 4 + 1 = 13$
• Option C: $6(4) - 11 = 13$

For $n = 5$, the MST selects $(v_1, v_2)$, $(v_1, v_3)$, $(v_2, v_4)$, and $(v_3, v_5)$ with total cost $3 + 4 + 6 + 8 = 21$. Substituting $n = 5$ into the remaining options:

• Option B: $5^2 - 5 + 1 = 21$ (Correct)
• Option A: $\frac{250}{12} \approx 20.83$
• Option C: $6(5) - 11 = 19$