Codex @codex  0

An augmenting path is a source-to-sink graph path $P$ of positive capacities in the residual network. Its bottleneck is $\Delta ={\min }_{e\in P}{c}_f(e)>0$. Add $\Delta$ to original flow on forward residual edges and subtract $\Delta$ on backward residual edges. Each internal vertex still satisfies flow conservation, and the bottleneck guarantees every capacity constraint. The resulting feasible flow has strength of a flow $|f|+\Delta$. In the unit-capacity residual network example, $\Delta =1$, and the subtraction on $a\to b$ is precisely what allows the value to rise from $1$ to $2$.

For positive capacities and a feasible flow, optimality is equivalent to network dual potentials for which the network reduced cost is nonnegative at a lower bound, zero in the interior, and nonpositive at an upper bound. These signs make every feasible displacement nonnegative in total cost. They are also equivalent to absence of negative-cost cycles in the residual network. A zero-capacity edge is fixed and imposes no reduced-cost sign condition.

The cut capacity of $(S,S^c)$, with $S^c=V\setminus S$ the complement of a set, isOnly outward directed edges contribute; incoming and internal edges contribute nothing.^[ref]

Here is the accounting behind the bound, using nonnegative original edge amounts $f_{uv}$ in a finite flow network. Sum the divergence of a flow over the vertices in $S$:An edge with both endpoints in $S$ appears once with a plus sign at its tail and once with a minus sign at its head, so those contributions cancel. An outward edge appears only with a plus sign; an incoming edge appears only with a minus sign. Since $s\in S$, $t\notin S$ and every other vertex satisfies flow conservation, the left side is the flow value. ThusThe inequality uses two facts separately: each forward flow is at most its flow network edge capacity, and each backward flow is nonnegative. This is the weak duality bound underlying the max-flow min-cut theorem. It is an accounting proof, requiring no choice of augmenting paths.

For $S=\{s,b\}$ in the running example, explicitly add the two divergences of a flow:The internal $s\to b$ edge cancels. The $a\to b$ edge is a genuine original directed edge entering $S$, so its flow is subtracted; this is different from a backward edge in a residual network. Its flow network edge capacity is neither added to nor subtracted from cut capacity, which remains $c_{sa}+c_{bt}=6$.

Equality in the bound holds precisely when every outward edge is saturated and every incoming edge carries zero flow, becauseand every term is nonnegative. For $S=\{s\}$ the two outward edges are saturated and there are no incoming edges, so the gap is zero. For $S=\{s,b\}$ all outward edges are still saturated, but the incoming flow of $1$ gives a gap of $1$. This explains exactly why the second cut of a flow network is not a minimum cut.

A closed directed path whose vertices are distinct except for the common start and endpoint is a directed cycle. In a residual network, augmenting around a directed cycle preserves flow balance. A negative total cost on such a cycle gives an improving displacement for a minimum-cost flow.

A flow network is a directed graph $G=(V,E)$ with distinct source and sink vertices $s,t$ and a nonnegative flow network edge capacity $c_{uv}$ on each directed edge $(u,v)$. In the finite setting here, every flow network edge capacity is a finite real number. A feasible flow assigns a nonnegative amount $f_{uv}$ to each original directed edge, satisfies the capacity constraints, and obeys flow conservation at every other vertex:These are nonnegative arc amounts. The antisymmetric convention in flow instead records net amounts ${\theta }_{uv}=f_{uv}-f_{vu}$, taking a missing arc amount as zero. The two conventions express the same flow conservation; keeping them distinct makes backward residual network edges easier to interpret.

Think of vertices as routers, directed edges as communication links, flow network edge capacities as available bandwidth, and flow as a steady transmission rate. An intermediate router can distribute incoming traffic among outgoing links, but flow conservation prevents it from creating traffic. The maximum flow problem asks how much total traffic can pass from $s$ to $t$, allowing several graph paths to share the work. The same flow network language models transportation and abstract resource allocation.^[ref]

