网络与流量

一个网络由有向图和每条边的容量 $u_{ij}\ge0$ 组成，另有源点 $s$ 与汇点 $t$。它可以是管道、道路、通信线路——凡是「有上限的输送」都能这么建模。

流给每条边一个数 $x_{ij}$，要求

$$0\le x_{ij}\le u_{ij}, \qquad \sum_{j}x_{ij}=\sum_{k}x_{ki}\quad(i\ne s,t),$$

即在中间节点进出相等（流量守恒）。流的值是汇点净流入：

$$z=\sum_{k}x_{kt}-\sum_{j}x_{tj}.$$

问题：怎样让 $z$ 最大？

课程先给了一个手工例子：一个五节点的网络，容量分别标在边上，靠不断找路径、能推多少推多少，最终得到 $9$ 单位的流。然后马上追问：怎么证明 $9$ 就是最大？

时间轴

割

图：五节点网络：边上的数字是流量/容量，虚线割的容量为 9。

把顶点分成两部分 $C$ 与 $\bar C$，使 $s\in C$、$t\in\bar C$。割容量定义为从 $C$ 指向 $\bar C$ 的边的容量之和：

$$\operatorname{cap}(C)=\sum_{i\in C,\ j\notin C} u_{ij}.$$

反方向的边不计入。

引理。 对任意流 $x$ 与任意割 $C$，

$$z\le\operatorname{cap}(C).$$

证明。 把从 $C$ 到 $\bar C$ 的净流出算两遍。一方面，由流量守恒，除 $s$ 之外的节点净流出为零，所以

$$\sum_{i\in C}\Big(\sum_j x_{ij}-\sum_k x_{ki}\Big) =\sum_{i\in C,\ j\notin C}x_{ij}-\sum_{i\in C,\ k\notin C}x_{ki} =z .$$

另一方面，第一项不超过对应容量 $\sum_{i\in C,j\notin C}u_{ij}$，第二项非负，所以 $z\le\operatorname{cap}(C)$。

于是上面的手工例子只需找到容量为 $9$ 的割，就能证明 $9$ 已是最优。课程指出三条特定的边恰好构成容量 $9$ 的割。

定理。 $\max z=\min_C\operatorname{cap}(C)$。

最大流的线性规划

变量：每条边的流量 $x_{ij}$，以及总流量 $z$。

$$\begin{aligned} \max\quad & z\\ \text{s.t.}\quad & x_{ij}\le u_{ij} &&\forall(i,j)\in E &&(\alpha_{ij}\ge0)\\ & \sum_{j}x_{ij}-\sum_{k}x_{ki}=0 &&\forall i\ne s,t &&(\beta_i\ \text{自由})\\ & z-\sum_{k}x_{kt}=0 && &&(\gamma\ \text{自由})\\ & x_{ij}\ge0 . \end{aligned}$$

第三行把「$z$ 等于流入汇点的总量」写成约束，这样目标函数就是一个单独的变量，取对偶时结构更整齐。

取对偶

对偶变量：容量约束配 $\alpha_{ij}\ge0$，守恒约束配 $\beta_i$（自由），$z$ 的约束配 $\gamma$（自由）。规定 $\beta_s=0$、$\beta_t=\gamma$，对偶写成

$$\min\;\sum_{(i,j)}u_{ij}\alpha_{ij}$$ $$\text{s.t.}\quad \alpha_{ij}+\beta_i-\beta_j\ge0\quad\forall(i,j)\in E, \qquad \beta_t\ge1,$$ $$\alpha_{ij}\ge0,\qquad \beta_i\ \text{自由}.$$

逐个变量看：$x_{ij}$ 出现在容量约束（系数 $1$）、节点 $i$ 的守恒式（系数 $+1$）、节点 $j$ 的守恒式（系数 $-1$），于是得到 $\alpha_{ij}+\beta_i-\beta_j\ge0$；$z$ 只出现在第三个等式（系数 $1$，移项后为 $\gamma$），得到 $\beta_t\ge1$。

$\beta_s=0$ 的理由：源点没有守恒约束，它对偶变量本不存在；把所有 $\beta$ 同时平移一个常数不改变差分 $\beta_i-\beta_j$，所以可以把 $\beta_s$ 规范成 $0$。

