SwiftShip, a courier company, moves parcels from its origin hub A to its delivery hub G through a network of intermediate hubs B, C, D, E and F. Parcels can travel only along the one-way links listed below. Each link has a fixed travel time and a maximum number of parcels it can carry per day.
| Link | Travel time (hours) | Capacity (parcels/day) |
|---|---|---|
| A → B | 3 | 400 |
| A → C | 2 | 300 |
| A → D | 4 | 350 |
| B → C | 1 | 150 |
| B → E | 4 | 250 |
| C → E | 3 | 200 |
| C → F | 5 | 250 |
| D → C | 1 | 100 |
| D → F | 2 | 300 |
| E → F | 1 | 100 |
| E → G | 3 | 350 |
| F → G | 2 | 700 |
Every time a parcel passes through an intermediate hub it is held for sorting: 1 hour at B, 2 hours at C, 1 hour at D, 2 hours at E and 1 hour at F. There is no sorting delay at A or G. The delivery time of a route is the total travel time plus the sorting delays at the intermediate hubs on that route. A *route* is any sequence of links from A to G. Hubs can sort any number of parcels; only link capacities limit how many parcels can move per day, and parcels bound for G may be split across different routes.
| Link | Travel time (hours) | Capacity (parcels/day) |
|---|---|---|
| A → B | 3 | 400 |
| A → C | 2 | 300 |
| A → D | 4 | 350 |
| B → C | 1 | 150 |
| B → E | 4 | 250 |
| C → E | 3 | 200 |
| C → F | 5 | 250 |
| D → C | 1 | 100 |
| D → F | 2 | 300 |
| E → F | 1 | 100 |
| E → G | 3 | 350 |
| F → G | 2 | 700 |
Every time a parcel passes through an intermediate hub it is held for sorting: 1 hour at B, 2 hours at C, 1 hour at D, 2 hours at E and 1 hour at F. There is no sorting delay at A or G. The delivery time of a route is the total travel time plus the sorting delays at the intermediate hubs on that route. A *route* is any sequence of links from A to G. Hubs can sort any number of parcels; only link capacities limit how many parcels can move per day, and parcels bound for G may be split across different routes.
Question 1
Single correct option
What is the minimum possible delivery time (in hours) for a parcel from A to G?
- A. 10
- B. 11
- C. 12
- D. 13
Show answer and solution
Answer: (A) 10
All 12 routes with delivery times (travel + sorting):
| Route | Time (h) |
|---|---|
| A-D-F-G | 4+1+2+1+2 = 10 |
| A-C-E-G | 12 |
| A-C-F-G | 12 |
| A-B-E-G | 13 |
| A-C-E-F-G | 13 |
| A-B-E-F-G | 14 |
| A-B-C-E-G | 15 |
| A-B-C-F-G | 15 |
| A-B-C-E-F-G | 16 |
| A-D-C-E-G | 16 |
| A-D-C-F-G | 16 |
| A-D-C-E-F-G | 17 |
Fastest: A → D → F → G = 4 (A→D) + 1 (sort at D) + 2 (D→F) + 1 (sort at F) + 2 (F→G) = 10 hours.
Trap: Ignoring sorting delays makes A-C-E-G look fastest (2 + 3 + 3 = 8 h of travel), but it picks up 4 hours of sorting at C and E, giving 12 h.
| Route | Time (h) |
|---|---|
| A-D-F-G | 4+1+2+1+2 = 10 |
| A-C-E-G | 12 |
| A-C-F-G | 12 |
| A-B-E-G | 13 |
| A-C-E-F-G | 13 |
| A-B-E-F-G | 14 |
| A-B-C-E-G | 15 |
| A-B-C-F-G | 15 |
| A-B-C-E-F-G | 16 |
| A-D-C-E-G | 16 |
| A-D-C-F-G | 16 |
| A-D-C-E-F-G | 17 |
Fastest: A → D → F → G = 4 (A→D) + 1 (sort at D) + 2 (D→F) + 1 (sort at F) + 2 (F→G) = 10 hours.
Trap: Ignoring sorting delays makes A-C-E-G look fastest (2 + 3 + 3 = 8 h of travel), but it picks up 4 hours of sorting at C and E, giving 12 h.
Question 2
Numerical answer
How many distinct routes are there from A to G?
Show answer and solution
Answer: 12
Count routes by the hub reached from A.
- From F: 1 way (F→G).
- From E: E→G directly, or E→F→G = 2 ways.
- Ways from C: C→E (2 ways) + C→F (1 way) = 3.
- Ways from B: B→E (2) + B→C (3) = 5.
- Ways from D: D→F (1) + D→C (3) = 4.
- Ways from A: A→B (5) + A→C (3) + A→D (4) = 12.
Tip: Count backwards from the destination: the number of routes from a hub equals the sum of the numbers for the hubs it links to.
- From F: 1 way (F→G).
- From E: E→G directly, or E→F→G = 2 ways.
- Ways from C: C→E (2 ways) + C→F (1 way) = 3.
- Ways from B: B→E (2) + B→C (3) = 5.
- Ways from D: D→F (1) + D→C (3) = 4.
- Ways from A: A→B (5) + A→C (3) + A→D (4) = 12.
Tip: Count backwards from the destination: the number of routes from a hub equals the sum of the numbers for the hubs it links to.
Question 3
Single correct option
What is the maximum number of parcels that can be sent from A to G in a day?
- A. 950
- B. 1000
- C. 1050
- D. 850
Show answer and solution
Answer: (B) 1000
Upper bound (a cut). Every route must use one of the links B→E, C→E, C→F or D→F (they separate {A, B, C, D} from {E, F, G}). Their total capacity is 250 + 200 + 250 + 300 = 1000. So at most 1000 parcels/day.
Achieving 1000:
- A-B-E-G: 250
- A-B-C-E-G: 100
- A-B-C-F-G: 50
- A-C-E-F-G: 100
- A-C-F-G: 200
- A-D-F-G: 300
Link loads: A→B 400, A→C 300, A→D 300, B→C 150, B→E 250, C→E 200, C→F 250, D→F 300, E→F 100, E→G 350, F→G 650 – all within capacity. Total = 1000.
Trap: 1050 is the capacity into G (350 + 700) and out of A (400 + 300 + 350), but the middle layer is the real bottleneck.
Achieving 1000:
- A-B-E-G: 250
- A-B-C-E-G: 100
- A-B-C-F-G: 50
- A-C-E-F-G: 100
- A-C-F-G: 200
- A-D-F-G: 300
Link loads: A→B 400, A→C 300, A→D 300, B→C 150, B→E 250, C→E 200, C→F 250, D→F 300, E→F 100, E→G 350, F→G 650 – all within capacity. Total = 1000.
Trap: 1050 is the capacity into G (350 + 700) and out of A (400 + 300 + 350), but the middle layer is the real bottleneck.
Question 4
Single correct option
On a particular day, the link D → F is closed. What are the minimum delivery time from A to G and the maximum number of parcels that can be sent from A to G that day?
- A. 12 hours; 750 parcels
- B. 13 hours; 700 parcels
- C. 12 hours; 700 parcels
- D. 12 hours; 1000 parcels
Show answer and solution
Answer: (C) 12 hours; 700 parcels
Time. Removing D→F eliminates route A-D-F-G (10 h). The next fastest are A-C-E-G and A-C-F-G, both 12 hours.
Parcels. Without D→F, the links from {A, B, C, D} to {E, F, G} are B→E (250), C→E (200) and C→F (250), totalling 700 – an upper bound. It is achieved by: A-B-E-G 250, A-C-E-G 100, A-C-E-F-G 100, A-C-F-G 100, A-B-C-F-G 150 (E→G carries 350, E→F 100, C→E 200, C→F 250, B→C 150, A→C 300 – all within limits). Total = 700.
Answer: 12 hours; 700 parcels.
Why others fail: 13 h is the next route after the tied 12-h routes; 750 or 1000 ignore the tighter cut once D→F disappears.
Parcels. Without D→F, the links from {A, B, C, D} to {E, F, G} are B→E (250), C→E (200) and C→F (250), totalling 700 – an upper bound. It is achieved by: A-B-E-G 250, A-C-E-G 100, A-C-E-F-G 100, A-C-F-G 100, A-B-C-F-G 150 (E→G carries 350, E→F 100, C→E 200, C→F 250, B→C 150, A→C 300 – all within limits). Total = 700.
Answer: 12 hours; 700 parcels.
Why others fail: 13 h is the next route after the tied 12-h routes; 750 or 1000 ignore the tighter cut once D→F disappears.
Question 5
Numerical answer
If the capacity of link C → F alone is increased by 100 parcels per day (all other links unchanged), by how many parcels per day does the maximum A-to-G flow increase?
Show answer and solution
Answer: 50
Originally two different cuts both have capacity 1000:
- Cut 1: B→E + C→E + C→F + D→F = 250 + 200 + 250 + 300 = 1000
- Cut 2 (around {A, B, C, D, E}): E→G + E→F + C→F + D→F = 350 + 100 + 250 + 300 = 1000
C→F lies in both cuts, so raising it by 100 lifts both to 1100. But now a third cut binds: the links into G, E→G + F→G = 350 + 700 = 1050.
So the new maximum is min(1100, 1100, 1050, …) = 1050, which is achievable (e.g. keep the 1000-parcel plan and send an extra 50 via A-D-C-F-G, using the spare capacity on A→D, D→C, the upgraded C→F and F→G). Increase = 1050 − 1000 = 50.
Trap: Answering 100 assumes the upgraded link was the only bottleneck; always recheck every cut after a change.
- Cut 1: B→E + C→E + C→F + D→F = 250 + 200 + 250 + 300 = 1000
- Cut 2 (around {A, B, C, D, E}): E→G + E→F + C→F + D→F = 350 + 100 + 250 + 300 = 1000
C→F lies in both cuts, so raising it by 100 lifts both to 1100. But now a third cut binds: the links into G, E→G + F→G = 350 + 700 = 1050.
So the new maximum is min(1100, 1100, 1050, …) = 1050, which is achievable (e.g. keep the 1000-parcel plan and send an extra 50 via A-D-C-F-G, using the spare capacity on A→D, D→C, the upgraded C→F and F→G). Increase = 1050 − 1000 = 50.
Trap: Answering 100 assumes the upgraded link was the only bottleneck; always recheck every cut after a change.
Saved on this device. Sign in or create a free account to keep it on every device.