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.
What will be the cost of the minimum spanning tree (MST) of such a graph with \(n\) nodes?
- A.
\(\frac{1}{12} (11n^2 - 5 n)\) - B.
\(n^2-n+1\) - C.
\(6n-11\) - D.
\(2n+1\)
Attempted by 121 students.
Show answer & explanation
Correct answer: B
Answer: n^2 - n + 1
Key observations:
Edges present and their weights: for i = 1..n-1 the edge (i, i+1) has weight 2i+1; for i = 1..n-2 the edge (i, i+2) has weight 2i+2.
Constructive MST (the tree Kruskal's algorithm picks): take edges (1,2) and (1,3) first (weights 3 and 4). Then for each j = 2..n-2 include edge (j, j+2) of weight 2j+2. The chosen edges are (1,2), (1,3), (2,4), (3,5), ..., (n-2, n). These are n-1 edges and form a spanning tree.
Compute the total weight: 3 + 4 + sum_{j=2}^{n-2} (2j+2). Evaluate the sum:
3 + 4 + sum_{j=2}^{n-2} (2j+2) = 7 + 2*sum_{j=2}^{n-2} j + 2(n-3) = 7 + (n^2 - n - 6) = n^2 - n + 1.
By Kruskal's correctness (edges are processed in increasing weight and each chosen edge connects a new node without creating a cycle), no cheaper spanning tree can exist, so n^2 - n + 1 is the MST cost for n > 2.
A video solution is available for this question — log in and enroll to watch it.