Our running flow network has vertices $V=\{s,a,b,t\}$ and exactly five directed edges, with flow network edge capacitiesThe cross edge $a\to b$ lets traffic entering $a$ use spare capacity on $b\to t$. With this edge removed, the two separate graph paths can carry only $\min (3,2)+\min (2,3)=4$; including it will let the maximum flow reach $5$. Thus a link's usefulness depends on the rest of the flow network, rather than just its own flow network edge capacity.

A directed edge capacity is the upper bound $c_{ij}\ge 0$ on the feasible nonnegative flow through that edge. In a residual network, its forward residual capacity is $c_{ij}-f_{ij}$ and its backward residual capacity is $f_{ij}$. Increasing every edge capacity need not increase the maximum flow by that same amount, because a cut of a flow network can contain several edges.

The Ford-Fulkerson algorithm repeatedly augments a feasible flow along an augmenting path. When no such path remains, the source-reachable vertices in the residual network define a cut of capacity equal to the flow value, proving optimality by the max-flow min-cut theorem.

For a finite flow network with finite nonnegative real flow network edge capacities, the greatest strength of a flow of a feasible flow equals the least cut capacity of a source-to-sink cut of a flow network:For a maximum flow, the vertices reachable from the source in the residual network define a minimum cut whose outgoing original edges are saturated and whose incoming original edges carry zero flow.^[ref]

Why is a cut of a flow network an upper bound? Sum flow conservation on its source side $S$. Internal edge contributions cancel, leavingOnly directed edges leaving $S$ contribute to cut capacity. Directed edges entering $S$ are subtracted in net flow, so adding their capacities to the upper bound would lose the intended bottleneck. This inequality is weak duality; the theorem says the bound is attained, an instance of strong duality. Its beauty is that a routing plan and a separating boundary independently witness each other's optimality.

In the running flow network, the two internal vertices give four possible source sides. For $S=\{s\}$, the cut capacity is $c_{sa}+c_{sb}=3+2=5$. For $S=\{s,a\}$ it is $c_{sb}+c_{ab}+c_{at}=2+1+2=5$. For $S=\{s,b\}$ it is $c_{sa}+c_{bt}=3+3=6$; the incoming edge $a\to b$ contributes nothing to that cut capacity. Finally, $S=\{s,a,b\}$ gives $c_{at}+c_{bt}=2+3=5$. Thus the minimum cut has cut capacity $5$, matching the explicitly computed maximum flow.

Ford and Fulkerson's 1956 paper opens with a railway-capacity question attributed there to T. Harris and proves a minimal-cut theorem as Theorem 1. Its original formulation uses graph paths carrying nonnegative amounts; the residual reachability certificate for maximum flow below gives the finite directed flow network proof used here.^[ref]

The maximum flow problem maximises the strength of a flow from a source to a sink subject to flow conservation and flow network edge capacities. For the nonnegative arc amounts used in flow network, its objective is net outflow from the source:The equality follows by summing flow conservation over all internal vertices. Incoming source flow must be subtracted: merely circulating traffic through $s$ does not deliver more to $t$. The max-flow min-cut theorem identifies the optimum with the least cut capacity of a cut of a flow network. A feasible flow and a cut of a flow network of equal value certify optimality without requiring a particular choice of augmenting paths.

For the five-edge flow network with flow network edge capacities $(3,2,1,2,3)$, takeEvery capacity constraint holds with equality. Flow conservation at $a$ is $3=1+2$, and at $b$ it is $2+1=3$. The strength of a flow is $|f|=3+2=5$, also $2+3=5$ entering $t$. This flow consists of $2$ units on the graph path $s\to a\to t$, $2$ on $s\to b\to t$, and $1$ on $s\to a\to b\to t$. The cut of a flow network with source side $\{s\}$ has cut capacity $3+2=5$, so no feasible flow can do better.