为什么 $\beta_t\ge1$？ 因为 $z$ 的系数是 $1$，对偶要求对应表达式不小于目标系数。若 $\beta_t$ 更大，可以把所有 $\beta$ 按比例缩小，目标值随之下降，所以最优时取 $\beta_t=1$。

从对偶解读出割

给定一组 $\beta$，为了让目标最小，$\alpha_{ij}$ 取到它允许的最小值：

$$\alpha_{ij}=\max\big(0,\ \beta_j-\beta_i\big).$$

于是对偶目标是

$$\sum_{(i,j)}u_{ij}\max(0,\beta_j-\beta_i).$$

关键观察。 若每个 $\beta_i$ 只取 $0$ 或 $1$，那么 $\max(0,\beta_j-\beta_i)$ 只在「$\beta_i=0$ 且 $\beta_j=1$」时等于 $1$，其余为 $0$。令

$$C=\{i:\beta_i=0\},$$

则 $s\in C$（因为 $\beta_s=0$）、$t\notin C$（因为 $\beta_t=1$），而目标恰是

$$\sum_{i\in C,\ j\notin C}u_{ij}=\operatorname{cap}(C).$$

也就是说，对偶的 0/1 解对应一个割，对偶目标就是割容量。

为什么最优解可以取 0/1

任取一个对偶可行解 $\beta$（$\beta_s=0$、$\beta_t=1$）。把 $\beta$ 的取值排序：

$$0=\tau_0<\tau_1<\cdots<\tau_k=1,$$

并令 $C_r=\{i:\beta_i\le\tau_r\}$。这样得到一串嵌套的割 $C_1\subseteq C_2\subseteq\cdots\subseteq C_k$，其中 $C_k$ 含 $s$ 不含 $t$。

一条从 $\beta_i$ 层跨到 $\beta_j$ 层的边，贡献 $\beta_j-\beta_i$ 乘容量；把它按经过的每一层拆开，恰好是每层「跨过该层的容量」乘以层间距。于是

$$\sum_{(i,j)}u_{ij}\max(0,\beta_j-\beta_i) =\sum_{r=1}^{k}(\tau_r-\tau_{r-1})\operatorname{cap}(C_r).$$

右边是若干割容量的凸组合（权重 $(\tau_r-\tau_{r-1})$ 非负且和为 $1$）。平均值不小于最小值，所以

$$\text{对偶目标}\ \ge\ \min_C\operatorname{cap}(C).$$

另一方面，取最小割对应的 0/1 指示 $\beta$，目标恰好等于该割容量。所以对偶最优值等于最小割容量。

收尾。 由线性规划强对偶，最大流的值等于对偶最优值，也就等于最小割的容量：

$$\max z=\min_C\operatorname{cap}(C).$$

整个证明没有任何组合技巧：写 LP、取对偶、证明对偶解可以取整数、再读出组合意义。

整数流与增广路径

观察。 容量是整数时，最小割容量是整数之和，所以最大流的值是整数。但「值」是整数不代表每条边上的流量都是整数——可能某条边是 $6.5$、另一条是 $1.5$，加起来仍是 $9$。

定理。 整数容量下，存在每条边流量都是整数的最大流。

增广路径算法。 从零流开始，反复做：

1. 在残量网络中找一条从 $s$ 到 $t$ 的路径；
2. 沿路径推送「路径上最小残量」那么多流量。

残量网络的定义是：若边 $(i,j)$ 的流量 $x_{ij}<u_{ij}$，则保留正向边，容量为 $u_{ij}-x_{ij}$；若 $x_{ij}>0$，则新增反向边 $(j,i)$，容量为 $x_{ij}$——反向边表示「可以把已经推过去的流量退回来」。

每一步推送的量是整数（最小残量由整数相减得到），所以流量始终保持整数。算法终止时得到整数流。

为什么「找不到增广路径」就等于最优？ 设当前流值为 $v$，在残量网络中从 $s$ 出发做广度优先搜索，令

$$C=\{\text{从 } s \text{ 可达的节点}\}.$$

