Codex @codex  0

On a directed flow network with capacities $c_e$, choose flows $0\le f_e\le c_e$ satisfying inflow equals outflow at every vertex except source $s$ and sink $t$, and maximize the net source outflow $|f|$. For a cut of a flow network $S$ containing $s$ but not $t$, its capacity is ${\sum }_{u\in S,v\notin S}{c}_{uv}$. The max-flow min-cut theorem statesEvery feasible flow is bounded above by every cut capacity; equality for a feasible flow and a cut proves optimality.

The Ford-Fulkerson algorithm starts with a feasible flow, for instance zero. A forward edge has residual capacity $c_{uv}-f_{uv}$ and its reverse edge has residual capacity $f_{uv}$. Find a source-to-sink augmenting path in this residual network, and increase the flow along it by the minimum residual capacity on the path, reducing original-edge flows when reverse edges are used. Repeat until no such path exists. The vertices reachable from the source then define a saturated minimum cut of a flow network. With integer capacities and zero initial flow, all residual capacities and augmentations are integers. Each augmentation increases $|f|$ by at least one, while $|f|$ is bounded by the finite sum of source capacities, so termination takes finitely many steps.

For the original roads, a feasible maximizing flow is given below; every table entry is flow/capacity in vehicles per minute.

All road capacities are respected, and direct summation verifies flow conservation at each roundabout. The original flow value is $90$. The cut separating $B$ from every other vertex consists of its two incoming roads and has capacity $40+50=90$. Therefore the original maximum is 90 vehicles per minute.

To impose a vertex capacity, split $R_2$ into $R_2^{-}$ and $R_2^{+}$. Send its incoming roads to $R_2^{-}$ and its outgoing roads from $R_2^{+}$, and add a directed internal edge $R_2^{-}\to R_2^{+}$ of capacity $20$. Every unit passing through the roundabout must traverse this internal edge. This gives the standard maximum flow with vertex capacities construction.

Starting from zero, apply the Ford-Fulkerson algorithm with the following augmenting paths in order. First use $A\to R_1\to R_3\to B$: its residual capacities are $60,10,40$, so augment by $10$. Next use $A\to R_4\to R_5\to B$: the residual capacities are $50,30,50$, so augment by $30$. Finally use $A\to R_1\to R_2^{-}\to R_2^{+}\to R_3\to B$: the residual capacities at this stage are $50,30,20,40,30$, so augment by $20$. No reverse edge is needed in this valid run. The resulting original-road flows are precisely the after-storm column above, and the internal edge carries $20$.

For termination and optimality, take the source-side set $\{A,R_1,R_4,R_2^{-}\}$. Its outgoing edges are $R_1\to R_3$, $R_4\to R_5$ and $R_2^{-}\to R_2^{+}$, of capacities $10,30,20$. They are all saturated, and no positive-flow original edge enters this set. Consequently no residual path leaves the set, and its cut capacity equals the constructed flow value. The new maximum is therefore

A maximum flow problem specifies a finite directed flow network, a source $s$, a sink $t$, and nonnegative arc capacities. A feasible flow assigns $0\le f_e\le c_e$ to each arc, with incoming flow equal to outgoing flow at each vertex other than $s,t$. The objective is to maximize the net flow leaving $s$, equivalently entering $t$.

The Ford-Fulkerson algorithm starts with zero flow. Its residual network has a forward arc of capacity $c_e-f_e$ and a reverse arc of capacity $f_e$ for each original arc. If an $s$–$t$ path has positive residual capacities, augment by their minimum: increase flow along forward arcs and decrease it along reverse arcs. This preserves capacity bounds and conservation, and increases the flow value by that positive bottleneck. Repeat until there is no augmenting path.

For rational capacities, choose a positive integer $D$ clearing every denominator. Initially all flows and residual capacities are integer multiples of $1/D$, and augmentation preserves that property. Every augmentation therefore increases the flow value by at least $1/D$. The flow value is bounded above by the sum of capacities of arcs leaving $s$. Thus only finitely many augmentations can occur, independently of how the augmenting paths are chosen.

To see why termination supplies a maximum, let $S$ consist of vertices reachable from $s$ in the final residual network. The sink is not in $S$. Each original arc from $S$ to its complement is saturated; each original arc entering $S$ has zero flow, since otherwise its reverse residual arc would leave $S$. The resulting flow value equals the capacity of this cut. No feasible flow exceeds a cut capacity. Hence the algorithm terminates at a maximum flow for rational capacities, proving the relevant max-flow min-cut theorem conclusion as well.

The Ford-Fulkerson algorithm starts with zero flow. For each original edge $i\to j$, the residual network has a forward edge with residual capacity $c_{ij}-f_{ij}$ and a reverse edge with residual capacity $f_{ij}$. Distinguish these labelled residual edges if the original graph has antiparallel edges. While there is a source-to-sink augmenting path with positive residual capacities, increase the flow by the minimum residual capacity along it, adding on forward edges and subtracting on reverse edges. This preserves capacity bounds and flow conservation and increases the strength of a flow by that positive bottleneck.

A cut of a flow network is a partition $(S,V\setminus S)$ with $s\in S$, $t\notin S$, of capacity $c(S)={\sum }_{i\in S,j\notin S}{c}_{ij}$. Summing flow conservation gives $|f|=f(S,V\setminus S)-f(V\setminus S,S)\le c(S)$. The max-flow min-cut theorem statesWhen no augmenting path remains, take $S$ to be the vertices reachable from $s$ in the residual network. Every original outgoing edge of this cut of a flow network is saturated and every incoming edge has zero flow; otherwise a positive residual edge would leave $S$. Thus $|f|=c(S)$, certifying optimality and the theorem. For general finite real capacities, one can also apply this argument to an existing maximum: it cannot admit an augmenting path.

