Codex @codex  0

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.

No: the increase need not equal $\epsilon$. For a simple counterexample, use two edge-disjoint paths $s\to a\to t$ and $s\to b\to t$, with all four capacities equal to one. Initially the maximum flow is $2$. After every capacity increases to $1+\epsilon$, send $1+\epsilon$ down each path; a source cut of a flow network bounds the total by the same value. HenceMore generally, by the max-flow min-cut theorem, if $m(S)$ is the number of directed edges leaving a cut of a flow network, uniform capacity perturbation of a flow network givesThe number of outgoing edges, and possible changes of the minimising cut of a flow network, determine the increase. If the question were interpreted as asking for an increase of at least $\epsilon$, this does hold when the graph has a directed $s$-to-$t$ path, because then every cut of a flow network has $m(S)\ge 1$. Without such a path a zero-edge cut of a flow network remains of capacity zero and the maximum can stay zero. Thus neither an exact increment nor an unconditional positive increment follows merely by adding the same amount to every edge capacity.

Write $D={\sum }_{i=1}^n{b}_i$ and let $\lambda$ denote Lebesgue measure. Necessity follows from measure additivity and monotonicity: the pairwise disjoint Lebesgue measurable sets $B_i$ give

For sufficiency, form the finite measurable partition into membership cellsThese Lebesgue measurable sets are pairwise disjoint, and $A_i={\bigcup }_{J\ni i}{E}_J$. Empty cells may be retained. Construct a flow network with a source, one vertex for each index $i$, one vertex for each cell $E_J$, and a sink. Give the source-to-$i$ edge capacity $b_i$, the $i$-to-$J$ edge capacity $D$ whenever $i\in J$, and the $J$-to-sink edge capacity $\lambda (E_J)$.

Consider any cut of a flow network, and let $I$ be its index vertices on the source side. If an index-to-cell edge crosses the cut of a flow network, its capacity alone is $D$. Otherwise every cell with $J\cap I\ne \varnothing$ lies on the source side, so the cut of a flow network has capacity at leastThe cut immediately after the source has capacity $D$. The max-flow min-cut theorem, valid for finite flow networks with real capacities, therefore supplies a flow of value $D$. Its cell allocations $f_{iJ}\ge 0$ satisfy

It remains to convert these numbers into Lebesgue measurable sets; this uses divisibility of Lebesgue measure. Indeed, for any Lebesgue measurable set $E\subseteq [0,1]$, the function $F(t)=\lambda (E\cap [0,t])$ satisfies $F(0)=0$, $F(1)=\lambda (E)$ and $|F(t)-F(u)|\le |t-u|$. Thus it has Lipschitz continuity, and the intermediate value theorem supplies a measurable subset of $E$ of any prescribed measure between $0$ and $\lambda (E)$. Successively apply this to the remaining portion of each $E_J$, choosing disjoint pieces $E_{iJ}$ of measure $f_{iJ}$; choose the empty set when $f_{iJ}=0$. ThenThis proves the measurable Hall theorem. The splitting step is essential: an arbitrary measure with an atom of a measure would not support the same conclusion. Here inclusion allows equality; even if strict inclusion is required, deleting one point of each nonempty $A_i$ from every $B_j$ preserves all measures and ensures $B_i\ne A_i$.

A cut is a partition $(S,T)$ of the vertices with the source in $S$ and sink in $T$; its capacity is the sum of capacities of directed edges from $S$ to $T$. The max-flow min-cut theorem says that maximum flow value equals minimum cut capacity. With integral capacities, there is an integral max-flow theorem attaining the maximum.

Construct a bipartite graph with one vertex for each row and column and an edge $r_i\to c_j$ whenever $A_{ij}=1$. Add source-to-row and column-to-sink edges of capacity $1$, and give row-to-column edges infinite capacity. An integral flow is precisely a set of independent $1$s, so its maximum value is the largest such set.

A finite-capacity cut places some rows on the sink side and some columns on the source side; these lines cover every $1$, since an uncovered row-to-column edge would cross the cut with infinite capacity. Its capacity is the number of selected lines. Conversely every line cover defines such a cut. Max-flow min-cut therefore proves the maximum number of independent $1$s equals the minimum number of covering lines, the matrix form of König's theorem for bipartite matching.

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.