因为 $t$ 不可达，所以 $t\notin C$，$C$ 是一个割。对每条从 $C$ 指向 $\bar C$ 的边，残量必为 $0$（否则 $\bar C$ 的端点会被搜索到），即 $x_{ij}=u_{ij}$；对每条从 $\bar C$ 指向 $C$ 的边，流量必为 $0$（否则反向残量边会让 $C$ 的端点被反向到达）。于是

$$v=\sum_{i\in C,j\notin C}x_{ij}=\sum_{i\in C,j\notin C}u_{ij}=\operatorname{cap}(C).$$

找到流值等于割容量的割，由前面的引理，$v$ 就是最大值。

补充：一个能说明「必须回退」的例子。 取 $s\to a$（容量 $3$）、$s\to b$（$2$）、$a\to b$（$2$）、$a\to t$（$2$）、$b\to t$（$3$）。若先把 $2$ 单位推过 $s\to a\to b\to t$，剩余可推的只有 $2$ 单位，总额 $4$。但真正的最大流是 $5$：$s\to a$ 走 $3$（其中 $2$ 到 $t$、$1$ 到 $b$）、$s\to b$ 走 $2$，两条汇入 $t$ 的边满载。要拿到 $5$，必须在残量网络里沿反向边 $b\to a$ 把最初的决定撤掉一部分——这正是残量网络存在的原因，也是「贪心地找路径」不够用的原因。

应用：König 定理

二分图 $G=(L\cup R,E)$。构造网络：

• 源点 $s$ 连到 $L$ 中每个顶点，容量 $1$；
• $L$ 到 $R$ 的每条边容量视为 $\infty$；
• $R$ 中每个顶点连到 $t$，容量 $1$。

最大流给出最大匹配。 由整数性，存在 0/1 最大流。每条中间边上的 $1$ 表示匹配选中了它；容量为 $1$ 的两端保证了每个顶点最多被一条匹配边使用。所以流值不超过最大匹配，而任意匹配都能对应一个同样大小的流，于是流值等于最大匹配大小。

最小割给出最小顶点覆盖。 割的容量有限时，它不会切断容量为 $\infty$ 的中间边，只能切断 $s\to v$（$v\in L$）或 $w\to t$（$w\in R$）这类容量为 $1$ 的边。把被切断的端点收集起来：

$$\text{顶点覆盖}=\{v\in L:\ s\to v\ \text{被切断}\}\cup\{w\in R:\ w\to t\ \text{被切断}\}.$$

若某条中间边 $vw$ 的两端都没被选，则 $s\to v\to w\to t$ 会是一条容量为正的增广路径，与「割已切断所有路径」矛盾。所以这个集合确实覆盖所有边，且大小等于割容量。

由最大流最小割，最大匹配等于最小顶点覆盖——这就是 König 定理。上一讲用 LP 的整数性证明了它，这一讲用网络流再证明一次；两条路线本质相同。

本节结论

• 流满足容量约束与节点守恒；流值是汇点的净流入。
• 对任意割，流值不超过割容量；最大流等于最小割。
• 最大流 LP 的对偶以顶点标号为变量，最优解可取 0/1，且恰好对应一个割。
• 对偶目标等于割容量，强对偶给出最大流最小割定理。
• 整数容量下存在整数最大流；增广路径算法可以构造出来。
• 找不到增广路径时，从 $s$ 可达的节点集给出一个紧的割。
• König 定理是最大流最小割在二分图上的特例。

理解检验

1. 定义割与割容量，并证明任意流的值不超过任意割的容量。

参考答案：割是顶点划分 $(C,\bar C)$，$s\in C$、$t\notin C$；割容量 $\operatorname{cap}(C)=\sum_{i\in C,j\notin C}u_{ij}$。对 $C$ 中所有节点求净流出之和，由守恒性，$C$ 内部边的流量相互抵消，只剩跨割的项，等于流值 $z$。其中从 $C$ 指向 $\bar C$ 的部分不超过对应容量之和，从 $\bar C$ 指向 $C$ 的部分非负，故 $z\le\operatorname{cap}(C)$。

2. 写出最大流的线性规划，并指出每条约束对应的对偶变量。

参考答案：$\max z$，约束 $x_{ij}\le u_{ij}$（对偶 $\alpha_{ij}\ge0$）、$\sum_j x_{ij}-\sum_k x_{ki}=0$（$\beta_i$ 自由）、$z-\sum_k x_{kt}=0$（$\gamma$ 自由）、$x_{ij}\ge0$。规范 $\beta_s=0$、$\beta_t=\gamma$ 后得到对偶 $\min\sum u_{ij}\alpha_{ij}$，约束 $\alpha_{ij}+\beta_i-\beta_j\ge0$、$\beta_t\ge1$。

3. 对偶最优解为什么可以取 $\beta_i\in\{0,1\}$？

参考答案：给定任意可行 $\beta$，取 $\alpha_{ij}=\max(0,\beta_j-\beta_i)$ 使目标最小。把 $\beta$ 的不同取值排序为 $0=\tau_0<\dots<\tau_k=1$，令 $C_r=\{i:\beta_i\le\tau_r\}$。每条边跨越的层数贡献可拆成各层的容量乘以层间距，于是对偶目标等于 $\sum_r(\tau_r-\tau_{r-1})\operatorname{cap}(C_r)$，是若干割容量的凸组合，因此不小于最小割。取最小割的 0/1 指示又恰好达到该值，所以存在 0/1 最优解。

4. 整数容量下，为什么一定存在每条边流量都是整数的最大流？

参考答案：最小割容量是整数之和，所以最大流值是整数；但这不自动保证每条边是整数。用增广路径算法从零流出发，每次在残量网络中推送「路径上最小残量」，整数相减仍是整数，所以流量始终是整数。算法在无增广路径时终止，此时流值等于可达集割的容量，故是最大流，且每条边都是整数。

5. 残量网络中找不到 $s$ 到 $t$ 的路径时，怎样构造最小割？

参考答案：令 $C$ 为残量网络中从 $s$ 可达的节点集。$t\notin C$，故 $(C,\bar C)$ 是割。对每条 $C\to\bar C$ 的边，残量为 $0$，即 $x_{ij}=u_{ij}$；对每条 $\bar C\to C$ 的边，流量为 $0$（否则其反向残量边会让起点可达）。于是当前流值 $v=\sum_{C\to\bar C}x_{ij}=\operatorname{cap}(C)$，由流不超过割容量可知 $v$ 就是最大值，这个割就是最小割。

与前后课的关系

上一讲把强对偶读成「两位玩家的最优策略」，这一讲把同一套流程读成「割」：LP 的原问题给出流，对偶给出割，强对偶就是最大流最小割。至此，「写 LP → 取对偶 → 证明整数性 → 读出组合意义」的模板已经完整走过三次（König 定理、极小极大定理、最大流最小割）。下一讲转向信息论，从熵与编码开始，结构会完全不同。

Networks and flows

A network is a directed graph with a capacity $u_{ij}\ge0$ on every edge, plus a source $s$ and a sink $t$. It can model pipes, roads or communication links — anything with bounded throughput.

A flow assigns a number $x_{ij}$ to each edge with

$$0\le x_{ij}\le u_{ij}, \qquad \sum_{j}x_{ij}=\sum_{k}x_{ki}\quad(i\ne s,t),$$

i.e. flow is conserved at intermediate vertices. Its value is the net inflow at the sink:

$$z=\sum_{k}x_{kt}-\sum_{j}x_{tj}.$$

The problem: maximise $z$.

The lecture first works a five-vertex example by hand, pushing flow along paths as far as each allows, and reaches $9$ units. It then immediately asks: how do you prove $9$ is maximal?

Timeline

Cuts

Figure：A five-node network: labels are flow/capacity; the dashed cut has capacity 9。

Split the vertices into $C$ and $\bar C$ with $s\in C$ and $t\in\bar C$. The capacity of the cut is the total capacity of edges pointing from $C$ to $\bar C$:

$$\operatorname{cap}(C)=\sum_{i\in C,\ j\notin C} u_{ij}.$$

Edges pointing backwards do not count.

Lemma. For every flow $x$ and every cut $C$,

$$z\le\operatorname{cap}(C).$$

Proof. Compute the net outflow from $C$ in two ways. On one hand, conservation kills every vertex except $s$, so

$$\sum_{i\in C}\Big(\sum_j x_{ij}-\sum_k x_{ki}\Big) =\sum_{i\in C,\ j\notin C}x_{ij}-\sum_{i\in C,\ k\notin C}x_{ki} =z .$$

