Consider a graph G = (V, E), where V = \v_1, v_2, , v_100\, E = \(v_i, v_j) 1 ≤ i < j ≤ 100\, and weight of the edge (v_i, v_j) is |i - j|. The weight of minimum spanning tree of G is _______.

GATE CSE 2020 Q59: MST weight of a complete graph with weights |i − j|

Algorithms
2 marks
NAT
No negative marking

Consider a graph $G = (V, E)$ , where $V = \{v_1, v_2, \ldots, v_{100}\}$ , $E = \{(v_i, v_j) \mid 1 \le i < j \le 100\}$ , and weight of the edge $(v_i, v_j)$ is $|i - j|$ . The weight of minimum spanning tree of $G$ is _______.

Try it: numerical answer: type the value

Your answer

Numerical answer. No negative marking.

Show answer and explanation

Answer: 99 (official GATE 2020 final answer key)

Concept used: Every edge has weight at least 1, and a spanning tree on 100 vertices has 99 edges.

First step: The path $v_1 - v_2 - \cdots - v_{100}$ uses only weight-1 edges and spans all vertices.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key

PracticePractise Algorithms questions →Full paperAll GATE CSE 2020 questions →

GATE CSE 2020 Q59: MST weight of a complete graph with weights |i − j|

Question

Full step-by-step solution

More Algorithms PYQs