GATE CS 2011 Q.55 (CS Q.55): 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 54.

The length of the path from $v_5$ to $v_6$ in the MST of previous question with $n = 10$ is

Official answer and solution

Official answer: C
From: Official GATE 2011 answer key

Solution

Trace the unique path connecting vertex v5 and vertex v6 in the minimum spanning tree structure determined in Q54.

In the MST for $n = 10$ , the tree edges form two interlaced chains connected by a single bridging edge:

Odd chain: $v_1 - v_3 - v_5 - v_7 - v_9$ via edges $(v_{k-2}, v_k)$ for odd $k$ .
Even chain: $v_2 - v_4 - v_6 - v_8 - v_{10}$ via edges $(v_{k-2}, v_k)$ for even $k$ .
Bridging edge: $(v_1, v_2)$ with weight 3.

Because the tree contains no cycles, the unique simple path between $v_5$ (on the odd chain) and $v_6$ (on the even chain) must pass through the bridging edge $(v_1, v_2)$ :

v_5 \to v_3 \to v_1 \to v_2 \to v_4 \to v_6

Calculate the weight of each edge along this path:

Edge $(v_5, v_3)$ : weight $= 5 + 3 = 8$
Edge $(v_3, v_1)$ : weight $= 3 + 1 = 4$
Edge $(v_1, v_2)$ : weight $= 1 + 2 = 3$
Edge $(v_2, v_4)$ : weight $= 2 + 4 = 6$
Edge $(v_4, v_6)$ : weight $= 4 + 6 = 10$

Sum the weights along the path:

\text{Total path length} = 8 + 4 + 3 + 6 + 10 = 31

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: 55 of 65, printed as CS Q.55
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.