Until now, Rutalia's edges measured the cost of traversing them (minutes) or of building them (euros of fiber). This lesson gives them a third meaning: capacity — how many packages per hour can move along each street. The question changes in nature: we no longer seek the best path for one van, but the maximum throughput the whole fleet can sustain between the warehouse and a neighborhood at rush hour. This is the maximum flow problem, one of the great classics of graph theory, with beautiful theory (the residual network, the max-flow min-cut theorem) and surprising reach: at the end we will see that even assigning couriers to orders is, secretly, a flow problem.

1. The flow problem: capacities, conservation, source and sink
2. The greedy trap and the residual network: why backward edges are needed
3. Ford-Fulkerson: the augmenting-path method
4. Edmonds-Karp: Ford-Fulkerson with the BFS of 03-02
5. Rutalia's rush-hour network, solved step by step
6. The max-flow min-cut theorem: the physical bottleneck
7. Assignment as flow: a preview of 03-06

A flow network is a directed graph where each edge (u, v) has a capacity c(u, v) ≥ 0, with two distinguished nodes: the source s (where the flow is born) and the sink t (where it dies). A flow assigns each edge an amount f(u, v) satisfying:

• Capacity constraint: 0 ≤ f(u, v) ≤ c(u, v). A street rated at 8 packages/hour will not carry 9.
• Conservation: at every node except s and t, what comes in equals what goes out. Intersections neither manufacture nor store packages.

The value of the flow is the net amount leaving s (equivalently, the amount reaching t). The maximum flow problem: find the flow of maximum value.

Rutalia scenario: it is rush hour and the Historic Center (CEN) concentrates the orders. Packages leave the Warehouse (ALM) towards CEN through the Market area (MER), the River Bridge (RIO) and the University District (UNI). The capacities (packages/hour, estimated from traffic and how many vans each axis can take, in the direction that matters at rush hour) are:

Question: how many packages/hour can Rutalia inject into the Center? By eye it is not obvious: 12 + 11 = 23 leave ALM, 6 + 9 + 8 = 23 enter CEN… but we will see the real answer is 22, and the limit lies neither at the exit nor at the arrival, but in an intermediate cut.

First impulse: find a path from s to t with free capacity, push as much as possible, repeat. The problem is that an early choice can block better combinations. A minimal example (a sub-network with small capacities to see it clearly):

• ALM→MER: 8, ALM→RIO: 8, MER→CEN: 8, RIO→CEN: 8, and a transversal shortcut MER→RIO: 6.
• The optimum is obvious: 8 along the top (ALM→MER→CEN) and 8 along the bottom (ALM→RIO→CEN) = 16, ignoring the shortcut.
• But suppose the first path explored is ALM→MER→RIO→CEN and we push 6 through it. Now ALM→MER has 2 free and RIO→CEN has 2 free: the direct paths only add 2 + 2 = 4 more. Total 10. Stuck far from 16.

The solution is accounting, not physics: allow decisions to be undone. We define the residual network: for each edge with capacity c and flow f, the residual contains:

• the forward edge with capacity c − f (what still fits), and
• a backward edge v→u with capacity f (what can be cancelled).

