最后更新: 2025-01-22 10:10 ● 参与者查看: 14 次纠错分享参与项目词条搜索

最大流最小割定理

定理 11.4 告诉我们，网络 $N$ 中任何可行流 $f$ 流的值小于或等于任一割的容量，显然最大流的值小于或等于最小割的容量。如果能找到一个可行流 $f$ 和一个割 $(P, \bar{P})$ ，使得 $V_f=C(P, \bar{P})$ ，则 $f$ 是最大流。下面介绍 Ford－Fulkerson 于1956年给出的最大流最小割定理。

定理 11.5 （最大流最小割定理）在任一网络 $N$ 中，从 $s$ 到 $t$ 的最大流的值等于分离 $s$和 $t$ 的最小割的容量。

证明：设 $f$ 是一个最大流，用以下方法定义 $P$ 。
令 $s \in P$ 。如果 $i \in P$ 且 $f_{i j}<c_{i j}$ ，则 $j \in P$ ；如果 $i \in P$ 且 $f_{j i}>0$ ，则 $j \in P$ 。任何不在 $P$ 中的顶点在 $\bar{P}$ 中。
现在证明 $t \notin P$ 。假设 $t \in P$ ，则得到一条从 $s$ 到 $t$ 的路 $\mu$ 。定义路的方向是从 $s$ 到 $t$ ，如果 $\mu$ 上弧的方向与路的方向一致，称该弧为向前弧；如果 $\mu$ 上弧的方向与路的方向相反，称该弧为向后弧。由 $P$ 的定义可知，在向前弧 $(i, j)$ 上必有 $f_{i j}<c_{i j}$ ，在向后弧 $(j, i)$ 上必有 $f_{j i}>0$ 。路 $\mu$ 称为从 $s$ 到 $t$ 的增广路。

设 $\delta_1$ 是路 $\mu$ 上所有向前弧上 $c_{i, i+1}-f_{i, i+1}$ 的最小值，$\delta_2$ 是所有向后弧上 $f_{j+1, j}$ 的最小值， $\delta=\min \left(\delta_1, \delta_2\right), \delta>0$ ，在向前弧上可增加流量 $\delta$ ，在向后弧上可减少流量 $\delta$ ，使得流 $f$ 修改后得到的流 $f^{\prime}$ 仍满足流的条件，并且流的值增加 $\delta$ ，这与 $f$ 是最大流矛盾。因此 $t \notin P$ ，于是得到分离 $s$和 $t$ 的割 $(P, \bar{P})$ 。

由 $(P, \bar{P})$ 的构造可知，如果 $k \in P, i, j \in \bar{P}$ ，有 $f_{k i}=c_{k i}$ 以及 $f_{j k}=0$ ；又对任一割 $(P, \bar{P})$ ，定理11．4中式（3）成立，即 $\sum_{(k \in P, i \in \bar{P})} f_{k i}-\sum_{(k \in P, j \in \bar{P})} f_{j k}=V_f$ 。所以，对上述构造的割 $(P, \bar{P})$ ，有

$$
V_f=\sum_{(k \in P, i \in \bar{P})} c_{k i}=C(P, \bar{P})
$$

因为 f 是最大流，由定理 11.4 的结论可知，(,) P P 是最小割，并且最小割的容量等于最
大流的值。 □

容易得到下面的定理。
定理11．6 可行流 $f$ 是最大流当且仅当不存在从 $s$ 到 $t$ 的关于 $f$ 的增广路。从定理 11.5 的证明可以知道寻求最大流的方法，就是寻找从 $s$ 到 $t$ 的关于 $f$ 的增广路。最大流的标号方法
标号方法分为两个过程：标号过程和增广过程。通过标号过程找一条增广路，再由增广过程确定网络流量的增量，并且去掉标号。

1．标号过程
（1）给定初始流，不妨设初始流的值为 0 ；给发点标号 $(-, \Delta s)$ ，其中 $\Delta s=+\infty$ 。
（2）选择一个已标号的顶点 $p$ ，对于 $p$ 的所有未标号的相邻点 $q$ ，按下列规则标号：
（a）如果弧 $(p, q), q$ 未标号，当 $c_{p q}>f_{p q}$ 时，则点 $q$ 标号 $\left(p^{+}, \Delta q\right)$ ，其中 $\Delta q=\min \left\{\Delta p, c_{p q}-f_{p q}\right\}$ ；；当 $c_{p q}=f_{p q}$ 时，则 $q$ 不标号。
（b）如果弧 $(q, p), q$ 未标号，当 $f_{q p}>0$ 时，则点 $q$ 标号 $\left(p^{-}, \Delta q\right)$ ，其中 $\Delta q=\min \left\{\Delta p, f_{q p}\right\}$ ；当 $f_{q p}=0$时，则 $q$ 点不标号。
（3）重复第（2）步直到收点 $t$ 被标号为止，或不再有顶点可以标号为止。
如果 $t$ 点给出标号，说明存在一条增广路，则转向增广过程。
如果 $t$ 点未被标号，说明不存在增广路，则算法结束，所得的流为最大流。
2．增广过程
如果在收点 $t$ 已标号 $\left(y^{+}, \Delta t\right)$ ，已知其中 $\Delta t=\min \left\{\Delta y, c_{y t}-f_{y t}\right\}$ ，则存在一条从 $s$ 到 $t$ 的增广路 $\mu$ 。
（1）修改流 $f$ ，使得沿增广路 $\mu$ 在向前弧上流量增加 $\Delta t$ ，在向后弧上流量减少 $\Delta t$ ，于是得到新的流 $f^{\prime}$ ，且有 $V_f=V_f+\Delta t$ 。然后去掉顶点上标号。
（2）对流 $f^{\prime}$ 重新进行标号过程。
如果在收点 $t$ 没有标号，标号算法结束，用 $P$ 表示所有已标号的顶点集， $\bar{P}$ 表示所有未标号的顶点集，于是得到的 $(P, \bar{P})$ 便是最小割，它的容量等于最大流的值。

从上述算法可见，我们不仅得到最大流，而且同时得到了最小割，要想提高总流量，只有增大最小割中弧的容量才行。

上述算法还要注意两点。
（1）初始流量可以不为 0 。
（2）每次标号时，可能有多种情况，任选一种即可。
例 11.2 考虑图 11.3 （a）中的网络，（b）到（g）表示求最大流的标号过程和增广过程。标号算法结束得到最大流的值为 7 ，最小割 $(P, \bar{P})$ ，其中 $P=\{s, a, c, d\}, \bar{P}=\{b, t\}, C(P, \bar{P})=7$ 。算法还构造性地证明了网络流理论中的一个重要定理。
定理 11.7 （整数流定理）任一网络中，若所有弧的容量是整数，则必存在整数最大流。
 ![图片](/uploads/2025-01/fe7a7f.jpg)
  ![图片](/uploads/2025-01/826dee.jpg)
   ![图片](/uploads/2025-01/2b0647.jpg)

上一篇：网络最大流

下一篇：二分图的匹配

本文对您是否有用？有用 (0) 无用 (0)