On the other hand, the first term is at most $\sum_{i\in C,j\notin C}u_{ij}$, and the second is non-negative, so $z\le\operatorname{cap}(C)$.

Thus the hand-worked example proves its own optimality once a cut of capacity $9$ is exhibited; the lecture points to the three edges forming it.

Theorem. $\max z=\min_C\operatorname{cap}(C)$.

The linear program for maximum flow

Variables: a flow $x_{ij}$ per edge and the total value $z$.

$$\begin{aligned} \max\quad & z\\ \text{s.t.}\quad & x_{ij}\le u_{ij} &&\forall(i,j)\in E &&(\alpha_{ij}\ge0)\\ & \sum_{j}x_{ij}-\sum_{k}x_{ki}=0 &&\forall i\ne s,t &&(\beta_i\ \text{free})\\ & z-\sum_{k}x_{kt}=0 && &&(\gamma\ \text{free})\\ & x_{ij}\ge0 . \end{aligned}$$

The third line writes "$z$ equals the total inflow at the sink" as a constraint, so the objective is a single variable and the dual comes out tidily.

Taking the dual

Dual variables: $\alpha_{ij}\ge0$ for capacities, free $\beta_i$ for conservation, free $\gamma$ for the $z$ constraint. Setting $\beta_s=0$ and $\beta_t=\gamma$, the dual is

$$\min\;\sum_{(i,j)}u_{ij}\alpha_{ij}$$ $$\text{s.t.}\quad \alpha_{ij}+\beta_i-\beta_j\ge0\quad\forall(i,j)\in E, \qquad \beta_t\ge1,$$ $$\alpha_{ij}\ge0,\qquad \beta_i\ \text{free}.$$

Check: $x_{ij}$ appears in its capacity constraint (coefficient $1$), in the conservation row of $i$ ($+1$) and of $j$ ($-1$), giving $\alpha_{ij}+\beta_i-\beta_j\ge0$; $z$ appears only in the third equality (coefficient $1$, moved to $\gamma$), giving $\beta_t\ge1$.

Why $\beta_s=0$? The source has no conservation constraint, so its dual variable does not exist; and shifting all $\beta$ by a constant leaves the differences $\beta_i-\beta_j$ unchanged, so $\beta_s$ can be normalised to $0$.

Why $\beta_t\ge1$? Because $z$ has coefficient $1$ in the objective, and duality requires the corresponding expression to be at least the objective coefficient. If $\beta_t$ were larger, scaling all $\beta$ down would lower the objective, so the optimum has $\beta_t=1$.

Reading cuts out of the dual

Given $\beta$, the objective is minimised by taking each $\alpha_{ij}$ as small as allowed:

$$\alpha_{ij}=\max\big(0,\ \beta_j-\beta_i\big),$$

so the dual objective is

$$\sum_{(i,j)}u_{ij}\max(0,\beta_j-\beta_i).$$

Key observation. If every $\beta_i$ is $0$ or $1$, then $\max(0,\beta_j-\beta_i)$ equals $1$ exactly when $\beta_i=0$ and $\beta_j=1$, and $0$ otherwise. Let

$$C=\{i:\beta_i=0\}.$$

Then $s\in C$ (since $\beta_s=0$) and $t\notin C$ (since $\beta_t=1$), and the objective is precisely

$$\sum_{i\in C,\ j\notin C}u_{ij}=\operatorname{cap}(C).$$

So a 0/1 dual solution is a cut, and the dual objective is its capacity.

Why the optimum can be taken 0/1

Take any dual feasible $\beta$ with $\beta_s=0$, $\beta_t=1$. Sort its distinct values:

$$0=\tau_0<\tau_1<\cdots<\tau_k=1,$$

and let $C_r=\{i:\beta_i\le\tau_r\}$. This gives nested cuts $C_1\subseteq C_2\subseteq\cdots\subseteq C_k$, with $C_k$ containing $s$ but not $t$.

An edge from level $\beta_i$ to level $\beta_j$ contributes $(\beta_j-\beta_i)$ times its capacity; splitting that difference across the layers it crosses gives, layer by layer, the capacity crossing that layer times the gap between layers. Hence

