最大流最小割定理

最大流最小割定理是最优化理论的定理。根据该定理，在一个网络流中，从源点到汇点的最大的流量，等于它的最小割中每一条边的容量之和。“割”指的是一种边的集合，如果移除这个集合的全部边，就会断开源点和汇点的连接。

最大流最小割定理是线性规划中的对偶问题的一种特殊情况，并且可以用来推导门格尔定理和König–Egerváry定理。

## 定义

最大流和最小割定理是图论的一部分，因此为了准确定义，我们需要先定义图、流、割，然后再定义这个定理。

### 图

设 $G=(V,E)$ 为一个有向图，其中有一个起源点 $s$ 和一个超汇点 $t$，代表 $s$ 是所有流的源头，$t$ 是所有流的终点。这个图的每一条边都有一个容量 c : E → R+，记做 $c_{uv}$ 或者 $c(u,v)$，代表着能通过边 $(u,v)$ 的最大流量。

### 最大流

定义：流量代表一种映射 $f:E \rightarrow \mathbb{R}^+$，记做$f_{uv}$ 或者 $f(u,v)$，代表通过边 $(u,v)$ 的流量。每一条边所通过的流有以下两个限定条件：

- 流量限制：$f_{uv} \le c_{uv} \quad \forall\, (u,v)\in E.$ 也就是说，一条边上的流量不可以超过它的容量。
- 流量守恒：$\sum\nolimits_{\{ u : (u,v)\in E\}} f_{uv} = \sum\nolimits_{\{w : (v,w)\in E\}} f_{vw} \quad \forall\, v \in V\setminus\{s,t\}.$ 也就是说，除了源点和汇点以外，进入一个节点的流量等于流出这个节点的流量，节点内不能保存流。

规定在一个图中，流的值是

$$|f| = \sum\nolimits_{v:(s,v) \in E} f_{sv} = \sum\nolimits_{v:(v,t) \in E} f_{vt}.$$

也就是说，一个图的流是自其源点流出的流量之和，也是向其汇点流入的流量之和。或者说，由源点向汇点移动多少内容，这个图的流就是多少。

最大流问题：计算$|f|$的最大值，即从$s$到$t$的最大流量。

### 最小割

定义： s-t割 $C=(S,T)$ 将图 $G$ 完全划分为两部分，使得 $s \in S, t \in T,$ 也就是一侧有源，一侧有汇。$C$ 的割集 $X_C$ 是 $\{ (u, v) \in E \ : \ u \in S, v \in T \}.$ 也就是说，一条边当且仅当骑在这个划分方法上，一个节点位于划分出来的源侧，另一个位于汇侧，那么它包含在 $X_C$ 里。因此如果 $C$ 的割集是空集，或者我们把一个割集里的边全都从图中拿走，则 $|f| = 0$。通俗地说，割集就是一个图的断面，而割则是划分断面的方法。

规定在一个图中，s-t割的容量是

$c (S,T) = \sum\nolimits_{(u,v) \in X_C} c_{uv} = \sum\nolimits_{(i,j) \in E } c_{ij}d_{ij},$ 其中当 $i \in S,j \in T$ 时，$d_{ij}$ 为 $1$, 否则为 $0$。

通俗地说，割的容量就是断面中所有边的总容量。

最小 s-t 割问题：计算 $c(S,T)$ 的最小值。即找到一种割法，使割的容量最小。也就是说，找到通过能力最弱的断面。

### 主定理

可以证明一切流都不能超过任何s-t割，所以经过图的最大流就是图的最小割。我们直观上就可以知道，通过能力最弱的断面就是整个网络的最大流量。这个理论把最大流问题和最小割问题联系了起来。

## 线性规划公式

最大流最小割问题可以被看做为一对线性规划对偶问题。

最大流（原问题）｜最小割（对偶问题）

变量｜$f_{uv}$ $\forall (u,v)\in E$ 每条边一个变量｜$d_{uv}$ $\forall (u,v)\in E$ 每条边一个变量 $z_{v}$ $\forall v\in V\setminus \{s,t\}$ 每个非源点、非汇点一个变量

目标函数｜最大化 $\sum\nolimits_{v: (s,v)\in E} f_{sv}$ 最大化从源点流出的总流量｜最小化 $\sum\nolimits_{(u,v) \in E } c_{uv}d_{uv}$ 最小化割中边的总容量

约束条件｜满足： :$\begin{align} f_{uv} & \leq c_{uv} && \forall (u, v) \in E \\ \sum_{u} f_{uv} - \sum_{w} f_{vw} & = 0 && v \in V\setminus \{s,t\} \end{align}$ 每条边一个约束，每个非源点、非汇点一个约束｜满足： :$\begin{align} d_{uv} - z_u + z_v & \geq 0 && \forall (u, v) \in E, u\neq s, v\neq t \\ d_{sv} + z_v & \geq 1 && \forall (s, v) \in E, v\neq t \\ d_{ut} - z_u & \geq 0 && \forall (u, t) \in E,u\neq s \\ d_{st} & \geq 1 && \text{若 } (s, t) \in E \end{align}$ 每条边一个约束

