Flow problems
Apply the maximum-flow minimum-cut theorem to directed networks; identify cuts, calculate cut capacity, and determine the maximum flow from source to sink.
Worked examples
Calculating a cut capacity
Straightforward
Problem
A directed network has source S, sink T, and intermediate vertices A and B: S→A (capacity 8), S→B (capacity 6), A→T (capacity 5), B→T (capacity 7), A→B (capacity 4). Find the capacity of the cut with S-side = {S, A} and T-side = {B, T}.
1
State the rule for which edges cross a cut.
Identify every edge that crosses from the S-side to the T-side. An edge counts only if it starts on the S-side and ends on the T-side. S-side = {S, A}, T-side = {B, T}.
2
Check each edge to see whether it crosses the cut.
S→A: both S-side — does not cross
S→B: S is S-side, B is T-side → crosses (capacity 6)
A→T: A is S-side, T is T-side → crosses (capacity 5)
A→B: A is S-side, B is T-side → crosses (capacity 4)
B→T: both T-side — does not cross
S→B: S is S-side, B is T-side → crosses (capacity 6)
A→T: A is S-side, T is T-side → crosses (capacity 5)
A→B: A is S-side, B is T-side → crosses (capacity 4)
B→T: both T-side — does not cross
3
Add the capacities of the crossing edges.
Cut capacity = .
Answer
The capacity of the cut is 15.
Finding the maximum flow using the minimum-cut theorem
Moderate
Problem
For the same network (S→A cap 8, S→B cap 6, A→T cap 5, B→T cap 7, A→B cap 4), find the maximum flow from S to T by evaluating all possible cuts.
1
List the meaningful cuts (there are 4 non-trivial ways to split {S, A, B, T} into two groups with S and T on opposite sides) and their capacities.
Cut 1: S-side = {S}, T-side = {A, B, T}. Edges crossing: S→A (8) + S→B (6) = 14
Cut 2: S-side = {S, A}, T-side = {B, T}. Edges crossing: S→B (6) + A→T (5) + A→B (4) = 15
Cut 3: S-side = {S, B}, T-side = {A, T}. Edges crossing: S→A (8) + B→T (7) = 15 (A→B goes from T-side to S-side — backward edge, not counted)
Cut 4: S-side = {S, A, B}, T-side = {T}. Edges crossing: A→T (5) + B→T (7) = 12
Cut 2: S-side = {S, A}, T-side = {B, T}. Edges crossing: S→B (6) + A→T (5) + A→B (4) = 15
Cut 3: S-side = {S, B}, T-side = {A, T}. Edges crossing: S→A (8) + B→T (7) = 15 (A→B goes from T-side to S-side — backward edge, not counted)
Cut 4: S-side = {S, A, B}, T-side = {T}. Edges crossing: A→T (5) + B→T (7) = 12
2
Identify the minimum cut capacity.
The cut capacities are: 14, 15, 15, 12. The minimum is 12 (Cut 4).
3
Apply the maximum-flow minimum-cut theorem.
4
Verify that a flow of 12 units is achievable.
The only way to get 12 units from S to T is if both A→T (5) and B→T (7) carry their full capacity simultaneously. Working backwards: A→T uses 5 (so A needs 5 incoming); B→T uses 7 (so B needs 7 incoming). Try S→A = 8, S→B = 4, A→B = 3; then B = 4 + 3 = 7 ✓, A→T = 5 ✓. Total outflow = ✓.
Answer
The maximum flow from S to T is 12 units.
Interpreting the minimum cut in context
Challenging
Problem
A water supply system has source S (reservoir), sink T (town), and two pump stations A and B: S→A (capacity 10), S→B (capacity 7), A→T (capacity 8), B→T (capacity 6), A→B (capacity 3). Find the maximum flow the system can deliver to the town.
1
Evaluate the four possible cuts.
{S}: S→A (10) + S→B (7) = 17
{S, A}: S→B (7) + A→T (8) + A→B (3) = 18
{S, B}: S→A (10) + B→T (6) = 16 (A→B is backward here — not counted)
{S, A, B}: A→T (8) + B→T (6) = 14
{S, A}: S→B (7) + A→T (8) + A→B (3) = 18
{S, B}: S→A (10) + B→T (6) = 16 (A→B is backward here — not counted)
{S, A, B}: A→T (8) + B→T (6) = 14
2
Identify the minimum cut capacity.
Minimum cut capacity = 14 (cut through {S, A, B}).
3
State the maximum flow and explain the bottleneck.
Maximum flow = 14 units per unit time. The bottleneck is the total capacity of the pipes leading into the town — A→T (8) and B→T (6) — regardless of how much the earlier pipes can carry.
Answer
The maximum flow the system can deliver to the town is 14 units per unit time.
Practise
Q1·Straightforward
A cut divides the vertices of a network into two sets: those containing the source (S-side) and those containing the sink (T-side). A cut passes through three edges with capacities 4, 6 and 3. What is the capacity of this cut?
Explanation
The capacity of a cut = sum of capacities of edges crossing from S-side to T-side:
This cut has a capacity of **13 units**.
This cut has a capacity of **13 units**.
Q2·Straightforward
The maximum-flow minimum-cut theorem states that:
Explanation
The **maximum-flow minimum-cut theorem** states that the **maximum flow** from source to sink equals the **capacity of the minimum cut** — the cut with the smallest total capacity. The minimum cut acts as the network's bottleneck.
Q3·Straightforward
A simple directed network has source S, one intermediate vertex A and sink T. The edges are S→A (capacity 5) and A→T (capacity 9). What is the maximum flow from S to T?
Explanation
There is only one path: S → A → T. The flow along this path is limited by the minimum edge capacity:
Maximum flow = **5 units**.
Maximum flow = **5 units**.
Q4·Moderate
A directed network has source S, sink T and one intermediate vertex A. Edges: S→A (capacity 7), S→T (capacity 3), A→T (capacity 5).
There are two paths from S to T:
- Path 1: S→T directly (capacity 3)
- Path 2: S→A→T (the bottleneck is the smaller of 7 and 5)
What is the maximum flow from S to T?
There are two paths from S to T:
- Path 1: S→T directly (capacity 3)
- Path 2: S→A→T (the bottleneck is the smaller of 7 and 5)
What is the maximum flow from S to T?
Explanation
Path 1 (S→T directly): carries 3 units.
Path 2 (S→A→T): limited by units.
The paths share no intermediate edges, so their flows add:
Path 2 (S→A→T): limited by units.
The paths share no intermediate edges, so their flows add:
Q5·Moderate
A directed network has source S, sink T, and two intermediate vertices A and B. The edges are:
- S→A (capacity 6), S→B (capacity 4)
- A→T (capacity 5), B→T (capacity 7), A→B (capacity 3)
A cut is drawn so that the S-side contains {S} and the T-side contains {A, B, T}. Calculate the capacity of this cut.
- S→A (capacity 6), S→B (capacity 4)
- A→T (capacity 5), B→T (capacity 7), A→B (capacity 3)
A cut is drawn so that the S-side contains {S} and the T-side contains {A, B, T}. Calculate the capacity of this cut.
Explanation
The cut separates S from the rest. Edges crossing from {S} to {A, B, T}:
- S→A: capacity 6 ✓
- S→B: capacity 4 ✓
Edge A→B stays entirely on the T-side — it does not cross this cut.
Cut capacity = **10 units**.
- S→A: capacity 6 ✓
- S→B: capacity 4 ✓
Edge A→B stays entirely on the T-side — it does not cross this cut.
Cut capacity = **10 units**.
Q6·Moderate
Using the same network (S→A cap 6, S→B cap 4, A→T cap 5, B→T cap 7, A→B cap 3):
A second cut is drawn so that the S-side = {S, A, B} and the T-side = {T}. Calculate the capacity of this cut.
A second cut is drawn so that the S-side = {S, A, B} and the T-side = {T}. Calculate the capacity of this cut.
Explanation
Edges crossing from {S, A, B} to {T}:
- A→T: capacity 5 ✓
- B→T: capacity 7 ✓
Edges S→A, S→B and A→B all stay within the S-side and are not counted.
Cut capacity = **12 units**.
- A→T: capacity 5 ✓
- B→T: capacity 7 ✓
Edges S→A, S→B and A→B all stay within the S-side and are not counted.
Cut capacity = **12 units**.
Q7·Moderate
For the network (S→A cap 6, S→B cap 4, A→T cap 5, B→T cap 7, A→B cap 3), two of the possible cuts have capacities 10 and 12 respectively. A third cut (S-side = {S, A}, T-side = {B, T}) passes through edges S→B (4), A→T (5) and A→B (3). What is the capacity of this third cut?
Explanation
Edges from {S, A} to {B, T}:
- S→B: capacity 4 (S is S-side, B is T-side ✓)
- A→T: capacity 5 (A is S-side, T is T-side ✓)
- A→B: capacity 3 (A is S-side, B is T-side ✓)
Cut capacity = **12 units**.
- S→B: capacity 4 (S is S-side, B is T-side ✓)
- A→T: capacity 5 (A is S-side, T is T-side ✓)
- A→B: capacity 3 (A is S-side, B is T-side ✓)
Cut capacity = **12 units**.
Q8·Moderate
For the network (S→A cap 6, S→B cap 4, A→T cap 5, B→T cap 7, A→B cap 3), the three cut capacities are 10, 12 and 12. What is the maximum flow from S to T?
Explanation
The three cuts have capacities 10, 12 and 12. The minimum cut capacity is 10.
By the **maximum-flow minimum-cut theorem**:
By the **maximum-flow minimum-cut theorem**:
Q9·Challenging
A directed pipeline network has source S, sink T and intermediate vertices P and Q:
- S→P (capacity 8), S→Q (capacity 5)
- P→T (capacity 6), Q→T (capacity 4), P→Q (capacity 3)
Consider the cut with S-side = {S, P} and T-side = {Q, T}. Calculate its capacity.
- S→P (capacity 8), S→Q (capacity 5)
- P→T (capacity 6), Q→T (capacity 4), P→Q (capacity 3)
Consider the cut with S-side = {S, P} and T-side = {Q, T}. Calculate its capacity.
Explanation
Edges from {S, P} to {Q, T}:
- S→Q: capacity 5 (S is S-side, Q is T-side ✓)
- P→T: capacity 6 (P is S-side, T is T-side ✓)
- P→Q: capacity 3 (P is S-side, Q is T-side ✓)
Edge S→P stays within the S-side. Edge Q→T stays within the T-side.
Cut capacity = **14 units**.
- S→Q: capacity 5 (S is S-side, Q is T-side ✓)
- P→T: capacity 6 (P is S-side, T is T-side ✓)
- P→Q: capacity 3 (P is S-side, Q is T-side ✓)
Edge S→P stays within the S-side. Edge Q→T stays within the T-side.
Cut capacity = **14 units**.
Q10·Challenging
Using the same pipeline network (S→P cap 8, S→Q cap 5, P→T cap 6, Q→T cap 4, P→Q cap 3):
You have found these cut capacities so far:
- Cut {S}: capacity 13
- Cut {S, P}: capacity 14
Now find the capacity of the cut with S-side = {S, Q} and T-side = {P, T}.
You have found these cut capacities so far:
- Cut {S}: capacity 13
- Cut {S, P}: capacity 14
Now find the capacity of the cut with S-side = {S, Q} and T-side = {P, T}.
Explanation
S-side = {S, Q}, T-side = {P, T}. Check each edge:
- S→P: S is S-side, P is T-side → crosses ✓ (8)
- S→Q: both S-side → does not cross
- Q→T: Q is S-side, T is T-side → crosses ✓ (4)
- P→Q: P is T-side, Q is S-side → **backward edge**, not counted
- P→T: both T-side → does not cross
Cut capacity = **12 units**.
- S→P: S is S-side, P is T-side → crosses ✓ (8)
- S→Q: both S-side → does not cross
- Q→T: Q is S-side, T is T-side → crosses ✓ (4)
- P→Q: P is T-side, Q is S-side → **backward edge**, not counted
- P→T: both T-side → does not cross
Cut capacity = **12 units**.
Q11·Challenging
For the pipeline network (S→P cap 8, S→Q cap 5, P→T cap 6, Q→T cap 4, P→Q cap 3), the cuts evaluated so far are:
- Cut {S}: 13
- Cut {S, P}: 14
- Cut {S, Q}: 12
- Cut {S, P, Q}: edges P→T (6) and Q→T (4) = 10
Using the maximum-flow minimum-cut theorem, what is the maximum flow from S to T?
- Cut {S}: 13
- Cut {S, P}: 14
- Cut {S, Q}: 12
- Cut {S, P, Q}: edges P→T (6) and Q→T (4) = 10
Using the maximum-flow minimum-cut theorem, what is the maximum flow from S to T?
Explanation
Cut capacities: 13, 14, 12 and 10.
The minimum is **10** (the cut separating {S, P, Q} from {T}).
By the maximum-flow minimum-cut theorem:
This makes sense — the total capacity entering T is , which is the absolute ceiling for flow into T.
The minimum is **10** (the cut separating {S, P, Q} from {T}).
By the maximum-flow minimum-cut theorem:
This makes sense — the total capacity entering T is , which is the absolute ceiling for flow into T.
Q12·Challenging
A directed network has source S, sink T and intermediate vertices A, B and C:
- S→A (capacity 10), S→B (capacity 8)
- A→C (capacity 6), A→B (capacity 4)
- B→T (capacity 9), C→T (capacity 7)
The cut with S-side = {S, A, B} and T-side = {C, T} passes through edges A→C and B→T. Calculate the capacity of this cut.
- S→A (capacity 10), S→B (capacity 8)
- A→C (capacity 6), A→B (capacity 4)
- B→T (capacity 9), C→T (capacity 7)
The cut with S-side = {S, A, B} and T-side = {C, T} passes through edges A→C and B→T. Calculate the capacity of this cut.
Explanation
Edges from {S, A, B} to {C, T}:
- A→C: capacity 6 (A is S-side, C is T-side ✓)
- B→T: capacity 9 (B is S-side, T is T-side ✓)
Edges S→A, S→B and A→B all stay within the S-side. Edge C→T stays within the T-side.
Cut capacity = **15 units**.
This is in fact the **minimum cut** for this network (you can verify the other cuts all give values ≥ 15), so the maximum flow = 15 units.
- A→C: capacity 6 (A is S-side, C is T-side ✓)
- B→T: capacity 9 (B is S-side, T is T-side ✓)
Edges S→A, S→B and A→B all stay within the S-side. Edge C→T stays within the T-side.
Cut capacity = **15 units**.
This is in fact the **minimum cut** for this network (you can verify the other cuts all give values ≥ 15), so the maximum flow = 15 units.
Open Math
Flow problems
Networks · MS-N2
Name:
Date:
Q1Straightforward
A cut divides the vertices of a network into two sets: those containing the source (S-side) and those containing the sink (T-side). A cut passes through three edges with capacities 4, 6 and 3. What is the capacity of this cut?
Q2Straightforward
The maximum-flow minimum-cut theorem states that:
- A.The maximum flow equals the number of edges in the network
- B.The maximum flow from source to sink equals the capacity of the minimum cut
- C.The minimum cut passes through the source vertex
- D.The maximum flow equals the sum of all edge capacities
Q3Straightforward
A simple directed network has source S, one intermediate vertex A and sink T. The edges are S→A (capacity 5) and A→T (capacity 9). What is the maximum flow from S to T?
Q4Moderate
A directed network has source S, sink T and one intermediate vertex A. Edges: S→A (capacity 7), S→T (capacity 3), A→T (capacity 5).
There are two paths from S to T:
- Path 1: S→T directly (capacity 3)
- Path 2: S→A→T (the bottleneck is the smaller of 7 and 5)
What is the maximum flow from S to T?
There are two paths from S to T:
- Path 1: S→T directly (capacity 3)
- Path 2: S→A→T (the bottleneck is the smaller of 7 and 5)
What is the maximum flow from S to T?
Q5Moderate
A directed network has source S, sink T, and two intermediate vertices A and B. The edges are:
- S→A (capacity 6), S→B (capacity 4)
- A→T (capacity 5), B→T (capacity 7), A→B (capacity 3)
A cut is drawn so that the S-side contains {S} and the T-side contains {A, B, T}. Calculate the capacity of this cut.
- S→A (capacity 6), S→B (capacity 4)
- A→T (capacity 5), B→T (capacity 7), A→B (capacity 3)
A cut is drawn so that the S-side contains {S} and the T-side contains {A, B, T}. Calculate the capacity of this cut.
Q6Moderate
Using the same network (S→A cap 6, S→B cap 4, A→T cap 5, B→T cap 7, A→B cap 3):
A second cut is drawn so that the S-side = {S, A, B} and the T-side = {T}. Calculate the capacity of this cut.
A second cut is drawn so that the S-side = {S, A, B} and the T-side = {T}. Calculate the capacity of this cut.
Q7Moderate
For the network (S→A cap 6, S→B cap 4, A→T cap 5, B→T cap 7, A→B cap 3), two of the possible cuts have capacities 10 and 12 respectively. A third cut (S-side = {S, A}, T-side = {B, T}) passes through edges S→B (4), A→T (5) and A→B (3). What is the capacity of this third cut?
Q8Moderate
For the network (S→A cap 6, S→B cap 4, A→T cap 5, B→T cap 7, A→B cap 3), the three cut capacities are 10, 12 and 12. What is the maximum flow from S to T?
Q9Challenging
A directed pipeline network has source S, sink T and intermediate vertices P and Q:
- S→P (capacity 8), S→Q (capacity 5)
- P→T (capacity 6), Q→T (capacity 4), P→Q (capacity 3)
Consider the cut with S-side = {S, P} and T-side = {Q, T}. Calculate its capacity.
- S→P (capacity 8), S→Q (capacity 5)
- P→T (capacity 6), Q→T (capacity 4), P→Q (capacity 3)
Consider the cut with S-side = {S, P} and T-side = {Q, T}. Calculate its capacity.
Q10Challenging
Using the same pipeline network (S→P cap 8, S→Q cap 5, P→T cap 6, Q→T cap 4, P→Q cap 3):
You have found these cut capacities so far:
- Cut {S}: capacity 13
- Cut {S, P}: capacity 14
Now find the capacity of the cut with S-side = {S, Q} and T-side = {P, T}.
You have found these cut capacities so far:
- Cut {S}: capacity 13
- Cut {S, P}: capacity 14
Now find the capacity of the cut with S-side = {S, Q} and T-side = {P, T}.
Q11Challenging
For the pipeline network (S→P cap 8, S→Q cap 5, P→T cap 6, Q→T cap 4, P→Q cap 3), the cuts evaluated so far are:
- Cut {S}: 13
- Cut {S, P}: 14
- Cut {S, Q}: 12
- Cut {S, P, Q}: edges P→T (6) and Q→T (4) = 10
Using the maximum-flow minimum-cut theorem, what is the maximum flow from S to T?
- Cut {S}: 13
- Cut {S, P}: 14
- Cut {S, Q}: 12
- Cut {S, P, Q}: edges P→T (6) and Q→T (4) = 10
Using the maximum-flow minimum-cut theorem, what is the maximum flow from S to T?
Q12Challenging
A directed network has source S, sink T and intermediate vertices A, B and C:
- S→A (capacity 10), S→B (capacity 8)
- A→C (capacity 6), A→B (capacity 4)
- B→T (capacity 9), C→T (capacity 7)
The cut with S-side = {S, A, B} and T-side = {C, T} passes through edges A→C and B→T. Calculate the capacity of this cut.
- S→A (capacity 10), S→B (capacity 8)
- A→C (capacity 6), A→B (capacity 4)
- B→T (capacity 9), C→T (capacity 7)
The cut with S-side = {S, A, B} and T-side = {C, T} passes through edges A→C and B→T. Calculate the capacity of this cut.
Worked solutions and answers at openmath.au/year-12/standard-2/network-flow/flow-problems