Solutions — Network Flow Problems — Grade 12 General Maths

Fluency S→A (cap 6), S→B (cap 4), A→T (cap 5), B→T (cap 7). Maximum flow.

Path S→A→T: limited by min(6,5) = 5. Send 5 units.
Path S→B→T: limited by min(4,7) = 4. Send 4 units.
No more paths.
Maximum flow = 5 + 4 = 9 units

Verify with cut {S→A, S→B}: capacity = 6+4 = 10. But max flow = 9 because A→T has capacity 5 (bottleneck on S→A path). The minimum cut is {A→T, S→B} = 5+4 = 9. ✓

Fluency Flow in to C: AC=3, BC=5. Find flow out on C→D.

Flow conservation: flow in = flow out at node C.
Flow in = 3 + 5 = 8
Flow on C→D = 8 units

Fluency Cut 1: {S→A=8, S→B=5} = 13. Cut 2: {A→T=6, B→T=9} = 15.

Both cuts are valid upper bounds on the maximum flow.
Cut 1 capacity = 8+5 = 13
Cut 2 capacity = 6+9 = 15

Cut 1 gives a better (tighter) upper bound. The minimum cut gives the actual maximum flow. Since Cut 1 = 13 < 15 = Cut 2, the maximum flow is at most 13 (and may equal 13 if Cut 1 is the minimum cut).

Fluency Verify feasibility: S→A=4(cap5), S→B=3(cap3), A→C=2(cap4), A→T=2(cap3), B→C=3(cap3), C→T=5(cap6).

Capacity check:
S→A: 4 ≤ 5 ✓ S→B: 3 ≤ 3 ✓ A→C: 2 ≤ 4 ✓ A→T: 2 ≤ 3 ✓ B→C: 3 ≤ 3 ✓ C→T: 5 ≤ 6 ✓

Flow conservation:
Node A: in=4, out=2+2=4 ✓
Node B: in=3, out=3 ✓
Node C: in=2+3=5, out=5 ✓

This is a valid feasible flow. Total flow = 4+3 = 7 units (leaving S) = 2+5 = 7 units (entering T) ✓

Understanding Water network: S→A=10, S→B=8, A→C=6, A→B=3, B→D=9, C→T=7, D→T=8.

(a) Augmenting paths:
Path S→A→C→T: flow = min(10,6,7) = 6. Remaining: S→A=4, A→C=0, C→T=1.
Path S→B→D→T: flow = min(8,9,8) = 8. Remaining: S→B=0, B→D=1, D→T=0.
Path S→A→B→D→T: flow = min(4,3,1,0)=0 (D→T exhausted).
No more useful augmenting paths with remaining capacity.
Maximum flow = 6 + 8 = 14 units

(b) Cut verification:
Consider cut {C→T, D→T} (S-side: S,A,B,C,D; T-side: T):
Capacity = 7 + 8 = 15 (not minimum).
Consider cut {A→C, S→B} (S-side: S,A; T-side: B,C,D,T):
S→B goes S-side to T-side: cap 8. A→C goes S-side to T-side: cap 6. Total = 14. ✓
Minimum cut = {A→C=6, S→B=8} = 14 = maximum flow ✓

Understanding Traffic network: S→A=12, S→B=10, A→C=8, A→D=6, B→C=5, B→D=9, C→T=10, D→T=12.

Augmenting paths:
S→A→C→T: min(12,8,10)=8. Remaining: S→A=4, A→C=0, C→T=2.
S→A→D→T: min(4,6,12)=4. Remaining: S→A=0, A→D=2, D→T=8.
S→B→D→T: min(10,9,8)=8. Remaining: S→B=2, B→D=1, D→T=0.
S→B→C→T: min(2,5,2)=2. Remaining: S→B=0, B→C=3, C→T=0.
No more augmenting paths.

Maximum flow = 8+4+8+2 = 22 vehicles/minute
Verify: cut {C→T=10, D→T=12} = 22 ✓

Understanding Why a single pipe with capacity 5 limits total flow to 5.

A single pipe (edge) with capacity 5, placed anywhere between S and T, forms a cut by itself. Every unit of flow from S to T must pass through this pipe (because removing it disconnects S from T).

By the max-flow min-cut theorem, the maximum flow equals the minimum cut capacity. A cut consisting of just this single edge has capacity 5. Therefore, no more than 5 units can flow through the network, regardless of the capacity of any other pipe.

This is the “bottleneck” principle — the narrowest point limits the entire system.

Understanding Max flow = 15. Min cut = {cap 8, cap 7} = 15. How to increase flow to 20?

To increase maximum flow from 15 to 20, the minimum cut must be increased to ≥ 20. This requires upgrading edges in the minimum cut.

Current min cut: 8 + 7 = 15. Need 5 more units of capacity.

Options:
• Upgrade the capacity-8 edge by 5 (to 13): new cut = 13+7 = 20 ✓
• Upgrade the capacity-7 edge by 5 (to 12): new cut = 8+12 = 20 ✓
• Upgrade both partially (e.g. +3 and +2): also works

Cheapest strategy: upgrade whichever edge in the minimum cut costs less per unit of capacity increase. Upgrading edges outside the minimum cut has no effect on maximum flow.

Problem Solving Data network: S→A=20, S→B=15, A→C=12, A→D=10, B→C=8, B→D=14, C→T=18, D→T=16.

(a) Augmenting paths:
S→A→C→T: min(20,12,18) = 12. Remaining: S→A=8, A→C=0, C→T=6.
S→A→D→T: min(8,10,16) = 8. Remaining: S→A=0, A→D=2, D→T=8.
S→B→D→T: min(15,14,8) = 8. Remaining: S→B=7, B→D=6, D→T=0.
S→B→C→T: min(7,8,6) = 6. Remaining: S→B=1, B→C=2, C→T=0.
No more augmenting paths (C→T and D→T both saturated).

Maximum flow = 12+8+8+6 = 34 MB/s

(b) Minimum cut:
Cut {C→T=18, D→T=16}: capacity = 18+16 = 34 ✓
The bottleneck edges are C→T (18 MB/s) and D→T (16 MB/s). These are the links into the sink that limit total throughput.

Problem Solving Max flow = 24. Cuts: Cut 1 = 24, Cut 2 = 28, Cut 3 = 30.

(a) Minimum cut: Cut 1 (total capacity = 24, which equals the maximum flow). Cuts 2 and 3 have higher capacities, so they are not minimum cuts.

(b) Can the network carry 25 units?
No. The max-flow min-cut theorem states the maximum flow equals the minimum cut capacity = 24. It is impossible to send 25 units through this network without increasing capacity in the minimum cut (Cut 1).

(c) Upgrading an edge in Cut 1 from capacity 7 to 12 (adding 5 units):
New Cut 1 capacity = 9+8+12 = 29.
However, the maximum flow won’t necessarily increase to 29 — it increases to the new minimum cut, which may now be Cut 2 (capacity 28) if that becomes binding.
New maximum flow = min(29, 28, 30) = 28 units. The flow increases by 4 (from 24 to 28), with Cut 2 now becoming the bottleneck.