最小割

定义

定义流网络 $G=(V,E)$ 的割 $[S,T]$ 将点集 $V$ 划分成两个 $S$ 和 $T$ 两个部分，使得 $s\in S$，并且 $t\in T$，符号 $[S,T]$ 代表一个边集合 $\{|\in E,u\in S,v\in T\}$，穿过割 $[S,T]$ 的净流为 $f(S,T)=\sum_{u\in S}\sum_{v\in T}f(u,v)$，割 $[S,T]$ 的容量为 $c(S,T)=\sum_{u\in S}\sum_{v \in T}c(u,v)$

最小割可行边

定义：如果边 $$ 存在于某个最小割方案中，那么边 $$ 为最小割可行边

充要条件：

1. 满流
2. 残量网络中不存在 $u$ 到 $v$ 的增广路

最小割必须边

定义：如果边 $$ 存在于所有最小割方案中，那么边 $$ 为最小割必须边

充要条件：

1. 满流
2. 残量网络中存在 $s$ 到 $u$ 的增广路以及 $v$ 到 $t$ 的增广路

性质

1. 不同的最小割最多只有 $n - 1$ 个
2. 求完最大流后，当前这种最小割将点集分为从 $s$ 能到的点和剩下的点
3. 求完最大流后，当前这种最小割的割边一定是满流边，但满流边不一定是割边
4. 减少最小割可行边的容量会使最小割减少
5. 增大最小割必须边的容量会使最小割增大
6. 令从 $s$ 能到达的点集为 $S$，从 $t$ 能到达的点集为 $T$，如果 $S$ 和 $T$ 相加不为总点数，令剩下的点集是 $M$，则 $M$ 夹在 $S$ 和 $T$ 之间，且 $M$ 中一定有割边。所以如果 $M$ 为空，则最小割唯一