Computer Sciences > GATE 2025 SET-2 > Graph Theory
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

Correct : c

The correct answer is Option C - Bridges on Q, R, T, and V.
This is a graph theory problem in disguise. The 5 zones Z1–Z5 are nodes, and each river segment that separates two zones is a potential edge. To connect all 5 zones with the minimum number of bridges, we need a spanning tree - which for 5 nodes requires exactly 4 edges (bridges).
Options A (3 bridges) and B/D (4–5 bridges) are either insufficient or redundant. Option C with bridges on Q, R, T, and V provides exactly 4 bridges that form a spanning tree connecting all 5 zones without any cycle. This is the minimum needed to ensure every zone is reachable from every other zone.
The key formula - to connect n zones with minimum bridges, you always need exactly n−1 bridges. With 5 zones, that''s 4 bridges. Option C is the only set of 4 bridges that successfully connects all zones.

Similar Questions

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time on Depth First Search of G? Assume that the graph is represen...
#14 MCQ
Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected co...
#18 MCQ
In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, a...
#91 MCQ

Related Topics

river system bridges GATE 2025 GATE CS 2025 Set-2 Q10 minimum bridges zones graph theory spanning tree connect zones minimum edges GATE computer science 2025 GATE previous year questions graph theory MCQ GATE river segments PQRSTUV zones

Unique Visitor Count

Total Unique Visitors

Loading......