An undirected graph \(G(V,E)\) contains \(n \: (n>2)\) nodes named \(v_1,v_2,…
2011
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 < \mid i-j\mid \leq 2\). Each edge \((v_i,v_j)\) is assigned a weight \(i+j\). A sample graph with \(n=4\) is shown below.
The length of the path from \(v_5\) to \(v_6\) in the MST of previous question with \(n = 10\) is
- A.
11
- B.
25
- C.
31
- D.
41
Attempted by 123 students.
Show answer & explanation
Correct answer: C
Key insight: build the minimum spanning tree using Kruskal's algorithm. For any i, the edge (vi,vi+1) has weight 2i+1 and the edge (vi,vi+2) has weight 2i+2, so edges are chosen in increasing numeric order.
Pick edges in increasing weight. The MST edges chosen (in order) for n=10 are:
(v1,v2)=3, (v1,v3)=4, (v2,v4)=6, (v3,v5)=8, (v4,v6)=10, (v5,v7)=12, (v6,v8)=14, (v7,v9)=16, (v8,v10)=18.
Find the path between v5 and v6 in this tree:
The path is v5 → v3 → v1 → v2 → v4 → v6 with edge weights 8, 4, 3, 6, 10 respectively.
Total path length = 8 + 4 + 3 + 6 + 10 = 31.
Therefore the correct answer is 31.
A video solution is available for this question — log in and enroll to watch it.