GATE CS 2025 Set 2 — Question 10
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MCQ+2 / -0.67MediumTrees & Spanning TreesGraph Theory (Math)Engineering MathematicsAnalytical AptitudeGeneral Aptitude
Engineering Mathematics → Analytical Aptitude → Trees & Spanning Trees
Last updated
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.
Correct answer
(C) Bridges on Q, R, T, and V
Solution
This problem can be modeled as finding a spanning tree in a graph where the zones ( to ) are nodes and the river segments () represent potential edges (bridges) connecting adjacent zones.1. Identify Adjacencies (Edges):
Based on the topology of the diagram:
Connect all 5 nodes () using the least number of bridges. For a graph with nodes, the minimum number of edges required to connect them is (a spanning tree).3. Evaluate Options:
Based on the topology of the diagram:
- P connects and .
- S connects and .
- Q connects and (separating the left zone from the top-right zone).
- R connects and .
- T connects and .
- V connects and .
- U connects and .
Connect all 5 nodes () using the least number of bridges. For a graph with nodes, the minimum number of edges required to connect them is (a spanning tree).3. Evaluate Options:
- (A) Bridges on P, Q, and T:
- Edges: .
- Connected components: . Node is isolated.
- Incorrect.
- (B) Bridges on P, Q, S, and T:
- Edges: .
- This creates a cycle . Node is still isolated.
- Incorrect.
- (C) Bridges on Q, R, T, and V:
- Edges: .
- All edges connect to node (forming a star-like structure centered at ).
- Connectivity: . All nodes are connected.
- Number of bridges: 4 (minimal).
- Correct.
- (D) Bridges on P, Q, S, U, and V:
- Number of bridges: 5. Since 4 is sufficient, 5 is not the least number.
- Incorrect.
Continue learning with Success Tracker
A step still unclear? Work through it with support
Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.
AI-powered practice· Unlimited practice on eligible plans
- PYQs with solutions
- Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
- Practice that adapts
- Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
- AI doubt support
- Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.
Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.
This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.
More questions on Analytical Aptitude
2026 Set 1 Q1The antonym of the word protagonist is ________.2026 Set 2 Q1Expedite, Hasten, Hurry, __________ Fill the blank by choosing a word with a meaning similar to…2026 Set 1 Q2The figure shows two 4-tile patterns. [figure] Either one or both of the patterns can be used any…2026 Set 2 Q2A black square PQRS has been cut into two parts. One part of it is shown in Panel I. Which one of…2026 Set 1 Q3Consider a knock-out women’s badminton singles tournament where there are no ties. The loser in…