COMPSCI320 Chap.11 Maximum Flow and Minimum Cut
Maximum Flow and Minimum Cut
Network flow begins with a directed graph, a source, a sink and capacities.
This chapter defines flows, values and cuts, explains why greedy augmentation gets stuck and how residual graphs repair it, runs Ford-Fulkerson by hand to a maximum flow of 15, reads a minimum cut from the vertices still reachable, and analyses why generic Ford-Fulkerson is not polynomial.
The worked example keeps one table of augmenting paths, bottlenecks and running values, and reads the cut from the reachable set.
The practice cards measure a second cut correctly and analyse the network on which badly chosen paths need a number of augmentations proportional to the capacities.
What this chapter covers
- 01
Capacity and conservation constraints
- 02
Cuts and their capacities
- 03
Residual graphs and backward edges
- 04
Augmenting paths and bottlenecks
- 05
The max-flow min-cut theorem
- 06
Integrality and running time
Worked example · free
Augment to a maximum flow and read the cut
- 1Augment s, a, t by 4 and s, a, c, t by 5, filling s→a.
- 1Augment s, b, c, t by 4, filling b→c and c→t.
- 1Augment s, b, t by 2; the flow value is now 15.
- 1In the residual graph s reaches only b, so A = {s, b}.
- 1The cut edges s→a, b→c and b→t have capacity 9 + 4 + 2 = 15, equal to the flow.
Key terms
- Flow Network
- A directed graph with a source, a sink and a non-negative capacity on every edge.
- Residual Graph
- A graph of remaining capacities, with forward edges for spare capacity and backward edges that can cancel flow.
- Augmenting Path
- A path from source to sink in the residual graph along which more flow can be sent.
- Minimum Cut
- A split of the vertices with the source on one side and the sink on the other that has the smallest capacity.
- Flow Value
- The net amount of flow leaving the source of a network.
- Bottleneck Capacity
- The smallest residual capacity on an augmenting path, which is the amount the path can carry.
Maximum Flow and Minimum Cut FAQ
Why does a cut's capacity ignore edges pointing back to the source side?
Capacity measures the most flow that could leave the source side, so only edges from the source side to the sink side count. Flow on edges coming back is subtracted when computing the net flow across the cut, but it never adds capacity. Counting those edges is a frequent slip and makes a cut look larger than it is.
Why do we need backward edges in the residual graph?
A greedy method that only adds flow can commit to a bad route and get stuck below the maximum, as the lecture's example stuck at 16 instead of 19 shows. A backward edge lets a later path cancel flow sent earlier and reroute it. With backward edges, the absence of any augmenting path really does mean the flow is maximum.
Is Ford-Fulkerson a polynomial-time algorithm?
Not in general. Each augmentation adds at least one unit with integer capacities, so the number of augmentations can grow with the largest capacity C. The lecture shows a network that needs 2C augmentations when paths are chosen badly. Choosing paths by bottleneck size or by length gives polynomial bounds instead.
What does the integrality theorem guarantee?
With integer capacities, Ford-Fulkerson only ever adds whole units, so every flow value and residual capacity stays an integer and the final maximum flow is integral. This is what allows flow to solve matching and assignment problems, where each unit means one pairing and a fractional flow would have no sensible interpretation.
Exam move
Run Ford-Fulkerson by hand on two small networks, keeping one table of paths, bottlenecks and running values, and finish each with the reachable-set cut. Compute the capacity of two or three other cuts to see that none is smaller. Then explain the backward edge in a sentence using a concrete undo. Close your revision by drawing the residual graph of your final flow and checking that no path leads from the source to the sink.
Rehearse the three equivalent conditions of the max-flow min-cut theorem until you can state them in order.
Working through Maximum Flow and Minimum Cut in COMPSCI320? Sia is AskSia’s AI Computer Science tutor — ask any COMPSCI320 Maximum Flow and Minimum Cut question and get a clear, step-by-step explanation grounded in how COMPSCI320 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
