GATE CS 2011 Q.54 (CS Q.54): Minimum Spanning Trees

Linked answer questions

Statement for Linked Answer Questions 54 and 55:

An undirected graph $G(V,E)$ contains $n$ ( $n > 2$ ) nodes named $v_1, v_2, \dots, v_n$ . Two nodes $v_i, v_j$ are connected if and only if $0 < |i - j| \le 2$ . Each edge $(v_i, v_j)$ is assigned a weight $i + j$ . A sample graph with $n = 4$ is shown below.

Sample undirected graph with four vertices v1, v2, v3, v4 where edge (vi, vj) has weight i + j for 0 < |i - j| <= 2

Shared with question 55.

What will be the cost of the minimum spanning tree (MST) of such a graph with $n$ nodes?

$\frac{1}{12}(11n^2 - 5n)$

$n^2 - n + 1$

$6n - 11$

$2n + 1$

Official answer and solution

Official answer: B
From: Official GATE 2011 answer key

Solution

Apply Kruskal's algorithm to find which edges are included in the MST and evaluate the closed-form summation of their weights.

The graph contains vertices $v_1, v_2, \dots, v_n$ . An edge $(v_i, v_j)$ exists with weight $i + j$ if and only if $0 < |i - j| \le 2$ .

List candidate edges in increasing order of weight:

Weight 3: $(v_1, v_2)$ . Included in MST.
Weight 4: $(v_1, v_3)$ . Included in MST.
Weight 5: $(v_2, v_3)$ . Forms cycle with $(v_1, v_2)$ and $(v_1, v_3)$ , so discarded.
Weight 6: $(v_2, v_4)$ . Connects $v_4$ to the tree. Included in MST.
Weight 7: $(v_3, v_4)$ . Forms cycle with $(v_2, v_3)$ paths, discarded.
Weight 8: $(v_3, v_5)$ . Connects $v_5$ to the tree. Included in MST.

In general, for any step $k \ge 3$ , the edge $(v_{k-2}, v_k)$ of weight $(k - 2) + k = 2k - 2$ connects new vertex $v_k$ to the tree without creating cycles, while edges of the form $(v_{k-1}, v_k)$ have larger weight $2k - 1$ and would create cycles.

The complete set of $n - 1$ edges in the MST consists of:

$(v_1, v_2)$ with weight 3.
$(v_{k-2}, v_k)$ with weight $2k - 2$ for all $k \in \{3, 4, \dots, n\}$ .

Compute total MST cost:

\text{Cost} = 3 + \sum_{k=3}^n (2k - 2)

Notice that for $k = 3$ , $2(3) - 2 = 4$ , which is the weight of $(v_1, v_3)$ .
Evaluating the sum:

\sum_{k=3}^n (2k - 2) = 2 \sum_{j=2}^{n-1} j = 2 \left[ \frac{(n-1)n}{2} - 1 \right] = (n - 1)n - 2 = n^2 - n - 2

Adding the first edge of weight 3:

\text{Cost} = 3 + (n^2 - n - 2) = n^2 - n + 1

Verification for small $n$ :

For $n = 3$ : $\text{Cost} = 3^2 - 3 + 1 = 7$ . Edges are $(v_1, v_2)$ of weight 3 and $(v_1, v_3)$ of weight 4, sum = 7.
For $n = 4$ : $\text{Cost} = 4^2 - 4 + 1 = 13$ . Edges are $(v_1, v_2)$ of weight 3, $(v_1, v_3)$ of weight 4, and $(v_2, v_4)$ of weight 6, sum = 13.
The formula holds for all $n > 2$ .

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2011 Computer Science and Information Technology (CS)
Question: 54 of 65, printed as CS Q.54
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.