Respect capacities and conservation, then use a cut as an optimality certificate.
By the end: distinguish feasible throughput from a route and explain residual cancellation.
Capacity and conservation
A flow network is a directed graph with nonnegative edge capacities, a source, and a distinct sink. A feasible flow assigns a nonnegative amount to each edge no larger than its capacity. At every other vertex, total inflow equals total outflow. No material is created or permanently stored inside this steady model.
Flow value is net outflow from the source, equivalently net inflow to the sink. Capacities here use items per hour, so flows and cut capacities use the same unit. They are not travel times. Multiple routes may carry flow simultaneously, and shared edges must obey their capacity across all those routes together.
Account for rates at every junction
A route answers whether something can get through. A flow asks how much can get through when several routes operate together. Imagine parcels of one interchangeable kind moving between depots. A capacity of four items per hour means that an edge may carry at most that rate in the stated direction. It does not mean that a parcel spends four hours there. A long journey may have high throughput once operation settles. Travel duration and sustained delivery rate are different quantities, even when both describe the same physical transport system.
Consider a separate paper network with vertices A, B, C, D, source A, and sink D. Its only directed edges and capacities are A to B with four, A to C with three, B to C with two, B to D with two, and C to D with four items per hour. Assign flows four, two, two, two, four in that record order. Every assignment fits its capacity. At B, four arrive and two plus two depart. At C, two arrive directly from A and two arrive from B; four depart toward D.
Six delivered items per hour use fourteen edge-units
Labels are flow/capacity in items per hour. The only edges are the five arrows shown. B receives four and sends four; C receives four and sends four. A sends six and D receives six. Positions and line lengths are schematic.
The source sends six items per hour, while the sink receives six. Adding every edge's flow instead gives fourteen, which is not the delivered throughput. That sum counts some items at several stages of their journey. Two items per hour take A to B to C to D and contribute to three edge entries each. The other four take two-edge routes. Counting arrivals at the final destination avoids this repeated counting. More generally, net source departure means departures minus arrivals, because a graph can allow some flow to return to its source.
Capacity checks alone would miss an impossible allocation. In the same network, suppose someone records four on A to B, one on B to C, and two on B to D, leaving the other records unchanged. B now receives four but forwards only three. One item per hour accumulates there. Temporary storage could make that happen during a changing operation, but it violates this steady flow model. Conservation is a separate constraint from capacity. Repairing the allocation requires changing compatible incoming or outgoing rates, not merely observing that each edge remains below its individual limit.
Route descriptions can also hide shared capacity. Two proposed streams might each use C to D at three items per hour. Each route sounds feasible when considered alone because that edge permits four. Together they demand six on the same edge and cannot both operate at their proposed rates. Edge records combine all route uses before checking capacity. For the feasible allocation above, the two streams entering C have rates two and two. Their combined departure of four exactly uses C to D. Sharing a junction is allowed; exceeding a shared edge's capacity is not.
An edge can fit while its junction accumulates items
Vertex
Feasible inflow / outflow
Altered inflow / outflow
A, source
0 / 6
0 / 6
B
4 / 4
4 / 3
C
4 / 4
3 / 4
D, sink
6 / 0
6 / 0
Both allocations use the first paper network. The altered B-to-C flow remains within capacity, but B accumulates one item per hour and C falls short by one. A steady allocation must satisfy every internal balance, not only every edge limit.
This arithmetic assumes that the capacities already describe simultaneously available resources. If B to D and C to D use the same vehicle, treating their capacities as independent may overstate what can operate together. Likewise, a parcel addressed to B cannot always substitute for one addressed to D. The single-sink model deliberately treats the transported units as interchangeable and requires delivery to D. It establishes feasibility under those recorded constraints. Whether measured handling rates, shared vehicles, or different destinations justify those constraints is evidence to collect before interpreting the result as an operational promise.
Residual edges permit revision
The residual capacity of a forward edge is its capacity minus current flow. A reverse residual edge has capacity equal to that flow and permits cancelling part of an earlier decision. It is a bookkeeping permission, not a new physical reverse pipe. An augmenting path is a source-to-sink path in this residual network.
Increase flow along an augmenting path by its smallest residual capacity. Forward steps add flow; reverse steps subtract it. Conservation remains true at internal vertices. Repeated improvement need not preserve an initially chosen route. Refusing to revise earlier choices can leave capacity unused even when a larger feasible flow exists.
Revise an allocation without inventing a reverse service
Residual capacity describes a permitted change to an allocation, rather than a second inventory of physical links. If a directed edge has capacity three and currently carries one, its forward residual capacity is two. You may add up to two to that edge's flow. Its backward residual capacity is one. You may subtract up to one from that same record. Both permissions follow from keeping the new flow between zero and three. A saturated edge has no forward spare capacity, but its whole allocation remains available for cancellation if a larger arrangement needs revision.
Use another four-vertex paper example, again with source A and sink D. The only original edges are A to B, A to C, B to C, B to D, C to D, with capacities three, three, two, three, three respectively. An early allocation sends two along A to B to C to D, then one along A to B to D and one along A to C to D. The resulting edge flows are three, one, two, one, three. B and C each conserve flow, and the delivered value is four items per hour.
Residual permissions belong to original edge records
Original edge
Capacity
Flow
Forward spare
Backward cancellation
Example edge
3
1
2
1
Saturated example
3
3
0
3
B to C
3
2
1 toward C
2 toward B
C to B, separate edge
4
1
3 toward B
1 toward C
Forward spare capacity equals capacity minus flow. Backward permission equals flow. The final two rows describe separate opposite original edges, so a C-to-B residual step has two different possible meanings. All quantities are integer items per hour.
No further source-to-sink route uses only original forward spare capacity in that allocation. A to B is full, so a new forward-only route must begin A to C. C to D is also full, and C has no other original outgoing edge. This failure does not establish a maximum. A to C still permits two more, the B-to-C record permits cancelling two, and B to D permits two more. These permissions join into the residual path A to C to B to D. Its C-to-B step refers to cancellation of B to C.
Increasing along that residual path by two changes three records. A to C rises from one to three, B to C falls from two to zero, and B to D rises from one to three. A to B and C to D remain at three. At B, losing two of its previous departures toward C is balanced by adding two departures toward D. At C, losing two arrivals from B is balanced by adding two arrivals from A. The final value is six. The calculation revises who forwards which flow, without requiring any parcel to travel physically backward.
The smallest residual permission on a path limits the whole change. Here every step permits two, so adding two is legal and adding three would fail on every step. If only one unit had previously used B to C, cancellation through that record could not exceed one, even if the other residual steps allowed more. For integer capacities and an integer starting allocation, this minimum and every updated flow stay integer. Each successful augmentation increases the integer delivered value. A finite source-capacity bound prevents an endless sequence of such positive integer increases in these examples.
Three residual steps increase delivery by two
Only the chosen residual path is drawn, not the complete physical graph. A to C adds two to its original flow, C to B cancels two on the original B-to-C record, and B to D adds two. Final original flows on AB, AC, BC, BD, CD are 3, 3, 0, 3, 3, giving value six.
Keep original edge identity when directions overlap. Suppose an original B-to-C edge has capacity three and flow two, while a separate original C-to-B edge has capacity four and flow one. A residual step from C toward B could cancel up to two on the first record or add up to three on the second. Those changes affect different original edges, despite sharing endpoints and direction in the residual view. The lesson's model records which edge and which kind of change each step uses. Combining them without that information would make the final allocation difficult to reconstruct or check. Before inspecting the model, define a source-to-sink cut as a partition with the source in one part and the sink in the other. Its capacity counts only original edges leaving the source part, not those entering it. The later conservation argument explains why this bounds delivery.
Inspect the graph and its result
A feasible flow and an equal cut
Maximum feasible flow
Flow value: 5 items/hour.
Minimum cut certificate
Source side: A. Cut capacity: 5 items/hour.
Edge
Flow / capacity
A → B
3 / 3
A → C
2 / 2
B → C
1 / 1
B → D
2 / 2
C → D
3 / 3
Exact endpoint records. Crossing lines do not add a vertex.
Augmenting paths and conservation
Augmentation
Added
Total items/hour
A → B; B → D
2
2
A → C; C → D
2
4
A → B; B → C; C → D
1
5
A reverse residual step subtracts an earlier original-edge flow. An empty trace means zero was already maximum.
Internal vertex
Inflow
Outflow
B
3
3
C
3
3
Internal inflow equals outflow in every final allocation.
Presets replace all capacities. Edge labels are flow/capacity in items per hour on the left and capacity on the right. Blue cut edges go from the marked source side to its complement. The flow is a steady single-commodity allocation, not a transit timetable.
Certificate in the displayed network
Items per hour
Feasible flow value
5
Cut leaving A: 3 + 2
5
Cut entering D: 2 + 3
5
Matching feasible and upper-bound values establish optimality.
Read the preset results as allocations and certificates
In the Capacity five preset, first read the original edge records rather than the apparent widths or lengths of the drawing. The vertices are A, B, C, D; source A and sink D remain fixed. Capacities on A to B, A to C, B to C, B to D, C to D are three, two, one, two, three. The model begins with zero on every edge and searches for residual augmenting paths using breadth-first search. This chooses a path with fewest residual steps, not a route with shortest travel time or cheapest transport.
The complete augmentation trace explains the final allocation. First A to B to D adds two, limited by B to D. Next A to C to D adds two, limited by A to C. The source has then sent four. There is still one spare unit on A to B, B to C, and C to D, so A to B to C to D adds one. Final flows in edge-record order are three, two, one, two, three. B forwards its three arrivals as one plus two; C forwards its two plus one arrivals as three.
The five-unit preset grows through three feasible allocations
Added path
AB
AC
BC
BD
CD
Value
Initial
0
0
0
0
0
0
A to B to D, +2
2
0
0
2
0
2
A to C to D, +2
2
2
0
2
2
4
A to B to C to D, +1
3
2
1
2
3
5
Columns list original edge flows in items per hour. Capacities in that same order are 3, 2, 1, 2, 3. Each row conserves at B and C. This is the deterministic breadth-first residual trace, not a transit timetable.
The final cut marks only A as the source side. Both outgoing edges from A are full, so there is no positive residual step leaving A. Their original capacities total five. This yields an upper bound of five, while the allocation constructs five. Matching those two numbers is stronger than seeing that the algorithm stopped. It gives a result you can check without replaying its search choices. A different feasible allocation with the same delivered value would be equally optimal, even if its intermediate route choices or distribution across internal edges differed.
Switch to Sink bottleneck two and predict which capacity change matters. The source edges remain three and two, and B to C remains one, but B to D and C to D each permit only one. The model can send one along A to B to D and one along A to C to D. There is unused source capacity, yet all delivery into D is full. The final residual-reachable source side is A, B, C. Its outgoing original cut edges are precisely B to D and C to D, whose capacities total two.
In Sink disconnected, the only edges are A to B with three, A to C with two, and B to C with one. D is still a vertex, but no edge enters it. The all-zero allocation is feasible and already maximum. Residual search reaches A, B, C, not D. No original edge leaves that set, so its cut capacity is zero. This illustrates why an empty augmentation trace can be a complete result rather than a missing computation. A source may have generous outgoing capacity while every source-to-sink flow still has value zero.
Each feasible value matches its cut bound
Preset
Source side
Outgoing cut edges
Capacity = value
Capacity five
{A}
AB: 3, AC: 2
5
Sink bottleneck two
{A, B, C}
BD: 1, CD: 1
2
Sink disconnected
{A, B, C}
None
0
A is always the source and D the sink. Source sides are the final residual-reachable sets. Only original edges leaving those sets contribute capacity. An empty cut certifies zero even though the source can reach B and C.
Compare the three presets through both displayed panels. The left gives a feasible edge allocation; the right identifies an upper bound through a partition. Capacity five and Sink bottleneck two both have unused or used internal options that matter only through the full network. Sink disconnected fails through missing connectivity. These are conditional comparisons of supplied records, not observations of a delivery business. Opening the existing augmentation and conservation trace exposes the arithmetic already described here. It adds no transit clock, storage behavior, or measurement of how rapidly the graph calculation would run elsewhere.
A cut supplies an upper bound
An s-t cut partitions vertices so the source is on one side and the sink on the other. Sum capacities of original edges directed from the source side to the sink side, not edges in the reverse direction. Every feasible flow value is at most that sum. Internal inflow and outflow cancel when you total conservation over the source side.
When no residual augmenting path remains, take all vertices reachable from the source in the residual graph. Outgoing crossing edges are saturated and incoming crossing edges carry zero flow. The flow value equals that cut's capacity, so neither a larger feasible flow nor a smaller cut is possible. This is the max-flow/min-cut certificate. The bounded integer model uses a breadth-first augmenting-path search, not real traffic simulation.
Derive the bound and locate useful capacity changes
Return to the first paper network, whose capacities on A to B, A to C, B to C, B to D, C to D are four, three, two, two, four. There are only four source-side sets for an A-to-D cut, because A must be included, D excluded, and B and C can each go on either side. Listing them gives source sides {A}, {A, B}, {A, C}, and {A, B, C}. Their forward crossing capacities are seven, seven, eight, and six respectively. The smallest bound is six, matching the feasible allocation constructed earlier.
Why does any such partition bound delivery, even when routes cross it several times? Total the conservation balances for all vertices on the source side except the source, then include the source's net departure. An edge with both endpoints inside contributes once as departure and once as arrival, so those contributions cancel. What remains is outward crossing flow minus inward crossing flow. That difference equals the delivered value. Outward crossing flow cannot exceed the sum of its edge capacities, and inward crossing flow cannot be negative. Consequently the delivered value cannot exceed the forward cut capacity.
Enumerate every cut in the six-unit paper network
Source side
Forward crossing edges
Capacity, items/hour
{A}
AB, AC
4 + 3 = 7
{A, B}
AC, BC, BD
3 + 2 + 2 = 7
{A, C}
AB, CD
4 + 4 = 8
{A, B, C}
BD, CD
2 + 4 = 6
The graph has only AB:4, AC:3, BC:2, BD:2, CD:4, directed as written. A belongs to the source side and D never does, leaving four possibilities. Their minimum forward capacity is six, and the earlier feasible allocation attains it.
This reasoning also explains the direction rule. An edge pointing back into the source side does not provide additional outward capacity. If it carries flow, it subtracts from net delivery across that boundary. For example, add an original D-to-B edge of capacity three to this paper network and leave its flow zero. In the cut with source side {A, B, C}, that new edge points inward. The cut capacity remains six, not nine. The original feasible six-unit allocation still works, and the unchanged cut proves that this extra reverse service cannot increase the maximum value.
At a final residual search, let the source side contain exactly the vertices still reachable from A. Every original edge leaving that set must be saturated. Otherwise its forward residual step would reach another vertex. Every original edge entering that set must carry zero flow. Otherwise its backward residual step would also reach outside. The cut balance therefore has outward flow equal to outward capacity and inward flow equal to zero. This proves equality between the returned value and the cut bound. The lack of a residual route supplies the particular partition needed for the certificate.
A minimum cut can guide a capacity proposal, but raising any one edge is not automatically useful. In the paper network, increasing A to B from four to five leaves the six-unit cut entering D unchanged, so maximum delivery stays six. Increasing C to D from four to five instead permits flows four, three, two, two, five in record order. They conserve at B and C and deliver seven. The original source cut now supplies a matching bound of seven. This contrast separates additional local spare capacity from a change that actually improves the network's objective.
The useful upgrade changes an actual throughput constraint
Scenario
Capacities
Feasible flows
Equal cut bound
Original
4, 3, 2, 2, 4
4, 2, 2, 2, 4
BD + CD = 6
AB raised to 5
5, 3, 2, 2, 4
4, 2, 2, 2, 4
BD + CD = 6
CD raised to 5
4, 3, 2, 2, 5
4, 3, 2, 2, 5
AB + AC = 7
All scenarios use vertices A, B, C, D and the same five directed edge records. Capacities and feasible flows are listed in AB, AC, BC, BD, CD order. An equal cut proves each stated maximum; extra capacity alone need not increase delivery.
Even that improvement remains conditional on the steady model. Seven units of simultaneous flow do not specify departure times, guarantee deadlines, or separate different parcel destinations. A physical upgrade might also alter more than one recorded capacity, or introduce a shared handling limit absent from the graph. The mathematical certificate remains useful because its claim is precise: these rates fit these capacities, and this partition rules out a larger rate. To use it as advice, identify the real observations that support those premises. A failed empirical prediction can reveal a missing constraint without invalidating the cut calculation.
Exercises
A bottleneck bound
The source has outgoing capacities 4 and 3 items/hour. A later s-t cut has exactly two forward crossing edges, each with capacity 2 items/hour. Is source capacity 7 proof of throughput 7?
Hint
Find an s-t cut, not just local spare capacity.
Worked answer
Constraint
Upper bound, items/hour
Source exit
7
Required later cut
4
Best of these bounds
4
The smaller upper bound is necessary, not automatically attainable.
No. The later cut has capacity 4, so every feasible flow is at most 4. The source cut gives a weaker upper bound of 7. Achieving 4 still requires a feasible flow; a cut bound alone does not construct one.
Undo a poor first route
Unit-capacity edges are A to B, A to C, B to C, B to D, and C to D. One unit first travels A-B-C-D. How can residual cancellation reach value two?
Hint
Use A-C, reverse the B-C allocation, then use B-D.
Worked answer
Original edge
Final flow / capacity
A-B
1 / 1
A-C
1 / 1
B-C
0 / 1
B-D
1 / 1
C-D
1 / 1
Reverse residual movement revises an allocation. Thick blue edges are the named selection; all original connections remain visible.
Augment along residual A-C-B-D. The C-to-B residual step cancels the previous B-to-C flow. The final original-edge flows are one on A-B, A-C, B-D, and C-D, and zero on B-C. No physical reverse edge was added. The source cut of capacity two proves optimality.
Sources and further reading
Selected reference passages support the definitions and algorithms below. The networks, explanations, and implementations are original. Terminology and assumptions are stated within each lesson; source review is not an independent audit of this course. Optional links are not runtime dependencies.
Brief overview and links to implementations. This page is explicitly incomplete; substantive residual and certificate details were checked in the linked implementation.