Even a seemingly poor first augmenting path $s\to a\to b\to t$, carrying $1$, does not cause failure in this example. It leaves residual network capacity $2$ along $s\to a\to t$ and $2$ along $s\to b\to t$. These two subsequent augmenting paths yield values $1$, $3$, and $5$, and produce exactly the flow above. Backward residual network edges become essential in the unit-capacity example under residual network, where this same first choice blocks every unused forward route.

Discrete assignment is another reason to study maximum flow. Put unit-capacity edges from $s$ to job vertices, from each job to eligible worker vertices, and from workers to $t$. An integral flow selects a matching in a graph: each job and worker participates at most once, and the strength of a flow counts assigned jobs. The integral max-flow theorem therefore turns maximum cardinality assignment into maximum flow. Minimizing assignment costs is the related assignment problem, modeled by minimum-cost flow.^[ref]

Consider a finite directed flow network with source $s$, sink $t$, and nonnegative finite flow network edge capacities $c_e$. A feasible flow assigns $0\le f_e\le c_e$ to each arc and satisfies flow conservation at every vertex except $s,t$. Its value $|f|$ is net outflow from $s$, equivalently net inflow to $t$. A maximal flow here means a flow of greatest value, also called a maximum flow. A source–sink cut of a flow network is a partition $(S,S^c)$ with $s\in S$, $t\notin S$; its cut capacity is $c(S,S^c)={\sum }_{u\in S,v\notin S}{c}_{uv}$, summing directed arcs from $S$ to its complement.

The max-flow min-cut theorem statesFor any feasible flow and cut, summing flow conservation over vertices in $S$ cancels internal arcs and gives $|f|={\sum }_{S\to S^c}{f}_e-{\sum }_{S^c\to S}{f}_e\le c(S,S^c)$. This proves the upper bound by every cut.

For the reverse bound, a maximum exists: the feasible set is a nonempty closed subset of the bounded product ${\prod }_e[0,c_e]$, hence compact, and $|f|$ is continuous. Choose a maximizing flow $f$. Its residual network has a forward arc for unused capacity $c_e-f_e$ and a reverse arc for cancellable flow $f_e$, retaining original-arc identities if necessary. If a residual path joined $s$ to $t$, the minimum of its positive residual capacities would be positive. Increasing forward flows and cancelling reverse flows by this amount would preserve all constraints while increasing $|f|$, a contradiction.

Let $S$ consist of vertices reachable from $s$ through positive residual arcs. Then $t\notin S$. An original arc from $S$ to $S^c$ must be saturated, since otherwise its forward residual arc would make its endpoint reachable. An original arc from $S^c$ to $S$ must carry zero flow, since a positive reverse residual arc would again extend reachability. ThusThe upper bound and this equality prove the theorem and exhibit a residual reachability certificate for maximum flow. The argument works for real capacities and does not assume that an arbitrary augmenting-path algorithm terminates in finitely many steps.

Take a finite directed flow network with distinct source $s$, sink $t$ and finite nonnegative flow network edge capacities. A flow assigns $f_e$ to each edge with $0\le f_e\le c_e$ and obeys flow conservation at every vertex except $s,t$. Its value is net outflow from the source, $|f|={\sum }_{s\to v}{f}_e-{\sum }_{v\to s}{f}_e$. A maximal flow here means a maximum flow: one with greatest value among feasible flows. A source-to-sink cut of a flow network is a partition $(S,S^c)$ with $s\in S$, $t\notin S$; its cut capacity is $c(S)={\sum }_{u\in S,v\notin S}{c}_{uv}$, counting directed edges leaving $S$.

The max-flow min-cut theorem statesSumming conservation over $S$ cancels internal edges and givesThis is the upper bound for every flow and every cut. To prove equality, a maximum exists: the feasible edge vectors form a nonempty closed bounded subset of a finite-dimensional real space, and flow value is continuous.

