ISRO CS 2023 Q.1: solution and answer

ISRO 2023 · CSQ.1 · 1 mark · MCQ

Find the minimum spanning distance and the corresponding number of edges for the following graph

ISRO CS 2023 question 1: Undirected weighted graph on vertices A, B, C, D, E. — Figure from the ISRO CS 2023 paper. It is part of the question.

(A)
10, 3
(B)
11, 4
(C)
15, 4
(D)
28, 7

Answer and solution

ANSWER

The minimum spanning tree has weight 11 and 4 edges, option (b).

Official answer: BSource: ISRO's revised and final answer key of 16 February 2024

The edges are $A B = 1$ , $D E = 2$ , $B E = 3$ , $B D = 4$ , $B C = 5$ , $C E = 6$ , $A C = 7$ . There are 5 vertices, so every spanning tree has $5 - 1 = 4$ edges.
Kruskal's rule: sort the edges by weight and add each one unless it closes a cycle.
Add $A B = 1$ , which joins A and B. Add $D E = 2$ , which joins D and E. Add $B E = 3$ , which joins the components ${A, B}$ and ${D, E}$ into ${A, B, D, E}$ .
Skip $B D = 4$ : B and D are already connected through E, so adding it would close the cycle $B$ - $D$ - $E$ .
Add $B C = 5$ : C is the only vertex not yet in the tree, so this edge cannot form a cycle. The tree now has 4 edges, so stop.
Total weight $= 1 + 2 + 3 + 5 = 11$ with $4$ edges, which is option (b). Option (a) has only 3 edges, too few to span 5 vertices. Options (c) and (d) are heavier: 28 is the sum of all 7 edges, and 15 with 4 edges cannot be minimal because a tree of weight 11 exists.

KEY IDEA

A minimum spanning tree of a connected graph with $n$ vertices always has $n - 1$ edges. Kruskal's algorithm builds one by taking the lightest edges that do not form a cycle.

WATCH OUT FOR

Adding $B D = 4$ after $B E = 3$ and $D E = 2$ closes a cycle. Another slip is quoting the sum of all edges (28 with 7 edges) as the answer.

From the ISRO CS 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 2 ISRO Graph algorithms questions, with notes