The diagram below shows a river system consisting of 7 segments, marked P, Q, R, S, T, U, and V. It splits the land into 5 zones, marked Z1, Z2, Z3, Z4, Z5. We need to connect these zones using the least number of bridges. Out of the following options, which one is correct?
Note: The figure shown is representative.
A. Bridges on P, Q and T
B. Bridges on Q, R, T and V
C. Bridges on P, Q, S and U
D. Bridges on P, Q, S, U and V
GATE 2025 · General Aptitude · Maps · medium
Answer: 4 bridges are needed; the correct set is P, Q, S and U. Answer: C. Bridges on P, Q, S and U
Determine minimum number of bridges needed: With 5 zones, we need exactly 4 bridges. Options A (3 bridges) gives too few - one zone will be disconnected. Option D (5 bridges) has one redundant bridge (creates a cycle). Only B and C (both 4 bridges) can be the minimum spanning tree.
Check Option B: bridges on Q, R, T and V: The bridge arrangement in B connects some zones but based on the map topology, V is an outer segment and does not connect a new isolated zone; Z1 and Z5 may not all be bridged consistently. This option fails to connect all zones.
Check Option C: bridges on P, Q, S and U: Bridge P connects Z1 to Z2; Bridge Q connects Z1 to Z3; Bridge S connects Z2 to Z3 or Z2 to a further zone; Bridge U connects the remaining zone. Together they form a connected spanning tree over all 5 zones.