UPSC PYQPrelims 2017

Civil Services Examination · Question 77

Directions : Consider the given information (from Question 76 above) and answer the item that follows. In how many different ways can a train travel from F to A without passing through any station more than once?

  1. 1

  2. 2

  3. 3

  4. 4

Show answer & explanationShow explanation

Answer: (D) 4

Explanation

Given: From F, the only outgoing edge is F → D (since B → F is incoming only). Branch 1 via D → E: From D, moving to E gives three simple paths to A: (1) F → D → E → A, (2) F → D → E → C → A, and (3) F → D → E → G → C → A. Branch 2 via D → H: From D, moving to H gives one simple path to A: (4) F → D → H → G → C → A (moving G → B → F would repeat F). Result: There are 4 different ways to travel from F to A without repeating any station. Correct Answer: (d) 4

Diagram explaining the answer