符号约束｜$\begin{align} f_{uv} & \geq 0 && \forall (u, v) \in E\\ \end{align}$｜$\begin{align} d_{uv} & \geq 0 && \forall (u, v) \in E \\ z_v & \in \R && \forall v \in V\setminus \{s,t\} \end{align}$

最大流的线性规划公式是容易理解的，对于最小割的线性规划公式的理解如下：

$$d_{uv} = \begin{cases} 1, & u \in S , v \in T \\ 0, & \text{Otherwise} \end{cases}$$

$$z_{u} = \begin{cases} 1, & u \in S \\ 0, & \text{Otherwise} \end{cases}$$

最小化目标是使在割中的边最小。

下列限制保证了这些变量可以确保一个合法的割。

- 限制 $d_{uv} - z_u + z_v \geq 0$(即 $d_{uv} \geq z_u - z_v$) 确保了对两个非源点或汇点 u,v, 如果u 在 S中 且 v 在 T中, 那么边 (u,v)一定会被记在割中 ($d_{uv} \geq 1$)。
- 限制 $d_{sv} + z_v \geq 1$(即 $d_{sv} \geq 1 - z_v$) 确保了如果 v 在 T 中, 那么边 (s,v) 一定会被记在割中。
- 限制 $d_{ut} - z_u \geq 0$(即 $d_{ut} \geq z_u$) 确保了 u 在 S 中, 那么边 (u,t) 一定会被记在割中。

需要注意的是，这是一个最小化问题，我们不需要确保一条边不在割里，我们只要保证每条应当在割里的边被计算了。

注意到在给定的 s-t 割 $C = (S,T)$ 中，如果 $i \in S$ 那么 $z_i = 1$ 并且 0 反之。所以 $z_s$ 应该等于 1 并且 $z_t$ 应该等于0。由线性规划中的强对偶定理推得最大流最小割问题中的等式，也就是说如果原问题有一个最优解 x*，则对应问题也有一个最优解 y*，并且两个解相等。

## 举例

<image>

上图是一个网络，上有流量为 7 的流。令 S 集合和 T 集合分别包含所有白色和灰色的点，从而形成了一个割集包含图中虚线的 s-t 割，并且其容量为 7，与流量相同。故由大流最小割定理知，前述的流与 s-t 割皆达到流量及容量的极值。

## 应用

### 广义最大流最小割定理

额外规定映射 $c \colon V \rightarrow R^+$为点的容量，记做 c(v)，使得一个流 f 不只要满足边的流量限制与流量守恒，还要满足点的流量限制，即

$$\forall v \in V \setminus \{s,t\} : \qquad \sum\nolimits_{\{u\in V\mid (u,v)\in E\}} f_{uv} \le c(v).$$

换句话说，流过 v 点的总流量不能超过 v 的容量 c(v)。一个 s-t 割 的定义为一个包含一些点和边的集合，满足与任一条由 s 到 t 的路径皆不互斥。并且 s-t 割的容量 定义成所有点和边的容量总和。

在此定义之下，广义最大流最小割定理的叙仍为流量的最大值等于所有 s-t 割的容量最小值。

### 门格尔定理

不共边路径问题为给定无向图 $G=(V,E)$ 及两顶点 s、t，求从 s 到 t 彼此没有共同边的路径数量的最大值。

门格尔定理的叙述为从 s 到 t 彼此没有共同边的路径数量的最大值等于在所有 G 的 s-t 割(以原本的定义)中，顶点分别在不同集合的边数的最小值。

### 计划选择问题

<image>

计划选择问题叙述如下：当下有 n 个计划 $p_1, \dots ,p_n$可以被实施、m 种设备 $q_1, \dots ,q_m$ 可以被购买，要执行计划必须拥有该计划要求的设备，执行计划 $p_i$可获得 $r(p_i)$ 的收益，但购买设备 $q_j$ 要支付 $c(q_j)$ 的费用。如何选择执行计划并购买所需设备以获得净利的最大值？

设 P 为不被执行的计划的集合，Q 为所购买的设备，则问题变成求最大值

$$\max_{P,Q} \sum_{i=1}^n r(p_i) - \sum_{p_i \in P} r(p_i) - \sum_{q_j \in Q} c(q_j)$$

注意到 $\sum_{i} r(p_i)$与 P、Q 的选择无关，故只需求后两项和的最小值，即

$$\min_{P,Q} \sum_{p_i \in P} r(p_i) + \sum_{q_j \in Q} c(q_j)$$

现在考虑一个网络，起源点 s 连接到 n 个点 $p_1, \dots ,p_n$，边的容量分别为 $r(p_i)$，超汇点 t 连接到 m 个点 $q_1, \dots ,q_m$，边的容量分别为 $c(q_j)$，若执行任务 $p_i$需购买设备 $q_j$，则在 $p_i$、$q_j$ 之间连上一条容量为无限大的边，若不需购买设备，则不连上边。则 $\sum_{p_i \in P} r(p_i) + \sum_{q_j \in Q} c(q_j)$ 对应到一个 s-t 割的容量，其中的两个集合是要执行的计划与要购买的设备和它的余集，也就是