In the stuck example, the residual network contains RIO→MER with capacity 6 (the shortcut's backward edge). The residual path ALM→RIO→MER→CEN with bottleneck 6 "sends 6", which actually means: 6 new units come in along the bottom up to RIO, and 6 of the units that were turning down the shortcut towards RIO stay up top and continue to CEN. Nobody drives in reverse: only the bookkeeping is rewritten. Total: 16. The initial greed, corrected without starting over.

A path from s to t in the residual network is called an augmenting path; its bottleneck is the minimum residual capacity of its edges.

The Ford-Fulkerson method is exactly that loop:

Key properties:

• With integer capacities, each iteration increases the flow by ≥ 1, so it terminates; and the resulting maximum flow is an integer (integrality theorem — it will be crucial in 03-06: "half a courier" does not exist).
• Cost: O(m) per search iteration × number of iterations. If the paths are chosen badly, the iterations can go up to f* (the value of the maximum flow): O(m · f*). There is a classic example with capacities of 1,000,000 and a capacity-1 shortcut where a perverse choice alternates 2 million one-unit paths. "Ford-Fulkerson" is a method; it still needs a rule for finding the path.

Edmonds-Karp pins down the choice: always find the augmenting path with the fewest edges, that is, with the BFS of 03-02 over the residual network. That detail bounds the iterations at O(n·m) regardless of the capacities, giving a total cost of O(n · m²).

A guided reading of the code:

• The residual network res unifies spare room and backward edges: res[u][v] is "how much more I can push from u to v right now", whether (u,v) was a real edge or the shadow of an opposite one.
• The BFS is literally the one from 03-02 with one extra filter (c_res > 0) and an early stop upon reaching t; parent reconstructs the path just as it did then.
• When no path exists, the set parent (the nodes reachable from s in the residual) is no byproduct: it is the S side of the minimum cut, as we will see shortly. The algorithm gives away the optimality certificate.

Sequence of augmenting paths that Edmonds-Karp finds (BFS favors short ones):

The final flow per edge: ALM→MER 12/12, ALM→RIO 10/11, RIO→MER 1/4, MER→CEN 6/6, MER→UNI 7/7, RIO→CEN 9/9, UNI→CEN 7/8. Check conservation at MER: 12 + 1 = 13 in, 6 + 7 = 13 out ✓. Iteration 4 is the residual network in action: the extra package comes in via the river and uses the RIO→MER shortcut to reach the room left in UNI→CEN.

An s-t cut is a partition of the nodes into (S, T) with s ∈ S and t ∈ T; its capacity is the sum of the capacities of the edges going from S to T (that direction only). Every flow must cross every cut, so maximum flow ≤ capacity of any cut. The deep result is the equality:

Max-flow min-cut theorem: the value of the maximum flow equals exactly the capacity of the minimum cut.

And the proof is constructive with what we already have: when Edmonds-Karp stops, S = {reachable from s in the residual} defines a cut whose S→T edges are all saturated (had they any room, the BFS would have crossed). That cut has capacity = current flow, and since no flow exceeds any cut, both are optimal at once. The algorithm gives not just the number but the certificate, just as the B&B bound in 02-03 certified the TSP's 35.22.

In Rutalia: S = {ALM, RIO, MER}, T = {UNI, CEN}. The edges of the minimum cut are MER→UNI (7), MER→CEN (6) and RIO→CEN (9): 7 + 6 + 9 = 22. Immediate physical interpretation for the operations team:

• The 22 packages/hour limit is not at the warehouse's exit (23) or at the final accesses to the Center (23), but in the intermediate ring.
• If the city council asks which streets to widen, the theorem's answer is surgical: only those in the minimum cut. Widening ALM→MER or UNI→CEN adds not one package; widening RIO→CEN by 1 raises the throughput to 23 (until another cut becomes the minimum — recompute after every change).

Note the parallel with 03-02: there we asked whether a cut disconnects (connectivity); here, how much it strangles (capacity). Maximum flow is the quantitative version of robustness.

The final surprise: maximum flow solves problems where nothing "flows" at all. Can 3 couriers be assigned to 3 orders if each courier can only handle certain orders (by zone, by vehicle type)? Build this network:

• Source s → each courier, capacity 1 (each one handles at most one order).
• Courier → each compatible order, capacity 1.
• Each order → sink t, capacity 1 (each order is served by at most one courier).

Each integer unit of flow is a courier-order pair, and the maximum flow is the maximum number of simultaneous compatible assignments. Ford-Fulkerson's integrality guarantees the solution does not split couriers into fractions. This reduction — turning one problem into another already solved — is one of the most elegant weapons in algorithmics, and it is exactly the bridge to the next lesson: matching in bipartite graphs (03-06), where we will develop it in full detail along with its specialized algorithms.

• Omitting the backward edges: mistake number one. Without them, the result depends on the exploration order and can fall short (10 versus 16 in our minimal example). If your "maximum flow" changes when you reorder neighbors, it is almost certainly this.
• Modeling the network as undirected: rush-hour capacities have a direction — a two-way street is modeled as two directed edges, each with its own capacity. Copying the graph of 03-01 without directing it produces meaningless answers.
• Using DFS for the augmenting path with large capacities: plain Ford-Fulkerson can iterate millions of times (the capacity-1 shortcut example). Edmonds-Karp's BFS bounds the iterations independently of the capacities. For serious networks there are better algorithms (Dinic, push-relabel); networkx.maximum_flow ships them out of the box.
• Reading the minimum cut as "the saturated edges": there are saturated edges that are not in the minimum cut (ALM→MER runs at 12/12 and is not in it). The cut is S→T with S = reachable in the residual; saturation is necessary but not sufficient.
• Forgetting to verify conservation while debugging: sum the inputs and outputs of every intermediate node. It is the cheapest, most telltale assert in this whole lesson.
• Tip: always draw the residual network after each augmentation in small examples. This lesson's "aha" moment is watching a backward edge turn a bad decision into a reversible one.

1. Surgical widening. Using edmonds_karp, check how much the rush-hour network's throughput improves if (a) ALM→MER goes from 12 to 15, (b) RIO→CEN goes from 9 to 11. Explain both results using the minimum cut before running the code, then verify.
2. The analyst's worst cut. Compute by hand the capacity of the cuts S = {ALM} and S = {ALM, MER, RIO, UNI} of the rush-hour network and check that both exceed 22. What does this tell you about using "what leaves the warehouse" as an estimate of delivery capacity?
3. Express assignment. Rutalia has 3 couriers with compatibilities: R1→{P1, P2}, R2→{P2}, R3→{P2, P3}. Build the assignment network (source, sink, capacities 1) and compute with edmonds_karp how many orders can be served at once. Is there a perfect assignment?

Exercise 1:

(a) ALM→MER does not belong to the minimum cut {MER→UNI, MER→CEN, RIO→CEN}: widening it is money down the drain, the strangling continues downstream. (b) RIO→CEN is in the cut: widening by 2 raises the cut to 24, but then another limit takes over (at 23 the ALM exit saturates: 12+11) and only 1 is gained. Cuts take turns: after every roadwork you must recompute.

Exercise 2:

• S = {ALM}: edges ALM→MER (12) + ALM→RIO (11) = 23.
• S = {ALM, MER, RIO, UNI}: edges into T = {CEN}: MER→CEN (6) + RIO→CEN (9) + UNI→CEN (8) = 23.

Both cuts are worth 23 > 22: valid upper bounds, but not tight ones. Moral: the warehouse's output capacity (or the neighborhood's intake) is an optimistic estimate of real throughput; the true limit can hide in any intermediate cut, and only maximum flow finds it with a certificate.

Exercise 3:

Maximum flow 3 = perfect assignment: R1→P1, R2→P2, R3→P3. Notice that naive greed could fail (if R1 grabbed P2, R2 would be left without an order) and it is the augmenting-path machinery that straightens it out — in 03-06 we will see this same correction under its proper name: alternating path.

We have added the third reading of an edge — capacity — and with it the maximum flow problem: throughput from s to t while respecting capacities and conservation. The key conceptual piece is the residual network, whose backward edges make greedy decisions reversible and sustain the Ford-Fulkerson method; the practical embodiment is Edmonds-Karp, which finds each augmenting path with the BFS of 03-02 and guarantees O(n·m²). And the theoretical prize is max-flow min-cut: the maximum flow of Rutalia's rush hour is 22 packages/hour not because of what leaves the warehouse or what fits into the Center, but because of an intermediate three-street cut — the physical bottleneck that says exactly what to widen and what not to. As a parting gift, a reduction with an immediate future: courier-order assignment is a flow with capacities of 1. In 03-06, the module's final lesson, that idea blossoms into the matching algorithms for bipartite graphs: bipartiteness, alternating paths, the Hungarian algorithm and the optimal assignment we used to solve with linear programming in 02-01.