GATE CSE 2025 | Set 2 | GA | Question: 10

Question

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$

Comments

minimum bridges is 3, any way you choose

 

Answer 1

Option C CORRECT

Comments

Let's check all options one by one:
Option A:
We are not connecting zone Z4.
Option B:
We are not connecting zone Z4.
Option C:
We are connecting all Zones using 4 Bridges.
Option D:
We are connecting all zones using 5 Bridges.

Question is asking about Least number of bridges (Which is 4) so correct answer is option C.

Answer 2

Similar to graph coloring problem .

Each River is divided into segments . Where each intersection of the rivers act as start and end point of the segment.

Consider Option A and B , here we are not building bridge across U or V so as to connect zone Z4.

Option C , here we do connect Z4 by bridge across Z4 to Z3 via V river and require minimum number of bridges compared to Option D. Hence , the answer is Option C.

Answer 3

Model the problem as a graph problem where the zones are vertices and the bridges are edges.

Clearly, they are asking for minimum number of edges to form a connected subgraph. That would be a spanning tree, and the spanning tree will always have n-1 edges. So the answer cannot be A or D.

Between B and C, it is easy to observe that only C is a spanning tree.