The GATE Grind

GATE 2011 CS (CS1) – Question 64

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

An undirected graph has vertices v₁,…,vₙ, n>2. Vertices vᵢ,vⱼ are adjacent iff 0<|i−j|≤2; edge weight is i+j. The drawing shows n=4. Find MST cost for general n.

Diagram for GATE 2011 CS (CS1) question 64
  1. $(11n^2-5n)/12$
  2. $n^2-n+1$
  3. $6n-11$
  4. $2n+1$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $n^2-n+1$

Explanation

Kruskal selects edge (1,2) of weight three, then for each j≥3 the lighter edge to j is (j−2,j), of weight 2j−2. These edges connect every new vertex and form a tree. Total is $3+\sum_{j=3}^n(2j-2)=3+[n(n-1)-2]=n^2-n+1$, B.

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →