最后更新: 2025-01-22 10:10 查看: 65 次纠错评论(0) 课件开VIP

最大流最小割定理

定理 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)

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：网络最大流

下一篇：二分图的匹配

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