---
title: "Cuts and Flows"
summary: The definitions, the capacity bound, and why "flow" and "cut" are the same optimisation seen from two sides.
difficulty: core
tags: [flow, cuts, duality]
prereq: [foundations/representation, directed/scc]
see: [flow/maxflow, flow/mincut-models]
---

:::definition label="Flow"
A directed graph with source $s$, sink $t$, and capacities $c(u,v) \ge 0$. A **flow** is $f : E \to \mathbb{R}_{\ge 0}$ with
1. **capacity**: $f(u,v) \le c(u,v)$,
2. **conservation**: $\sum_v f(v,u) = \sum_w f(u,w)$ for every $u \notin \{s,t\}$.
Its value is $|f| = \sum_v f(s,v) - \sum_v f(v,s)$. With antisymmetric $f$ (the convention in code: `f(u,v) = -f(v,u)`), conservation becomes $\sum_{v} f(v,u) = 0$ for internal $u$ and the value is just the net out-flow of $s$.
:::

:::definition label="Cut"
An **$s$–$t$ cut** is a partition $(S, \bar S)$ with $s \in S$, $t \in \bar S$; its capacity is
$$c(S, \bar S) = \sum_{u \in S, v \notin S} c(u,v)$$
— edges **forward only**. Backward edges do not count: they carry flow the other way, which *helps*, so ignoring them is the correct accounting.
:::

:::lemma title="Weak duality"
For every flow $f$ and every $s$–$t$ cut $(S,\bar S)$: $|f| \le c(S, \bar S)$.
:::

:::proof
$|f| = \sum_{u \in S, v \notin S} f(u,v) - \sum_{u \notin S, v \in S} f(u,v)$ — conservation makes all internal terms cancel when you sum the balance equations over $S$. Dropping the (non-negative) second sum and applying $f \le c$ on the first gives $|f| \le \sum_{u\in S, v\notin S} c(u,v)$. ∎
:::

:::theorem title="Max-flow min-cut"
$\max_f |f| = \min_{(S,\bar S)} c(S,\bar S)$, and both are attained. (Proof: @flow/maxflow — the min cut is read off the residual graph after saturation.)
:::

:::props title="The vocabulary you will need for every modelling problem"
- **residual capacity** $r(u,v) = c(u,v) - f(u,v) + f(v,u)$; an edge with $r > 0$ is a *residual edge*,
- an **augmenting path** is an $s \leadsto t$ path of residual edges; augmenting along it by the bottleneck increases $|f|$ by exactly that amount,
- a flow is **maximum** iff the residual graph has no $s \leadsto t$ path (integrality: if all capacities are integral, the algorithm keeps $f$ integral — this is why flow counts *things*),
- the **min cut** is $S = $ vertices reachable from $s$ in the final residual graph; it is the *smallest* such $S$ (source side) and its complement, the vertices that can reach $t$, is the largest — knowing which side is which settles a whole class of "which side does vertex $x$ belong to" questions.
:::

:::note title="What the theorem buys in modelling terms"
Flow algorithms are only as useful as the *encoding*: "the min cut of a network you built" equals the answer of a combinatorial problem. The recurring encodings, with their proofs of correctness all being "a cut is exactly a valid object here":
- project selection / maximum weight closure (@flow/mincut-models),
- minimum vertex cover in bipartite graphs = maximum matching (Kőnig, @matching/konig),
- "delete fewest edges/vertices so that $s$ and $t$ disconnect" — Menger, made algorithmic by unit capacities (@foundations/connectivity),
- binary energy minimisation with submodular pairwise terms — the graph cut of computer vision,
- Dilworth's theorem as a flow on a poset DAG (@directed/dag-toposort's chain-cover remark, made algorithmic in @matching/bipartite).
:::

:::figure src="Simple_Directed_Graph.svg" caption="A directed network is the same shape as any digraph: only the edge capacities are new. Given this graph, an s–t cut is a choice of which side each vertex lands on, and its cost is the sum of capacities of the edges that point across, forward only."
:::

:::problems
- [[CSES 1694]] Download Speed | https://cses.fi/problemset/task/1694 | core | max flow on a small dense graph — parallel edges must be summed
- [[CSES 1695]] Police Chase | https://cses.fi/problemset/task/1695 | core | edge-disjoint paths = unit-capacity max flow
:::