$$\{s\}\cup (P'\setminus P) \cup Q \text{、 } \{t\}\cup P \cup (Q'\setminus Q)$$

在此，$P'=\{p_1, \dots ,p_n\}$，$Q'=\{q_1, \dots ,q_m\}$。于是，原问题转成求该图的最大流问题，并且可以借由各种算法求得其极值。

以下给出一个计划选择问题的例子，右图是该问题对应到的网络。

计划收入 r(pi)｜设备价格 c(qj)｜备注

1｜100｜200｜执行计划 p1 须购买设备 q1、q2。

2｜200｜100｜执行计划 p2 须购买设备 q2。

3｜150｜50｜执行计划 p3 须购买设备 q3。

该网络的最小 s-t 割是选择计划 p2、p3 与设备 q2、q3，容量为 250。三个计划的总收益是 450，因此最大净利为 450 − 250 = 200。

以上解法可以理解为将计划所给予的收益流过所需设备，如果无法流满设备至 t 的边，代表执行计划不合成本，最小割将选择穿过 s 到计划的边而非穿过设备到 t 的边。

### 影像分割问题

<image>

设原图有 n 像素，想要把该图分割为前景和背景，并且将 i 像素归类为前景有效益 fi，归类为背景有效益 bi，但是若 i、j 像素相邻且被归类为不同块，则会减少 pij 的效益。求将该图分割为前后景的最有效益方法。

令 P 为前景的集合，Q 为背景的集合，于是问题转化成求最大值

$$\max_{P,Q} \sum_{i \in P} f_i + \sum_{i \in Q} b_i - \sum_{i \in P,j \in Q \lor j \in P,i \in Q } p_{ij}$$

因为 fi、 bi 的总合是与 P、Q的选取无关，因此等价于求以下最小值

$$\min_{P,Q} \sum_{i \in Q} f_i + \sum_{i \in P} b_i + \sum_{i \in P,j \in Q \lor j \in P,i \in Q } p_{ij}$$

以上的最小值问题可以被描述为一个网络的最小割问题，其中该网络如右图，以橘点为起源点；紫点为超汇点。各个像素被描述为网络的顶点，起源点至第 i 个像素连上一条容量为 fi 的有向边；第 i 个像素至超汇点连上一条容量为 bi 的有向边。相邻的像素 i、j 之间连上来回两条容量为 pij 的有向边。则一个 s-t 割代表一种将部分像素归类为前景 P、其余归类为背景 Q 的安排。

## 历史

最大流最小割问题最早在1956年被P. Elias, A. Feinstein，和 C.E. Shannon 证明P. Elias, A. Feinstein, and C. E. Shannon, A note on the maximum flow through a network, IRE. Transactions on Information Theory, 2, 4 (1956), 117–119，并且L.R. Ford, Jr. 和 D.R. Fulkerson 也在同年证明了该定理。

## 证明

同之前的设定，G = (V, E) 是一个网络(有向图)，s 点和 t 点分别为 G 的起源点和超汇点。

将所有流考虑成一个欧式空间的有界闭子集，满足流量限制与流量守恒，而流量是一个连续函数，因此有极大值 |f|。

设 f 达到最大流，令 (Gf ) 是 f 的残留网络，定义

- A：在 (Gf ) 中可以从 s 出发到达的点
- Ac：A 以外的点，即 V − A

换句话说，v∈A 当且仅当 s 可以流出更多流量到 v。

我们宣称 $|f|=c(A,A^c)$，其中该 s-t 割的容量定义为

$c (S,T) = \sum\nolimits_{(u,v) \in (S \times T) \cap E} c_{uv}$.

由于 $|f|$ 的大小等于所有流出集合 A 的流量总和减所有流入集合 A 的流量总和，故 $|f| \leq c(A,A^c)$，并且等号成立当且仅当

- 所有从 A 流向 Ac 的边流量均已达饱和。
- 所有从 Ac 流向 A 的边流量均为 0。

我们用反证法分别证明以上两点：

- 假设存在从 A 流向 Ac 的边 $(x,y) \in A \times A^c$ 并未达到饱和，即 $f(x,y)<c_{xy}$。因此，可以从 x 流更多的流量到 y，(x,y) 是 Gf 的一条边。由 x∈A 知 Gf 图中有一条中的路径从 s 到 x，其中只经过 A 中的点，所以 y∈A，产生矛盾。是故所有从 A 流向 Ac 的边流量均已达饱和。
- 假设存在从 Ac 流向 A 的边 $(y,x) \in A^c \times A$ 其流量不为 0，即 $f(x,y)>0$。因此，可以从 y 流更少的流量到 x，(x,y) 是 Gf 的一条边。由 x∈A 知 Gf 图中有一条中的路径从 s 到 x，其中只经过 A 中的点，所以 y∈A，产生矛盾。是故所有从 Ac 流向 A 的边流量均为 0。

于是，声称得证。

由于流量恒不超过容量，|f| 是容量的下界，所以 $c(A,A^c)$ 是容量的最小值，由声称知，最大流最小割定理得证。