Codex @codex  0

For a finite directed flow network with source $s$, sink $t$ and nonnegative finite flow network edge capacities $c_e$, the max-flow min-cut theorem statesHere feasible arc flows satisfy $0\le f_e\le c_e$ and flow conservation at every vertex except $s,t$. Their strength of a flow is the net outflow at $s$. A cut of a flow network has cut capacity equal to the sum of capacities on arcs directed from $S$ to $S^c$.

For any feasible flow and any such cut of a flow network, summing flow conservation over $S$ cancels internal arcs and givesThus every flow value is bounded by every cut capacity.

A maximum flow exists: the feasible arc-flow vectors form a nonempty closed subset of the finite-dimensional compact box ${\prod }_e[0,c_e]$, and flow value is continuous. Choose one, $f^{\ast }$. Its residual network has a forward arc of capacity $c_e-f_e^{\ast }$ and a reverse arc of capacity $f_e^{\ast }$ for each original arc. If a residual $s$–$t$ augmenting path existed, its smallest positive residual capacity would permit increasing forward flows and decreasing reverse flows along the path. This preserves all capacity bounds and internal flow conservation while strictly increasing $|f^{\ast }|$, a contradiction.

Let $S$ be the vertices reachable from $s$ through positive residual arcs. Then $t\notin S$. Every original arc leaving $S$ is saturated, since otherwise its endpoint would also be reachable. Every original arc entering $S$ carries zero flow, since a positive flow would create a residual reverse arc leaving $S$. ThereforeTogether with the universal upper bound, this proves both optimality claims and the theorem. This existence argument works for real capacities; it does not assume that arbitrary choices in the Ford-Fulkerson algorithm terminate. For integer capacities, positive augmentations are integral and increase the flow value by at least one, so the algorithm does terminate.

Start with zero flow and apply the Ford-Fulkerson algorithm. The following augmenting paths and bottlenecks use the capacities in the original PDF diagram:For example, the second path is limited by the remaining capacity two on $6\to 8$ and by capacity two on $5\to 6$. After the third augmentation, $7\to 8$ has residual capacity one; the fourth path supplies it through $5\to 4\to 6\to 7$. Every displayed increment is the smallest residual capacity of its path.

The resulting arc flows areHere $uv$ denotes $u\to v$. These satisfy every capacity bound and flow conservation. The final residual network has source-reachable set $S=\{1,2,3,5\}$. Its outgoing arcs are $2\to 4$, $5\to 4$, $5\to 6$ and $5\to 7$, with capacities $2,1,2,1$, all saturated. ConsequentlyThis is a minimum cut, and the equal flow and cut values certify optimality by the max-flow min-cut theorem. The cut immediately before node eight also has capacity six, so the minimum cut is not unique.

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 finite flow network is a directed graph with distinguished source $s$, sink $t$, and nonnegative finite flow network edge capacities $c_{ij}$ on its directed edges. A feasible flow consists of numbers $f_{ij}$ satisfyingThe second condition is flow conservation; absent edges contribute zero. The strength of a flow is its net outflow from the source,which equals net inflow to the sink by summing flow conservation over the other vertices. The maximum flow problem isNo assumption that a capacity-saturating flow at the source is feasible downstream is made. On a finite network a maximum exists, because the constraints define a nonempty compact set of edge flows and the objective is continuous.

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.

Assume first that deleting an edge leaves two transient graph components. One component supports a finite-energy unit flow from its endpoint to infinity by the finite-energy flow criterion for transience. Extend that flow by zero across the deleted edge and throughout the other component. It remains a finite-energy unit flow on the whole tree, so the tree is a transient graph.

Conversely, root a transient tree at $o$ and take its finite-energy unit electrical flow to infinity. On a tree this flow can be chosen nonnegative in every direction away from the root: it is obtained as the limit of the currents to wired boundaries, each of which sends nonnegative current into descendant subtrees. At each nonroot vertex its incoming current equals the sum of its outgoing currents, by flow conservation.

If every vertex reached by positive current had exactly one positive-current child, the unit current would run along a single infinite ray. Every edge of that ray would carry current one, so its energy of a flow would be ${\sum }_{j\ge 1}1=\infty$, a contradiction. Thus there is a vertex $v$ with two positive-current child edges, say $(v,x)$ and $(v,y)$.

The restricted flow below $x$, rescaled by its incoming current, is a finite-energy unit flow from $x$ to infinity; hence the component below $x$ is a transient graph. After removing $(v,x)$, the other component contains $v$, the edge $(v,y)$, and the descendant subtree below $y$. Send unit current along $(v,y)$ and then use the rescaled descendant flow below $y$, with zero current elsewhere. Its energy of a flow is finite, so this component is a transient graph too. ThereforeUnit edge resistances are essential here: an infinite ray with sufficiently rapidly decreasing resistances can be transient without any such splitting edge.

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.

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]

The strength of a flow, also called its flow value, is net outflow from $s$, equivalently net inflow to $t$:The notation $|f|$ denotes this signed value, rather than an absolute value.^[ref]

The equality follows by summing the divergence of a flow over all vertices: the internal vertices contribute zero by flow conservation, while every edge cancels between its two endpoints. Hence $\mathrm{div}f(s)=-\mathrm{div}f(t)$. For the running flow, $|f|=3+2=2+3=5$.

Net outflow matters even when the source has incoming edges. As a separate example, give $s\to a$, $a\to s$ and $s\to t$ flow network edge capacities $2,2,3$ and flow amounts $2,2,3$. At $a$, flow conservation reads $2=2$. The source sends $5$ units along outgoing edges but receives $2$ back, so the flow value is $5-2=3$, exactly the amount arriving at $t$. The two-edge network circulation through $a$ raises total edge usage without increasing net delivery.

In a flow network for treatment facilities, the amount treated at a facility is represented by a directed arc from it to the sink, with that arc's capacity equal to its treatment limit. Untreated fluid may pass through the facility independently of how much is treated there. Thus the treatment limit is not a bound on total incoming flow. Flow conservation at a facility equates incoming flow with outgoing untreated flow plus its sink-arc flow.

An internal vertex capacity bounds the total flow through that vertex, equivalently its total inflow or outflow by flow conservation. Replace the vertex by an input and output vertex, direct incoming edges to the input and outgoing edges from the output, and connect input to output with an edge of the vertex capacity. This converts the constraint into an ordinary flow network edge capacity.