← Networks and Decision Mathematics › Network Flow Problems
Network Flow Problems
Key Terms
- A flow network is a directed graph with a source (S) and sink (T)
- Each edge has a capacity (maximum flow it can carry)
- A feasible flow: flow on each edge ≤ capacity; flow conservation at every interior node
- Flow conservation
- flow in = flow out at every non-source, non-sink vertex
- A cut is a set of edges whose removal disconnects S from T
- Capacity of a cut
- = sum of capacities of edges in the cut (going from S-side to T-side only)
- Max-flow min-cut theorem
- maximum flow = minimum cut capacity
Flow conservation (at interior nodes):
Σ(flow in) = Σ(flow out)
Maximum flow = Minimum cut:
To find max flow: find all cuts; identify the one with minimum total capacity
Identifying the minimum cut:
A cut separates the graph into two sets: S-side (contains source) and T-side (contains sink).
Only count edges going FROM S-side TO T-side.
Σ(flow in) = Σ(flow out)
Maximum flow = Minimum cut:
To find max flow: find all cuts; identify the one with minimum total capacity
Identifying the minimum cut:
A cut separates the graph into two sets: S-side (contains source) and T-side (contains sink).
Only count edges going FROM S-side TO T-side.
Worked Example: Flow network: S→A (cap 5), S→B (cap 4), A→T (cap 3), A→B (cap 2), B→T (cap 6).
Find the maximum flow:
Path S→A→T: flow = min(5,3) = 3. Remaining: S→A cap 2, A→T cap 0.
Path S→B→T: flow = min(4,6) = 4. Remaining: S→B cap 0, B→T cap 2.
Path S→A→B→T: flow = min(2,2,2) = 2. Total so far: 9.
No more augmenting paths. Maximum flow = 9.
Minimum cut check: Cut {S→A, S→B}: capacity = 5+4=9. ✓ (equals max flow)
Find the maximum flow:
Path S→A→T: flow = min(5,3) = 3. Remaining: S→A cap 2, A→T cap 0.
Path S→B→T: flow = min(4,6) = 4. Remaining: S→B cap 0, B→T cap 2.
Path S→A→B→T: flow = min(2,2,2) = 2. Total so far: 9.
No more augmenting paths. Maximum flow = 9.
Minimum cut check: Cut {S→A, S→B}: capacity = 5+4=9. ✓ (equals max flow)
Hot Tip: When identifying cuts, only count edges going from the S-side to the T-side. Backward edges (T-side to S-side) are not part of the cut capacity — this is a common mistake.
What Is a Flow Network?
A flow network models situations where something — water, traffic, data, goods — moves from a source (S) to a sink (T) through a network of pipes/roads/channels, each with a maximum capacity.
Feasible Flows
A feasible flow assigns a flow value to each edge such that:
- Flow ≤ capacity on every edge
- Flow conservation: at every interior node (not S or T), the total flow in equals the total flow out
Finding Maximum Flow
The maximum flow can be found by:
- Finding any path from S to T with remaining capacity (an augmenting path)
- Sending as much flow as possible along that path (limited by the minimum capacity edge)
- Repeating until no augmenting path exists
Cuts and the Max-Flow Min-Cut Theorem
A cut separates all vertices into two groups: those on the S-side (containing S) and those on the T-side (containing T). The cut capacity is the sum of capacities of edges going from S-side to T-side.
The max-flow min-cut theorem states: the maximum flow through the network equals the minimum cut capacity.
This means: to find the maximum flow, find the bottleneck set of edges that, if saturated, prevents any more flow from reaching T.
Strategy: After finding what you think is the maximum flow, verify it by identifying a cut with the same total capacity. If you can find such a cut, your max flow is correct (by the theorem).
Mastery Practice
- Fluency A flow network has edges: S→A (cap 6), S→B (cap 4), A→T (cap 5), B→T (cap 7). What is the maximum possible flow from S to T?
- Fluency In a flow network, node C has edges flowing in: AC=3 units, BC=5 units, and one edge flowing out: C→D. How much must flow on C→D? (Flow conservation applies.)
- Fluency A cut {S→A, S→B} has capacities 8 and 5. Another cut {A→T, B→T} has capacities 6 and 9. Which cut gives a better upper bound on the maximum flow?
- Fluency Verify that the following is a feasible flow: S→A=4 (cap 5), S→B=3 (cap 3), A→C=2 (cap 4), A→T=2 (cap 3), B→C=3 (cap 3), C→T=5 (cap 6). Check both capacity and flow conservation.
- Understanding A water distribution network has edges (with capacities): S→A=10, S→B=8, A→C=6, A→B=3, B→D=9, C→T=7, D→T=8.
- (a) Find the maximum flow from S to T by finding augmenting paths.
- (b) Identify a cut and verify it equals the maximum flow.
- Understanding A road network directs traffic (vehicles per minute) from an entrance (S) to an exit (T): S→A=12, S→B=10, A→C=8, A→D=6, B→C=5, B→D=9, C→T=10, D→T=12. Find the maximum traffic flow from S to T.
- Understanding Explain why a single pipe with capacity 5 in the middle of a large network cannot allow more than 5 units of flow to pass through the network (regardless of the capacities of all other pipes).
- Understanding A network flow problem has maximum flow = 15 units. A project engineer wants to increase the maximum flow to 20 units. The current minimum cut consists of edges with capacities 8 and 7 (total 15). What is the cheapest way to increase the flow? Explain.
- Problem Solving A data network routes packets from server S to user T. Edge capacities (MB/s): 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) Find the maximum data throughput from S to T.
- (b) Identify the minimum cut. Which edges are the bottlenecks?
- Problem Solving A flow network has a maximum flow of 24 units. A cut analysis reveals three possible cuts:
- Cut 1: edges with capacities 9, 8, 7 (total 24)
- Cut 2: edges with capacities 10, 6, 12 (total 28)
- Cut 3: edges with capacities 5, 11, 6, 8 (total 30)