The GATE Grind

GATE 2012 CS (CS1) – Question 39

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

A graph G has edge weights greater than one. G′ squares every edge weight. T,T′ are minimum spanning trees with weights t,t′. Which is true?

  1. T′=T and t′=t²
  2. T′=T and t′<t²
  3. T′≠T and t′=t²
  4. None of the above

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: MTA

Explanation

The official key awards marks to all. Squaring positive weights preserves their ordering, so the family of minimum spanning trees is preserved, but independently chosen trees need not be identical if the MST is nonunique. For a fixed tree with at least two positive edges, Σwᵢ²<(Σwᵢ)², explaining intended B. A one-edge tree instead has equality. These unstated qualifications prevent a universally valid single choice.

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

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