$$\sum_{(i,j)}u_{ij}\max(0,\beta_j-\beta_i) =\sum_{r=1}^{k}(\tau_r-\tau_{r-1})\operatorname{cap}(C_r).$$

The right side is a convex combination of cut capacities (the weights are non-negative and sum to $1$), and an average is at least the minimum, so

$$\text{dual objective}\ \ge\ \min_C\operatorname{cap}(C).$$

Conversely, the 0/1 indicator of a minimum cut attains exactly that cut's capacity. Therefore the dual optimum equals the minimum cut.

Conclusion. Strong LP duality gives

$$\max z=\min_C\operatorname{cap}(C).$$

Nothing in the proof is a combinatorial trick: write the LP, take the dual, show the dual optimum is integral, then read off the combinatorial meaning.

Integral flows and augmenting paths

Observation. With integer capacities the minimum cut is an integer sum, so the maximum flow value is an integer. But an integer value does not mean every edge carries an integer — one edge could carry $6.5$ and another $1.5$ and still sum to $9$.

Theorem. With integer capacities there is a maximum flow whose edge flows are all integers.

The augmenting-path algorithm. Start from the zero flow and repeat:

1. find a path from $s$ to $t$ in the residual network;
2. push along it the smallest residual capacity on the path.

The residual network is defined as follows: if edge $(i,j)$ carries $x_{ij}<u_{ij}$, keep a forward edge of capacity $u_{ij}-x_{ij}$; if $x_{ij}>0$, add a backward edge $(j,i)$ of capacity $x_{ij}$, meaning "the flow already sent can be sent back".

Each augmentation pushes an integer amount (a minimum of integers), so the flow stays integral. When the algorithm stops, the flow is integral and maximum.

Why does "no augmenting path" mean optimal? Let the current flow have value $v$ and run breadth-first search from $s$ in the residual network. Set

$$C=\{\text{vertices reachable from } s\}.$$

Since $t$ is unreachable, $t\notin C$ and $(C,\bar C)$ is a cut. Every edge from $C$ to $\bar C$ has zero residual (else its far endpoint would be reachable), i.e. $x_{ij}=u_{ij}$; every edge from $\bar C$ to $C$ carries zero flow (else its backward residual edge would make its tail reachable). Therefore

$$v=\sum_{i\in C,j\notin C}x_{ij}=\sum_{i\in C,j\notin C}u_{ij}=\operatorname{cap}(C).$$

A flow whose value equals a cut's capacity is maximum by the lemma, and that cut is a minimum cut.

