Figures (i) and (ii) represent intercity highway systems. The black dots represent
cities and the line segments between them represent intercity highways.
A salesperson needs to make a trip. She needs to start from a city, visit each of the
remaining cities exactly once, and finally return to the same city from which she
started.
Which one of the following options is then true?
Figures (i) and (ii) represent intercity highway systems. The black dots represent
cities and the line segments between them represent intercity highways.
A salesperson needs to make a trip. She needs to start from a city, visit each of the
remaining cities exactly once, and finally return to the same city from which she
started.
Which one of the following options is then true?
Show Hint
- Such a trip is possible for (i), but not for (ii).
- Such a trip is possible for (ii), but not for (i).
- Such a trip is possible for both (i) and (ii).
- Such a trip is possible neither for (i) nor for (ii).
The Correct Option is A
Solution and Explanation
Step 1: The salesperson's trip -- start at a city, visit every other city exactly once, and return to the start -- is exactly a Hamiltonian circuit on the highway graph.
Step 2: A necessary condition for a graph to contain a Hamiltonian circuit is that every vertex must have degree at least 2, because the circuit must enter and leave each city using two distinct edges.
Step 3: In figure (i), every city (vertex) has at least two highways (edges) connecting it to other cities, and the network is arranged so that a closed tour visiting every city exactly once can be traced -- so a Hamiltonian circuit exists for (i).
Step 4: In figure (ii), at least one city is connected to the rest of the network by only a single highway (a degree-1 vertex), so that city can be entered but not exited without reusing that same highway. Hence no Hamiltonian circuit exists for (ii).
Therefore the round trip is possible for (i) but not for (ii).
Final Answer: \(\boxed{A}\)
Top GATE CS General Aptitude Questions
- A person sold two different items at the same price. He made 10% profit in one item and 10% loss in the other item. In, selling the person made a total of
- The value of x in given series is
6, 9, 14, x, 30, 41 - log \([\frac{x+y}{2}]=\frac{1}{2}\) (log x+log y) the value of \(\frac{x}{y}+\frac{y}{x}\) is
- A cube is to be cut into 8 pieces of equal size and shape Here each cut should be straight and it should not stop till it reaches the other end of the cube The minimum number of such cuts required?
- Increasing order of the intensity
Walk → Jog → Sprint
Bothered →? Daunted
Top GATE CS Logical Reasoning Questions
The figure shows two 4-tile patterns.
Either one or both of the patterns can be used any number of times and in any
orientation to construct a new pattern. Which one of the options below cannot be
constructed by using only these two 4-tile patterns assuming there are no overlaps
among them?
A black square PQRS has been cut into two parts. One part of it is shown in
Panel I. Which one of the shapes in Panel II is the other part?
Water : P :: Food : Q
Choose the P and Q combination from the options below to form a meaningful
analogy.Two tiles are missing in Panel I. Which one of the options in Panel II is the
appropriate choice for the missing tiles?
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?