Flow network

A flow network is a directed capacitated graph with a source and sink. A feasible flow respects edge capacities and conserves flow at every other vertex.

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.

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. The max-flow min-cut theorem identifies the optimum with the least 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.

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.

This maximum flow algorithm repeatedly augments along a shortest residual path found by Breadth-first search. Residual distances from the source never decrease. If the same arc becomes saturated again after being restored by a reverse augmentation, the distance to its tail has increased by at least two. Thus each arc is critical only $O(|V|)$ times, yielding $O(|V||E|)$ augmentations. Each search costs $O(|E|)$, so the total time is $O(|V||E{|}^2)$. Termination with no residual source-sink path supplies a max-flow min-cut theorem certificate.

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.

Replace a vertex $v$ by $v_{\mathrm{in}},v_{\mathrm{out}}$ and an arc between them carrying its vertex capacity. Incoming arcs enter $v_{\mathrm{in}}$ and outgoing arcs leave $v_{\mathrm{out}}$. A path must cross that internal arc to use the vertex. This converts node-capacitated maximum flow to an ordinary flow network. For undirected mixed-failure cuts, normalize the source side so $v_{\mathrm{out}}$ inside implies $v_{\mathrm{in}}$ inside; then each original link contributes at most one crossing orientation.

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.

If a directed edge $e$ has capacity $c(e)$, a feasible flow satisfies $0\le f(e)\le c(e)$. In an antisymmetric-flow convention, this is encoded together with the residual capacity of the reverse orientation.

An source-to-sink cut is a partition $(A,V\setminus A)$ with the source in $A$ and the sink outside $A$. Its capacity is the sum of the capacities of directed edges leaving $A$.

A cut of a flow network of minimum cut capacity among cuts separating the prescribed source and sink. The max-flow min-cut theorem identifies this capacity with the maximum possible flow value.

The sum of arc capacities directed from the source side to the sink side of a cut of a flow network.

A flow is an antisymmetric function on directed edges whose divergence of a flow vanishes away from designated sources and sinks.

A unit flow from $a$ to $b$ is an antisymmetric flow with net outward strength of a flow one at $a$, net inward strength one at $b$, and zero divergence of a flow elsewhere. For a unit flow to infinity, only the finite source has nonzero divergence.

The divergence of a flow at a vertex is its total outward flow. Flow conservation means that this divergence vanishes at every interior vertex.

Flow conservation requires total inflow to equal total outflow at every vertex other than the source and sink, equivalently $\mathrm{div}f=0$ there.

The strength of a source-to-sink flow is the net amount leaving the source, equivalently the net amount entering the sink.

For unit edge resistances, the energy of a flow iswhere every unoriented edge is counted once.

An infinite locally finite connected graph is a transient graph exactly when it supports a unit flow from a vertex to infinity with finite energy of a flow.

The greatest value of a feasible source-to-sink flow equals the least capacity of a source-to-sink cut. For a maximum flow, the vertices reachable from the source in the residual graph define a cut whose forward edges are saturated and whose backward edges carry zero flow.

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.

A flow network with integer capacities has a maximum flow whose value on every edge is an integer. The augmenting-path algorithm proves this because every augmentation preserves integrality.

In a finite bipartite graph, the maximum size of a matching equals the minimum size of a vertex cover. It follows by representing matching as an integral flow and vertex covers as finite-capacity cuts.

For a feasible flow $f$, the residual network has forward residual capacity $c(u,v)-f(u,v)$ and reverse residual capacity $f(u,v)$. It records every local increase or cancellation that preserves the capacity constraints.

An augmenting path is a source-to-sink path of positive capacities in the residual network. Increasing the flow by the smallest residual capacity on the path gives another feasible flow of strictly greater value.

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.

Starting from the zero flow with integer capacities, every residual capacity and every augmenting bottleneck is an integer. Each augmentation therefore preserves integer edge flows and raises the flow value by at least one. Since the value is bounded by the total capacity leaving the source, the algorithm terminates after finitely many augmentations with an integral maximum flow.

If one edge leaving the source has capacity $x$, every cut capacity is affine in $x$ with coefficient zero or one. In the 2024 Cambridge Part IB example, cuts of capacities $x+5$ and $14$ are both sharp, giving