Note: an example where flow must be undone. Take $s\to a$ (capacity $3$), $s\to b$ ($2$), $a\to b$ ($2$), $a\to t$ ($2$), $b\to t$ ($3$). Pushing $2$ units along $s\to a\to b\to t$ first leaves room for only $2$ more units, total $4$. The true maximum is $5$: send $3$ along $s\to a$ (two to $t$, one to $b$) and $2$ along $s\to b$, filling both edges into $t$. Reaching $5$ requires sending flow backwards along $b\to a$ in the residual network, cancelling part of the first decision. This is why the residual network — and not greedy path-finding — is the right object. (This example is supplied for illustration; the lecture's worked network is larger.)

Application: König's theorem

Let $G=(L\cup R,E)$ be bipartite. Build a network:

• an edge from $s$ to each $v\in L$ of capacity $1$;
• an edge $v\to w$ of capacity $\infty$ for each original edge $vw\in E$;
• an edge from each $w\in R$ to $t$ of capacity $1$.

Maximum flow gives a maximum matching. By integrality there is a 0/1 maximum flow. An intermediate edge carrying $1$ is a matched edge; the unit capacities at both ends ensure no vertex is used twice. So the flow value is at most the maximum matching, and any matching yields a flow of the same size; they are equal.

Minimum cut gives a minimum vertex cover. A finite cut cannot cut an infinite intermediate edge, so it cuts only edges $s\to v$ ($v\in L$) or $w\to t$ ($w\in R$). Collect the endpoints:

$$\text{cover}=\{v\in L:\ s\to v\ \text{is cut}\}\cup\{w\in R:\ w\to t\ \text{is cut}\}.$$

If some edge $vw$ had neither endpoint chosen, then $s\to v\to w\to t$ would be a path of positive capacity, contradicting that the cut separates $s$ from $t$. So the set covers every edge and its size equals the cut capacity.

By max-flow min-cut, maximum matching equals minimum vertex cover — König's theorem. The previous lecture proved it through LP integrality; this is the same fact seen through flows.

What this lecture establishes

• A flow obeys capacities and conservation; its value is the net inflow at the sink.
• Any flow is bounded by any cut; maximum flow equals minimum cut.
• The dual of the max-flow LP is over vertex labels; its optimum can be taken 0/1 and describes a cut.
• The dual objective is the cut capacity, so strong duality proves max-flow min-cut.
• Integer capacities admit an integral maximum flow, constructible by augmenting paths.
• When no augmenting path remains, the vertices reachable from $s$ form a tight cut.
• König's theorem is max-flow min-cut specialised to bipartite graphs.

Comprehension check

1. Define a cut and its capacity, and prove that any flow is bounded by any cut.

Reference answer: A cut is a partition $(C,\bar C)$ with $s\in C$, $t\notin C$; its capacity is $\operatorname{cap}(C)=\sum_{i\in C,j\notin C}u_{ij}$. Summing the net outflow over all vertices of $C$, conservation cancels internal edges and leaves the flow value $z$. The part from $C$ to $\bar C$ is at most the corresponding capacity sum, and the part from $\bar C$ to $C$ is non-negative, so $z\le\operatorname{cap}(C)$.

2. Write the max-flow LP and name the dual variable attached to each constraint.

Reference answer: $\max z$ subject to $x_{ij}\le u_{ij}$ (dual $\alpha_{ij}\ge0$), $\sum_j x_{ij}-\sum_k x_{ki}=0$ (free $\beta_i$), $z-\sum_k x_{kt}=0$ (free $\gamma$), $x_{ij}\ge0$. Normalising $\beta_s=0$ and $\beta_t=\gamma$ gives the dual $\min\sum u_{ij}\alpha_{ij}$ with $\alpha_{ij}+\beta_i-\beta_j\ge0$ and $\beta_t\ge1$.

3. Why can the dual optimum be taken with $\beta_i\in\{0,1\}$?

Reference answer: For any feasible $\beta$, the objective is minimised by $\alpha_{ij}=\max(0,\beta_j-\beta_i)$. Sort the distinct values as $0=\tau_0<\dots<\tau_k=1$ and set $C_r=\{i:\beta_i\le\tau_r\}$. Each edge's contribution splits across the layers it crosses, so the objective equals $\sum_r(\tau_r-\tau_{r-1})\operatorname{cap}(C_r)$ — a convex combination of cut capacities, hence at least the minimum cut. The 0/1 indicator of a minimum cut attains that value, so a 0/1 optimum exists.

4. With integer capacities, why must an integral maximum flow exist?

Reference answer: The minimum cut is a sum of integers, so the maximum flow value is an integer — but that alone does not make each edge integral. The augmenting-path algorithm starts from the zero flow and always pushes the minimum residual along a path, a difference of integers, so the flow stays integral. It stops only when no augmenting path remains, at which point the flow equals a cut capacity and is therefore maximum.

5. When no $s$–$t$ path remains in the residual network, how do you construct a minimum cut?

Reference answer: Let $C$ be the set of vertices reachable from $s$ in the residual network. Since $t\notin C$, $(C,\bar C)$ is a cut. Every edge $C\to\bar C$ has zero residual, so $x_{ij}=u_{ij}$; every edge $\bar C\to C$ carries zero flow (otherwise its backward residual edge would make the tail reachable). Hence the current value $v=\sum_{C\to\bar C}x_{ij}=\operatorname{cap}(C)$, and since no flow exceeds any cut, $v$ is maximal and this cut is minimal.

Relation to neighbouring lectures

The previous lecture read strong duality as two players' optimal strategies; this lecture reads the same pipeline as a cut — the primal gives the flow, the dual gives the cut, and strong duality is max-flow min-cut. The template "write the LP, take the dual, prove integrality, read off the combinatorial meaning" has now run three times (König's theorem, the minimax theorem, max-flow min-cut). The next lecture turns to information theory, starting from entropy and coding, with a quite different structure.