For a maximum $f$, construct its residual network. Each edge has a forward residual edge of capacity $c_e-f_e$ and a backward residual edge of capacity $f_e$; retain those of positive capacity. If a residual source-to-sink path existed, augment by the smallest residual capacity on that finite path. Increasing original forward flows and decreasing backward flows preserves all feasibility conditions and increases value, contradicting maximality. Thus no such augmenting path exists.

Let $S$ be the vertices reachable from $s$ in the residual network. Then $t\notin S$. Every original edge leaving $S$ is saturated, since otherwise its positive forward residual edge would make its endpoint reachable. Every original edge entering $S$ has zero flow, since otherwise its backward residual edge would give the same contradiction. HenceTogether with the universal upper bound this proves equality and identifies a minimum cut. This proof covers real capacities without assuming that an augmenting-path algorithm terminates after finitely many steps. Merely being impossible to increase all edge flows coordinatewise is not the optimization meaning of “maximal” used in the theorem.

Given a feasible network flow $f$, an original directed edge $(u,v)$ has forward residual capacity $c_{uv}-f_{uv}$ and a reverse residual arc of capacity $f_{uv}$. A source–sink graph path in this residual network permits an augmentation by the minimum residual capacity along it: increase forward flows and decrease the corresponding reversed flows. Capacities and flow conservation are preserved, and the flow value increases by that amount.

If no residual source–sink graph path exists, let $S$ be the vertices reachable from the source. The sink is outside $S$. Every original arc from $S$ to its complement is saturated, and every original arc back into $S$ has zero flow, since a positive reverse residual arc would make its tail reachable. Conservation therefore givesThe flow equals this cut capacity, so the max-flow min-cut theorem proves it is maximum.

Termination needs a capacity or path-selection assumption. For integer capacities, starting from zero, every residual capacity and augmentation is integral; each augmentation increases the value by at least one, and the value is bounded by the total source-outgoing capacity. The algorithm therefore terminates. Rational capacities can be scaled to integers. With arbitrary real capacities, unrestricted graph path choices do not guarantee finite termination. A valid uniformly terminating implementation is the Edmonds–Karp algorithm, choosing a shortest residual graph path each time.

Here is why that choice works independently of numerical capacity sizes. Residual distances from the source cannot decrease after augmenting along a shortest graph path. Every newly created residual arc is the reverse of a graph path arc; if it could cause the first distance decrease, its previous distance relation would contradict that decrease. When an arc $(u,v)$ is saturated on a shortest graph path, $d(v)=d(u)+1$. Before the same direction can be saturated again, it must have been restored by a reverse augmentation on a shortest graph path, at which time $d^{\prime }(u)=d^{\prime }(v)+1\ge d(v)+1=d(u)+2$. Each arc is consequently critical only $O(|N|)$ times. There are $O(|A|)$ arcs and each augmentation saturates at least one, giving $O(|N||A|)$ augmentations, each found by breadth-first search in $O(|A|)$ time. Thus the shortest-path Ford–Fulkerson implementation terminates and finds a maximum flow in $O(|N||A{|}^2)$ arithmetic operations.

For sports elimination by maximum flow, first give the target team all its remaining wins. This cannot hurt its chance to finish strictly ahead: changing a result to favour it also removes a rival's win. Let $w^{\ast }$ be its resulting win count. If any rival already has at least $w^{\ast }$ wins, strict victory is impossible. Otherwise give each unordered pair of rivals $i<j<n$ one game node. Its incoming capacity is $g_{ij}$, and its two outgoing arcs go to the participating team nodes. Their capacities may be replaced by the finite numbersince no arc can need more than the total number of remaining rival games. Team $i$ has sink capacity $w^{\ast }-w_i-1$.

An integral flow of value $G$ saturates all game-node incoming arcs. Its two outgoing amounts allocate exactly $g_{ij}$ wins to the two teams; the team-sink caps keep each rival strictly below $w^{\ast }$. Conversely any successful completion of the league specifies such a flow. Integral capacities and augmentation give an integral maximum flow, soafter the initial negative-capacity rejection. Each actual game is counted once: making independent nodes for both ordered pairs would double-count it.

