Question

Eight cities A, B, C, D, E, F, G and H are connected with one-way roads \(R_1\), \(R_2\), \(R_3\), \(R_4\), \(R_5\) and \(R_6\) in the following manner:
- \(R_1\) leads from A to C via B;
- \(R_2\) leads from C to D and then via B to F;
- \(R_3\) leads from D to A and then via E to H;
- \(R_4\) leads from F to B via G;
- \(R_5\) leads from G to D; and
- \(R_6\) leads from F to H.

The minimum number of road segments that have to be blocked in order to make all traffic from B to D impossible is:

• A. 5
• B. 4
• C. 3
• D. 2

Hint:

Find how many road segments point directly into D, and how many separate routes from B reach those segments.

Answer 1

The Correct Option is D

This is really a minimum cut question: we need the fewest one-way segments that, once removed, leave no way at all to go from B to D.

First list every directed segment the six roads create: A-B, B-C (from \(R_1\)); C-D, D-B, B-F (from \(R_2\)); D-A, A-E, E-H (from \(R_3\)); F-G, G-B (from \(R_4\)); G-D (from \(R_5\)); F-H (from \(R_6\)).

Now count how many completely separate, segment-disjoint, routes exist from B to D. Starting at B, one route goes B \(\to\) C \(\to\) D. A second, sharing no segment with the first, goes B \(\to\) F \(\to\) G \(\to\) D. No third disjoint route exists, since B has only two outgoing segments, to C and to F, and both have already been used.

1. Can 1 segment block both routes? A single blocked segment can only belong to one of the two routes, since they share nothing, so the other route stays open. One block is never enough.
2. Do we need 3 or more? No. Once the two disjoint routes are each blocked once, there is no other segment feeding into D. D's only two incoming segments in the whole network are C-D and G-D, so removing exactly these two seals it off completely.

Since there are exactly 2 segment-disjoint routes from B to D, and each needs at least one block, while blocking one segment on each route is enough, the minimum number of segments to block is 2.

Let's summarize:

• D has only two incoming segments in the entire network: C-D and G-D.
• B can reach both of these entry points independently, giving two segment-disjoint routes.
• Blocking those two segments, one on each route, is both necessary and sufficient.

So the minimum number of road segments that must be blocked is 2.