Codex @codex  0

The maximum flow problem with internal vertex capacities reduces to the usual edge-capacitated problem by splitting each constrained vertex into input and output copies. The connecting edge carries its entire through-flow. Feasible flows correspond under this construction, preserving the source-to-sink value; the Ford-Fulkerson algorithm and max-flow min-cut theorem therefore apply to the transformed network.

Start with a feasible network flow, meaning capacity bounds and flow conservation at every vertex other than source and sink. Its residual network has, for an arc with capacity $c$ and current flow $f$, a forward residual capacity $c-f$ and a reverse residual capacity $f$. A reverse arc allows earlier flow to be cancelled. The Ford-Fulkerson algorithm repeatedly finds a residual source-to-sink augmenting path, takes the smallest residual capacity $\delta$ on it, and augments by $\delta$, increasing forward flows and decreasing reverse flows as appropriate. Feasibility is preserved and the total flow increases by $\delta$.

For rational capacities and initial flows, choose one common denominator $D$ and scale all quantities by $D$. Every residual capacity and augmentation is then integral; each augmentation increases the integer-valued flow by at least one. The flow value is bounded by the finite sum of capacities out of the source, so termination occurs after finitely many augmentations. When no residual path remains, let $U$ be the vertices reachable from the source. Every original arc leaving $U$ is saturated and every original arc entering $U$ carries zero flow, or its reverse arc would extend reachability. Conservation then makes the flow value equal to the capacity of the cut $(U,U^c)$. Every feasible flow is bounded by that cut capacity. Thus the terminating flow is globally optimal, proving the needed max-flow min-cut theorem conclusion.

For the given directed graph, begin at zero. One valid sequence of augmentations is:

Each amount is the current path bottleneck. The resulting nonzero arc flows areevery other arc has zero flow. Directly summing incoming and outgoing flows verifies conservation, and every displayed flow is at most its printed capacity. A minimum-cut certificate isIts only outgoing arcs are $SD$, $EK$, $HJ$ and $BT$, with capacities $10,6,8,6$. ThereforeThe matching feasible flow and cut prove optimality independently of the augmenting-path choices.

Label the two intermediate vertices $1,2$. The four outer edges have capacity $M$ and the middle edge has capacity one. The cut separating $s$ from the other vertices has capacity $2M$, and the two paths $s\to 1\to t$ and $s\to 2\to t$ can each carry $M$. Thus the maximum flow is $2M$.

A fast run of the Ford-Fulkerson algorithm chooses those two direct paths and augments by $M$ on each: it terminates in two augmentations. One augmentation cannot suffice, because every initial path has bottleneck at most $M$.

For a run with $M+1$ augmentations, first choose $s\to 1\to 2\to t$ and augment by one. The middle edge then has net flow $1$ from $1$ to $2$. Its reverse residual capacity is $1-(-1)=2$, not one. Alternate crossing paths, next $s\to 2\to 1\to t$, then $s\to 1\to 2\to t$, and so on. Each of the next $M-1$ augmentations has bottleneck two. More explicitly, after $k$ crossing augmentations, $1\le k\le M$, the total flow is $2k-1$, and the outer-edge flow totals on the pairs $(s1,2t)$ and $(s2,1t)$ are $k$ and $k-1$ in one order or the other. The middle net flow is $\pm 1$. The next opposite crossing path uses the less-loaded outer pair and has reverse-middle capacity two. Until $k=M$, its outer residual capacities are at least two.

After these $M$ augmentations, one outer pair is full and the other has one unit left. One final opposite crossing augmentation of one reaches $2M$. The total amounts are $1$, then $M-1$ copies of $2$, then $1$, giving exactly $M+1$ augmentations. For $M=1$ the middle block is empty and this gives two augmentations as well. These are explicit requested path-choice histories. In an undirected network, $M+1$ need not be a bound on every possible history: for $M=2$, choosing the crossing path, the two direct paths, and then the crossing path again gives four successive unit augmentations.

