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.

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