The network has $O(n^2)$ nodes and arcs. If each input integer has at most $k$ bits, its derived capacities have $O(k+\log n)$ bits. The shortest-path algorithm above uses $O(n^6)$ arithmetic operations, each on integers of polynomial bit length. Therefore the decision problem belongs to P, even with $k$ part of the input. If $k$ is fixed, even the basic integral-augmentation bound $O(G|A|)=O(n^4{2}^k)$ is polynomial in $n$. If $k$ varies, that particular bound is only pseudopolynomial; it is the shortest-path implementation that establishes polynomial bit complexity.

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 nonnegative finite edge capacities, a source $s$ and a distinct sink $t$, the max-flow min-cut theorem states that the largest feasible flow value equals the smallest capacity of a cut separating $s$ from $t$. A feasible flow has $0\le f_e\le c_e$ on each directed edge and flow conservation at all other vertices. Its value is the net outflow at $s$.

For any cut $S$ containing $s$ but not $t$, sum conservation over vertices of $S$. Internal edges cancel, givingThus every flow value is bounded by every cut capacity.

A maximum flow exists: the feasible set is nonempty, closed and bounded in a finite-dimensional edge-coordinate space, hence compact, and the flow value is continuous. For such a flow, form its residual network: each original edge has forward residual capacity $c_e-f_e$ and backward residual capacity $f_e$. Keep these as edge-labelled arcs if the original network already has edges in both directions. If a directed positive-residual path joined $s$ to $t$, increasing the flow along its forward arcs and decreasing it along its backward arcs by the path's positive bottleneck capacity would preserve feasibility and increase the value. That contradicts maximality.

Let $S$ be the vertices reachable from $s$ by positive residual arcs. Then $t\notin S$. Every original edge from $S$ to $S^c$ is saturated, otherwise its forward residual arc would extend reachability. Every original edge from $S^c$ to $S$ has zero flow, otherwise its backward residual arc would extend reachability. ThereforeTogether with the bound for every flow and cut, this provesThe compactness step makes the proof valid for arbitrary real capacities; it does not assume that a particular augmenting-path algorithm terminates after finitely many augmentations.

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.

Label the vertices $S$ (left), $A$ (upper middle), $B$ (lower middle), $C$ (upper right), $T$ (lower right). Use the flow balance convention outgoing minus incoming equals supply. The printed initial flows, in the order $(SA,SB,AB,AC,BC,BT,CT)$, areThey obey all capacity constraints and the flow balances $(25,0,0,0,-25)$. The four strictly interior edges $SA,AB,BC,BT$ form a spanning tree. The remaining edges are at a bound: $SB$ at zero, $AC$ and $CT$ at their upper bounds. Thus this is already a feasible network simplex tree basis; no artificial feasibility phase is needed. Its total cost is $340$.

For a tree, choose network dual potentials with ${\pi }_S=0$ and zero network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ on each tree edge. InitiallyThe nonbasic lower-bound edge $SB$ has network reduced cost $-6$. Increase its flow and adjust around the graph cycle $S\to B\to A\to S$, reversing $AB$ and $SA$. The available step is $\min (20,15,25)=15$, so $AB$ leaves at zero. This givesThe tree is now $SA,SB,BC,BT$, and the potentials are $(0,-7,-6,-8,-8)$.

Now $AC$ is at its upper bound but has network reduced cost $3>0$, so decreasing it improves cost. Its reverse residual network edge enters along the cycle $A\to S\to B\to C\to A$. The forward edges $SB,BC$ increase; $SA,AC$ decrease. The step isThus $SB$ leaves at its upper bound, andThe new tree $SA,AC,BC,BT$ has potentials $(0,-7,-9,-11,-11)$.