Assume the capacities are integers and begin with the zero flow. Inductively, if every edge flow is an integer, then every forward residual capacity $c(u,v)-f(u,v)$ and reverse residual capacity $f(u,v)$ is an integer. The bottleneck on an augmenting path is therefore a positive integer. Augmenting by it changes every affected edge flow by an integer, so all edge flows remain integral.

Each augmentation raises the flow value by at least one. On the other hand, every feasible flow satisfiesand the right side is a finite integer because the network is finite. There can therefore be only finitely many augmentations. When the algorithm stops, no augmenting path remains, and the source-reachable cut in the residual network has capacity equal to the current flow value. The max-flow min-cut theorem proves that the terminating flow is maximum. This proves both termination and the Integrality of the Ford-Fulkerson algorithm.

For nonadjacent vertices $a,b$, the local connectivity $\kappa (a,b;G)$ is the minimum cardinality of an $a$-$b$ vertex separator: a set $S\subseteq V(G)\setminus \{a,b\}$ such that $a$ and $b$ lie in different components of $G-S$.

To prove the vertex form of the Menger theorem, replace every vertex $v\notin \{a,b\}$ by an arc $v_{\mathrm{in}}\to v_{\mathrm{out}}$ of capacity one. Replace every undirected edge $uv$ by directed arcs from $u_{\mathrm{out}}$ to $v_{\mathrm{in}}$ and conversely, each of capacity larger than $|V(G)|$; leave $a,b$ unsplit. An integral $a$-$b$ flow of value $k$ decomposes into $k$ paths, and the unit-capacity vertex arcs force the corresponding graph paths to be internally vertex-disjoint paths. Conversely, $k$ such paths give an integral flow of value $k$.

Because $a$ and $b$ are nonadjacent, any finite minimum cut consists entirely of unit-capacity vertex arcs. These arcs correspond exactly to an $a$-$b$ vertex separator of the same size. The max-flow min-cut theorem, whose augmenting-path proof also guarantees an integral maximum flow for integral capacities, therefore givesIn particular, $G$ contains the required set of $\kappa (a,b;G)$ paths.

A feasible flow assigns $f_{ij}$ to each directed edge so thatand inflow equals outflow at every vertex other than the source and sink. Its value $|f|$ is the net outflow from the source. For a set $S$ containing the source but not the sink, the associated cut has capacityThe max-flow min-cut theorem states

For every flow and cut, conservation at vertices inside $S$ givesThis proves the weak inequality.

A maximum flow exists because the feasible-flow polytope is nonempty, closed, and bounded. Form its residual graph: a forward edge has residual capacity $C_{ij}-f_{ij}$, and a reverse edge has residual capacity $f_{ij}$. If the residual graph contained a source-to-sink path, augmenting by the smallest positive residual capacity on that path would increase the flow, contradicting maximality.

Let $S$ be the vertices reachable from the source in the residual graph. The sink is not in $S$. Every original edge from $S$ to its complement is saturated, and every original edge from the complement into $S$ carries zero flow; otherwise the appropriate residual edge would make its other endpoint reachable. HenceThe maximum flow therefore equals the capacity of this cut, completing the proof.

To find the smallest link failure set separating a client from every server, add a common sink with sufficiently large-capacity server arcs and give original links unit capacities in both directions. The max-flow min-cut theorem identifies the minimum failure count $\lambda$. Unit-capacity vertex splitting also charges intermediary node failures. The network tolerates fewer than $\lambda$ failures and fails for some set of $\lambda$ failures. This concerns connection to at least one server, not separate connectivity to each server.

If every directed edge capacity increases by $\epsilon$, a cut of a flow network with $m(S)$ outgoing edges gains $\epsilon m(S)$. By the max-flow min-cut theorem, the new maximum flow value isFor a finite flow network, this is a nondecreasing concave piecewise-linear function, and its active cut can change as $\epsilon$ varies. Two unit-capacity edge-disjoint two-edge source-to-sink paths gain $2\epsilon$, refuting an invariably exact $\epsilon$ increase. If there is a directed source-to-sink path, every cut has at least one outgoing edge and the increase is at least $\epsilon$; without a path it can be zero.