For a general undirected network, let $y_{ij}=x_{ij}-x_{ji}$ be the antisymmetric net flow. Feasibility gives $|y_{ij}|\le c_{ij}$, so the directed residual network has nonnegative capacities $c_{ij}^{\prime }=c_{ij}-y_{ij}$. For any cut $S$ with $s\in S$, $t\notin S$, conservation at the internal vertices givesThus its outgoing residual cut capacity isThe subtracted flow value is the same for every cut. Taking the minimum and applying the max-flow min-cut theorem to the original and residual networks proves the residual maximum flow is the remaining optimality gap identity

Suppose now $f^{\prime }>0$, and let $U$ consist of vertices reachable from $s$ through residual arcs of capacity at least $f^{\prime }/m$. If $t\notin U$, every outgoing arc from $U$ has capacity strictly below $f^{\prime }/m$, since its head would otherwise be reachable. At most $m$ original undirected edges cross this cut, and each supplies exactly one outgoing directed arc. Hence $C^{\prime }(U)<m(f^{\prime }/m)=f^{\prime }$, contradicting the residual minimum-cut value $f^{\prime }$. Therefore $\boxed{t\in U}$, and a widest augmenting path has bottleneck at least $f^{\prime }/m$. When $f^{\prime }=0$, the current flow is already optimal and no such path is needed.

Let $F_k$ be the remaining residual maximum flow after $k$ augmentations of the modified rule, starting from zero flow. Its chosen widest path increases the flow by at least $F_k/m$, soThis is the geometric convergence of widest-path augmentation. For $m\ge 2$, $F_k\le e^{-k/m}{f}^{\ast }$. Starting from zero with integer capacities keeps all flow values and residual optimality gaps integer. Thus $k>m\ln f^{\ast }$ makes $F_k<1$ and hence $F_k=0$, giving termination in $\boxed{O(m\log f^{\ast })}$ augmentations for $f^{\ast }\ge 2$. If $f^{\ast }=1$, one positive integer augmentation suffices; if $f^{\ast }=0$, none is required. A uniform statement is $O(m\log (1+f^{\ast }))$. With $m=1$, a nonzero flow is also completed in one augmentation, consistent with the recurrence's zero contraction factor.

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.

An cut of a flow network partitions a flow network into $S,S^c$, with source $A\in S$ and sink $B\notin S$. Its cut capacity is the sum of capacities of arcs directed from $S$ to $S^c$; a minimum cut minimizes this sum.

Use the suggested nodes. Give $A\to a_e$ capacity $1$, each $a_e\to b_v$ capacity $M=m+kn+1$, and each $b_v\to B$ capacity $k$. By the max-flow min-cut theorem, a flow of value $kn$ exists once every cut capacity is at least $kn$.

Consider a cut of a flow network containing no crossing arc of capacity $M$, and let $U$ be the intersections on the sink side. Every street incident to $U$ must also be on that side, or its arc to an endpoint in $U$ would cross the cut of a flow network. Hence at least $d(U)$ source-to-street arcs cross, as do the $n-|U|$ intersection-to-sink arcs from the other intersections. Therefore its cut capacity is at leastA cut of a flow network crossing a capacity-$M$ arc has still larger capacity. The cut of a flow network just before the sink has capacity $kn$, proving the maximum flow value is exactly $kn$.

The integral max-flow theorem supplies an integral maximum flow. Every intersection sends $k$ units to the sink; each street can supply at most one unit, assigned to one endpoint. Orient each assigned street away from its assigned endpoint. Orient unassigned streets arbitrarily. Then each vertex has at least $k$ outgoing streets. An Ford-Fulkerson algorithm with integer capacities constructs this flow and therefore the street directions. Notice that the condition also is necessary: outgoing streets from vertices in $U$ are distinct edges incident to $U$, so $d(U)\ge k|U|$. This is an outdegree orientation criterion.

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.

Starting from zero, one valid run of the Ford-Fulkerson algorithm augments alongThe resulting nonzero edge flows areand they obey every capacity constraint and every flow-conservation equation. The flow value is

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]