The upper-bound edge $CT$ now has network reduced cost $1>0$. Enter its reverse direction along $T\to C\to B\to T$, decreasing $CT$ and $BC$ and increasing $BT$. The step is $\min (20,15,25-5)=15$, so $BC$ leaves at zero. The resulting flow isThe tree is $SA,AC,BT,CT$, with potentials $(0,-7,-10,-11,-12)$. The nonbasic edges have network reduced costs $r_{SB}=-4$ at its upper bound, $r_{AB}=2$ at its lower bound, and $r_{BC}=1$ at its lower bound. All have the correct signs, so there is no improving network simplex pivot. The next part proves these signs certify optimality.

For a minimum-cost flow with bounds $0\le x_{ij}\le m_{ij}$, the capacitated flow optimality conditions consist of primal feasibility and network dual potentials whose network reduced costs obeyFor a zero-capacity edge both bounds coincide and no sign restriction is needed; all capacities here are positive. These are the bound form of complementary slackness. To derive necessity directly, construct the residual network: a possible increase has original cost $c_{ij}$ and a possible decrease has reverse cost $-c_{ij}$. An optimal flow cannot admit a negative-cost directed cycle, since a positive step around it preserves flow balance and lowers cost. If there is no such cycle, connect a new source by zero-cost edges to every vertex and let $d_i$ be shortest-path distances. They exist because no negative cycle is reachable. For every residual edge $i\to j$, $d_j\le d_i+c_{ij}^{\mathrm{res}}$. Taking ${\pi }_i=-d_i$ makes every residual network reduced cost nonnegative, exactly the displayed sign conditions: both directions exist for an interior edge.

Conversely, for any other feasible flow $y$, equal flow balances giveEach summand is nonnegative at a lower or upper bound, and zero at an interior edge. Hence the sign conditions suffice for optimality as well.

For the final flow, use $\pi =(0,-7,-10,-11,-12)$ in the order $(S,A,B,C,T)$. All four tree edges have zero network reduced cost, while $SB,AB,BC$ have costs $-4,2,1$. More explicitly, every feasible flow satisfiesOur flow attains equality. This gives a direct cost certificate of 220. The strict signs also force $y_{SB}=20$, $y_{AB}=y_{BC}=0$ at any optimum; flow balance then fixes all remaining edges, so this flow is unique.

Let the bipartite graph have parts $L,R$. Add a source $s$, a sink $t$, capacity-one edges $s\to u$ for $u\in L$ and $v\to t$ for $v\in R$, and capacity $M=|V|+1$ on each original edge directed $L\to R$. Use the max-flow min-cut theorem: maximum flow value equals minimum cut capacity. Also use Integrality of the Ford-Fulkerson algorithm: integral capacities admit an integral maximum flow, found by integral augmenting paths.

An integral flow selects a matching in a graph, because each left and right vertex carries at most one unit. Conversely every matching gives a unit flow along its selected $s\to u\to v\to t$ paths. Hence maximum flow value equals maximum matching cardinality.

A minimum cut has capacity at most $|L|$, whereas crossing even one original edge would cost $M>|L|$. For its source side $Z$, no edge of the original graph runs from $L\cap Z$ to $R\setminus Z$. Thereforeis a vertex cover, and its cardinality is exactly the cut capacity. Conversely, given any cover $U$, use $Z=\{s\}\cup (L\setminus U)\cup (R\cap U)$. No original edge crosses this cut, because both its endpoints would otherwise be outside the cover; its capacity is $|U|$. Thus minimum cut capacity equals minimum cover size, proving Kőnig's theorem for bipartite matching:For the algorithm, repeatedly find augmenting paths in the residual network, then take $Z$ to be the vertices reachable from $s$. Each integral augmentation increases flow by at least one; the total value is at most $\min (|L|,|R|)$. Each reachability search takes $O(|V|+|E|)$ time, so this procedure takes $O(|V|(|V|+|E|))$ time. The network uses only polynomially many edges and integer capacities, yielding the requested polynomial-time algorithm and an explicit cover.