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: 

• 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

Hint:

When solving minimum connectivity problems in GATE, model the problem as a graph and use Minimum Spanning Tree (MST) techniques like Kruskal’s or Prim’s algorithm to determine the optimal solution.

Answer 1

The Correct Option is C

To connect all five zones (Z1, Z2, Z3, Z4, and Z5) with the minimum number of bridges, we analyze the river system's segments.

The goal is to connect all the zones with the fewest number of bridges, which requires careful analysis of the river segments that divide the zones. We begin by identifying the critical segments in the river system that can be bridged to ensure access to each zone. In this case, segments \( Q, R, T, \) and \( V \) are the key points where bridges should be placed. These segments allow for the connection of all five zones while keeping the number of bridges to a minimum.

By strategically placing the bridges on these segments, we ensure that every zone is accessible, and the river system remains efficiently connected with the least amount of infrastructure.

Thus, the correct answer is (C).