The diagram below shows a river system consisting of 7 segments, marked P, Q,…
2025
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, and 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 P, Q, S, and T
- C.
Bridges on Q, R, T, and V
- D.
Bridges on P, Q, S, U, and V
Attempted by 16 students.
Show answer & explanation
Correct answer: C
Treat each land zone as a vertex of a graph and each river segment as a possible edge/bridge between the two zones separated by that segment. To connect 5 zones with the least number of bridges, we need a spanning tree, which has exactly 5 - 1 = 4 bridges.
From the diagram, bridges on Q, R, T and V connect the zones in a chain/tree:
Z1 --Q-- Z2 --R-- Z3 --T-- Z5, and Z3 --V-- Z4.
Thus all five zones are connected using exactly 4 bridges, which is the minimum possible. Hence the correct option is: bridges on Q, R, T and V.