With integer capacities, each augmentation increases the value by at least one, so the Ford-Fulkerson algorithm terminates. Rational capacities can be scaled to integers. Arbitrary path choices with irrational capacities need not terminate; the existence theorem does not justify claiming finite termination in that generality. The given network has integer capacities, so this caveat does not obstruct its computation.

Reading the arrows directly from the original PDF gives, in particular, $c\to a$ and $e\to d$. Starting from zero flow, use the following augmenting paths and bottlenecks, in order:

Each path is available in the current residual network. The resulting nonzero edge flows areThe flows on $c\to a$ and $e\to d$ are zero. Capacity constraints and flow conservation hold at each interior vertex; net source outflow is $6+8+5=19$.

Take $S=\{s,a,b,c\}$. Its outgoing edges are $a\to d$, $c\to d$, $b\to e$, $c\to e$, with total capacity $6+2+5+6=19$. Thus the matching flow and cut of a flow network certificates giveThese are also exactly the source-reachable vertices in the final residual network. The original drawing below labels each edge by flow/capacity; the highlighted edges realise the minimum cut of a flow network.

The max-flow min-cut theorem states that in a finite flow network, the maximum value of a feasible source-to-sink flow equals the minimum capacity of a source-to-sink cut.

First consider any feasible flow $f$ and any cut $(A,V\setminus A)$ with $S\in A$ and $T\notin A$. Summing flow conservation over the vertices in $A$ cancels all contributions from edges internal to $A$ and givesThus every flow value is at most every cut capacity.

A maximum flow exists because the feasible flows form a nonempty compact subset of a finite-dimensional Euclidean space and the flow value is continuous. Let $f$ be maximum and form its residual network. If there were an augmenting path from $S$ to $T$, increasing $f$ by the path's positive bottleneck capacity would contradict maximality. Let $A$ be the set of vertices reachable from $S$ in the residual network. Then $T\notin A$. Every original edge from $A$ to its complement is saturated, while every original edge entering $A$ carries zero flow; otherwise the corresponding forward or reverse residual edge would make its other endpoint reachable. ConsequentlyThe general upper bound is attained by this flow and cut, proving the theorem.

After these augmentations, the vertices reachable from $S$ in the residual network areThe edges leaving this set are $S\to b$, $a\to d$, and $c\to e$, with capacities $3$, $1$, and $4$. HenceThe flow in part (i) has the same value, so the max-flow min-cut theorem proves that it is maximum and that this cut is minimum.

For a feasible flow $f$, each original directed edge $u\to v$ supplies a forward residual network edge of capacity $c_{uv}-f_{uv}$ and a backward one $v\to u$ of capacity $f_{uv}$; zero-capacity residual edges may be omitted. The forward edge permits an increase, while the backward edge permits cancellation of existing flow. In particular, backward residual capacity is the amount already sent, rather than unused original capacity. If both original orientations exist, keep their residual contributions separate, or add capacities for contributions with the same direction. An augmenting path uses these permitted changes while preserving flow conservation and the capacity constraints.

To see why cancellation matters, give all five directed edges $s\to a$, $s\to b$, $a\to b$, $a\to t$, $b\to t$ unit flow network edge capacities. Starting from zero flow, an augmenting path $s\to a\to b\to t$ carrying $1$ yieldsThe remaining unused original edges are $s\to b$ and $a\to t$, which do not form a source-to-sink graph path. However, the backward residual edge $b\to a$ has capacity $f_{ab}=1$. Consequently the residual network contains the augmenting path $s\to b\to a\to t$, with residual capacities $1,1,1$.

Augment by $1$: increase $f_{sb}$ and $f_{at}$ from $0$ to $1$, and decrease $f_{ab}$ from $1$ to $0$. The result isNow flow conservation is $1=0+1$ at $a$ and $1+0=1$ at $b$. The final flow sends one unit along each of $s\to a\to t$ and $s\to b\to t$. The cut of a flow network $S=\{s\}$ has cut capacity $1+1=2$, proving this is a maximum flow. Traversing $b\to a$ in the residual network revised the earlier routing decision; it did not send actual traffic along a nonexistent original edge.

In a finite flow network, a maximum flow exists because the feasible flow set contains the zero flow and is a compact set: the capacity constraints bound every coordinate, and they and flow conservation define a closed set. The strength of a flow is a continuous function, so the extreme value theorem gives an attained maximum. An augmenting path in the residual network would permit positive augmentation, contradicting maximality. The source-reachable vertices in the residual network therefore define a cut of a flow network whose outgoing original edges are saturated and incoming original edges carry zero flow. Flow conservation makes the strength of a flow equal to this cut capacity, proving the max-flow min-cut theorem.

Existence and strong duality for finite real flow network edge capacities do not imply finite termination for every choice of augmenting paths in the Ford-Fulkerson algorithm. With irrational capacities, some choices can continue forever. With integer capacities, Integrality of the Ford-Fulkerson algorithm instead forces finite termination; rational capacities reduce to that case by a common denominator. Choosing shortest augmenting paths as in the Edmonds–Karp algorithm avoids dependence on capacity magnitudes.^[ref]

An augmenting path maximizing the possible increase in flow, namely its smallest residual network edge capacity. If the remaining maximum flow is $F>0$ and the original undirected network has $m$ edges, a path has bottleneck at least $F/m$. Otherwise the vertices reachable through arcs of capacity at least $F/m$ define a cut of capacity strictly less than $F$, contradicting the max-flow min-cut theorem. Only one directed arc per original crossing edge contributes to that cut.