定理简介

    这个定理的内容非常简洁，只有一句话，MAXFLOW的值等于极小割集的容量，MAXFLOW问题之前的博文已经总结过，这里需要给出一些新的定义，这些定义和本科图论的定义类似，和复杂性课上老师给的定义有一些出入，但所指的具体概念是没有区别的。

可行流：满足下述条件的流称为可行流(网络记为$D=(V,E,C)$)

1. 容量限制条件：对每一边$(v_i,v_j) \in E$，有$0 \leq f_{ij} \leq c_{ij}$
2. 平衡条件：对于中间点，流出量等于流入量，即对于每个$i$($i \neq s,t$)有$\sum_{(v_i,v_j) \in A} f_{ij}-\sum_{(v_j,v_i) \in A} f_{ji}=0$
3. 对于出发点$v_s$，记$\sum_{(v_s,v_j) \in A} f_{sj}-\sum_{(v_j,v_s) \in A} f_{js}=v(f)$
4. 对于收点$v_t$，记$\sum_{(v_t,v_j) \in A} f_{sj}-\sum_{(v_j,v_t) \in A} f_{jt}=-v(f)$，式中$v_f$称为这个可行流的流量

可行流显然是存在的，比如令所有的弧的流量$f_{ij}=0$，就得到一个可行流，其流量$v(f)=0$。

可行流$f$的增广链：设$f$是一个可行流，$\mu$是从$v_s$到$v_t$的一条链，若$\mu$满足下列条件，称为关于可行流$f$的增广链

1. 在弧$(v_i,v_j) \in \mu^+$($\mu$的前向弧)上，$0 \leq f_{ij} < c_{ij}$，即$\mu^+$中每一弧是非饱和弧
2. 在弧$(v_i,v_j) \in \mu^-$($\mu$的后向弧)上，$0 < f_{ij} \leq c_{ij}$，即$\mu^-$中每一弧是非零流弧

截集与截集的容量(也称为割集)：网络$D=(V,A,C)$，点集$V$被分为两个非空集合$V_1$和$\bar{V_1}$，使得，$v_s \in V_1$，$v_t \in \bar{V_1}$则把弧集$(V_1,\bar{V_1})$称为是分离$v_s$和$v_t$的截集，截集$(V_1,\bar{V_1})$中所有弧的容量之和称为这个截集的容量(简称为截量)，记为$c(V_1,\bar{V_1})$，即

$$c(V_1,\bar{V_1})=\sum_{(v_i,v_j) \in (V_1,\bar{V_1})}c_{ij}$$

定理证明

    由截集的定义可知，任何一个可行流的流量$v(f)$都不会超过任一截集的容量，即$v(f) \leq c(V_1,\bar{V_1})$
显然，如果能找到一个可行流$f$，使得存在某个截集$(V_1,\bar{V_1})$有$v(f)=c(V_1,\bar{V_1})$成立，必有$v(f)$为一个最大流，$(V_1,\bar{V_1})$为最小截集，若$v(f)$不是最大流，即存在$f^*$使$v(f^* )>v(f)$，则有$v(f^*) >c(V_1,\bar{V_1})$，矛盾。若$(V_1,\bar{V_1})$不是最小截集，则有$({V_1}^*,\bar{V_1^*})$使得$c(V_1^*,\bar{V_1^*})< c(V_1,\bar{V_1})$则有$c(V_1^*,\bar{V_1^*}) < v(f)$，同样导出矛盾。

    下面假设$f^*$为最大流，若$D$中存在关于$f^*$的增广链$\mu$，取

$$\theta=min\{\mathop{min} \limits_{\mu^+}(c_{ij}-f_{ij}^*),\mathop{min} \limits_{\mu^-}f_{ij}^*\}$$

由增广链的定义，可知$\theta>0$，令

$$f^{**}=\left\{\begin{array}{l} {f_{ij}^*+\theta \quad (v_i,v_j) \in \mu^+} \\ {f_{ij}^*-\theta \quad (v_i,v_j) \in \mu^-} \\ {f_{ij}^* \qquad (v_i,v_j) \notin \mu} \end{array}\right.$$

此时的$f^{**}$显然也是一个可行流，且$v(f^{**})=v(f^*)+\theta>v(f^*)$，这与$f^*$是最大流矛盾，故此时$D$中不存在关于$f^*$的增广链$\mu$。

    已知关于$f^*$的增广链不存在，定义点集合$V_1^*$如下：

1. 令$v_s \in V_1^*$
2. 若$v_i \in V_1^*$，且$f_{ij}^* < c_{ij}$，则令$v_j \in V_1^*$
3. 若$v_i \in V_1^*$，且$f_{ji}^*>0$，则令$v_j \in V_1^*$

因为不存在关于$f^*$的增广链，故由增广链的定义可知$v_t \notin V_1^*$。

    则记$\bar{V_1^*}=V \backslash V_1^*$，得到一个截集$(V_1^*,\bar{V_1^*})$，显然有

$$f^{**}=\left\{\begin{array}{l} {c_{ij} \quad (v_i,v_j) \in (V_1^*,\bar{V_1^*})} \\ {0 \quad (v_i,v_j) \in (\bar{V_1^*},V_1^*)} \end{array}\right.$$

这里$(V_1^*,\bar{V_1^*})$此截集上的正向流量都等于容量$c_{ij}$，不可能再增加流量，则必有

$$v(f^*)=c(V_1^*,\bar{V_1^*})$$

最大流$f^*$的流量$v(f^*)$等于一个截集$(V_1^*,\bar{V_1^*})$的容量，则$(V_1^*,\bar{V_1^*})$必为最小截集，则最大流量等于最小截集的容量，原命题得证。

     这个问题的证明很巧妙，把比较抽象的东西用数学语言表述出来了，图论方面的很多命题都有这样的特点。