Codex @codex  0

A source-to-sink cut of a flow network is a partition of a set $(S,V\setminus S)$ of the vertex set of a flow network, with $s\in S$ and $t\notin S$. Its cut capacity sums the flow network edge capacities of directed edges leaving $S$.^[ref]

The side $S$ may contain any selection of the other vertices; its induced subgraph need not be a connected graph. For the five-edge flow network with flow network edge capacities $(c_{sa},c_{sb},c_{ab},c_{at},c_{bt})=(3,2,1,2,3)$, $S=\{s\}$ gives the partition of a set $(\{s\},\{a,b,t\})$. Only $s\to a$ and $s\to b$ leave this side, so its cut capacity is $3+2=5$. Choosing $S=\{s,b\}$ instead puts $a\to b$ across the boundary in the incoming direction: its flow network edge capacity is excluded.

The left panel pairs a feasible flow of flow value $5$ with a cut of a flow network of cut capacity $5$, proving that each is optimal. The right panel uses the same feasible flow but a different cut of a flow network: the outward flow is $3+3=6$ and the backward flow is $1$, giving net flow $6-1=5$. That cut capacity is $6$, so it supplies a valid but less sharp bound. The dashed boundary marks a partition of a set, rather than an additional edge or a proposed route.

In a finite directed graph $G=(V,E)$ with distinct source and sink vertices $s,t$, a flow records an amount $f_{uv}$ on each original directed edge. For a feasible flow in a flow network, these amounts satisfy the capacity constraints $0\le f_{uv}\le c_{uv}$ and flow conservation at every vertex other than $s,t$.^[ref]

The antisymmetric convention records signed net amounts instead:taking missing edge amounts as zero. The paired signs describe one net transfer, rather than two independent transfers.^[ref]

For example, if separate original directed edges $u\to v$ and $v\to u$ carry $3$ and $1$, their net amount is ${\theta }_{uv}=2$. This signed record loses the separate amounts: $f_{uv}=2$, $f_{vu}=0$ would give the same net amount. When checking capacity constraints on actual edges, keep the original amounts or specify the signed bounds carefully; when summing flow conservation, either record gives the same divergence of a flow.

For the running flow network, choose the original edge amountsEvery capacity constraint holds. At $a$, incoming flow $3$ equals outgoing flow $1+2$; at $b$, incoming flow $2+1$ equals outgoing flow $3$. This feasible flow has flow value $5$, computed at $s$ or $t$.

The total of all five edge amounts is $11$, but the flow value is $5$. A unit passing through several edges appears several times in that total. Concretely, route $2$ units along each of the directed paths $s\to a\to t$ and $s\to b\to t$, and $1$ along $s\to a\to b\to t$. Their delivered amounts sum to $2+2+1=5$, while their edge usages sum to $2\cdot 2+2\cdot 2+1\cdot 3=11$. The cut of a flow network $S=\{s\}$ certifies that this delivery rate is already a maximum flow.

Flow conservation is useful because it makes a local ledger predict a global delivery rate: intermediate vertices only redistribute the resource. An additional network circulation can change the individual edge amounts without changing the flow value. Counting net delivery rather than total edge usage prevents such recirculation from masquerading as increased output.

A minimum cut is a cut of a flow network of least cut capacity for the prescribed source $s$ and sink $t$. The max-flow min-cut theorem equates that least cut capacity with the greatest flow value.^[ref]

To certify a particular minimum cut, exhibit a feasible flow whose flow value equals its cut capacity. Every feasible flow is bounded above by every cut capacity, so this single equality proves both optimalities.^[ref]

In the running example, the four possible source sides $\{s\}$, $\{s,a\}$, $\{s,b\}$ and $\{s,a,b\}$ have cut capacities $5,5,6,5$, respectively. The feasible flow of flow value $5$ therefore certifies three different minimum cuts. A minimum cut need not be unique; the optimum cut capacity is the same for all of them. Merely saturating many edges does not give this certificate: flow conservation and the particular cut of a flow network must also be checked.

The strength of a flow, also called its flow value, is net outflow from $s$, equivalently net inflow to $t$:The notation $|f|$ denotes this signed value, rather than an absolute value.^[ref]

The equality follows by summing the divergence of a flow over all vertices: the internal vertices contribute zero by flow conservation, while every edge cancels between its two endpoints. Hence $\mathrm{div}f(s)=-\mathrm{div}f(t)$. For the running flow, $|f|=3+2=2+3=5$.

Net outflow matters even when the source has incoming edges. As a separate example, give $s\to a$, $a\to s$ and $s\to t$ flow network edge capacities $2,2,3$ and flow amounts $2,2,3$. At $a$, flow conservation reads $2=2$. The source sends $5$ units along outgoing edges but receives $2$ back, so the flow value is $5-2=3$, exactly the amount arriving at $t$. The two-edge network circulation through $a$ raises total edge usage without increasing net delivery.