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

网络最大流

运输问题是把商品从产地运往市场，运输的路线用有向图表示，用一个顶点表示产地，另一个顶点表示市场，其他顶点表示中转站，每条弧表示一段运输路线。在每段路线上给定运输能力的条件下，试设计一个运输方案，使得运输速率最大，即单位时间的运输量最大。

定义 11.7 （网络）设连通无自环的带权有向图中有两个不同顶点 $s$ 和 $t$ ，且在弧集 $E$ 上定义一个非负整数值函数 $C=\left\{c_{i j}\right\}$ ，称该有向图为网络，记为 $N(V, E, C)$ 。称 $s$ 为发点，$t$ 为收点，除 $s$ 和 $t$ 以外其他顶点称为中间点。 $C$ 称为容量函数，弧 $(i, j)$ 上的容量为 $c_{i j}$ 。

定义 11.8 （流量）在网络 $N(V, E, C)$ 的弧集 $E$ 上定义一个非负整数值函数 $f=\left\{f_{i j}\right\}$ ，称 $f$为网络 $N$ 上的流，$f_{i j}$ 称为弧 $(i, j)$ 上的流量。若无弧 $(i, j)$ ，则 $f_{i j}$ 定义为 0 。设流 $f$ 满足下列条件。
（1）容量限制条件：对每一条弧 $(i, j)$ ，有 $f_{i j} \leqslant c_{i j}$ 。
（2）平衡条件：除 $s$ 和 $t$ 外的每个中间点 $k$ ，有 $\sum_{i \in V} f_{k i}=\sum_{j \in \ell} f_{j k}$ ，对于 $s$ 和 $t$ 有
$$
\sum_{i \in V} f_{k i}-\sum_{j \in V} f_{j k}=\left\{\begin{array}{cc}
V_f & k=s \\
-V_f & k=t
\end{array}\right.
$$

则称 $f$ 为网络 $N$ 的一个可行流，$V_f$ 为流 $f$ 的值，或称 $f$ 的流量。若 $N$ 中无可行流 $f^{\prime}$ ，使 $V_f^{\prime}>V_f$ ，则称 $f$ 为最大流。
 ![图片](/uploads/2025-01/676230.jpg)
图11．2是一个网络，每条弧上第一个数表示容量，第二个数表示流量。上述条件（1）表示在一段运输路线上运输量不超过它的容量，条件（2）表示除发点和收点外每个中转站的输入量等于输出量，而发点净出

图 11.2量等于收点净入量，它们的值均为 $V_f$ 。

定义 11.9 （饱和的／未饱和的）若 $f_{i j}=c_{i j}$ ，则称弧 $(i, j)$ 是饱和的；若 $f_{i j}<c_{i j}$ ，则称弧 $(i, j)$ 是未饱和的。
上面讨论的网络通常称为运输网络。用它来表示的物理模型是多种多样的。网络的弧可用来表示城市间铁路或公路，电信局之间的通信线路，网络的流则可表示在单位时间内，铁路上运输物资的量，公路上通过的车流量或其他信息量等。我们的目的是要找出它的最大流量的值。

为了解决求网络最大流的问题，先来讨论割的概念。
定义 11.10 （割）设 $N(V, E, C)$ 是有一个发点 $s$ 和一个收点 $t$ 的网络。若 $V$ 划分为 $P$ 和 $\bar{P}$ ，使 $s \in P, t \in \bar{P}$ ，则从 $P$ 中的点到 $\bar{P}$ 中的点的所有弧集称为分离 $s$ 和 $t$ 的割，记为 $(P, \bar{P})$ 。

若从网络 $N$ 中删去任一个割，则从 $s$ 到 $t$ 之间不存在有向路。
割 $(P, \bar{P})$ 的容量是它的每条弧的容量之和，记为 $C\left(P, P^{\prime}\right)$ ，即：

$$
C(P, \bar{P})=\sum_{(i \in P, j \epsilon \bar{P})} c_{i j}
$$

对于不同的割，它的容量显然不同。
若 $N$ 中不存在割 $\left(P^{\prime}, \overline{P^{\prime}}\right)$ ，使 $C\left(P^{\prime}, \overline{P^{\prime}}\right)<C(P, \bar{P})$ ，则称 $(P, \bar{P})$ 为最小割。
网络中的流的值具有上界，如下面的定理所述。
定理11．4 对于给定的网络 $N=(V, E, C)$ ，设 $f$ 是任一个可行流，$(P, \bar{P})$ 是任一个割，则 $V_f \leq C(P, \bar{P})$ 。

证明：根据流的平衡条件可知：对于发点 $s \in P$ 有

$$
\sum_{i \in V} f_{s i}-\sum_{j \in V} f_{j s}=V_f
$$

对于 $P$ 中 不是发 点 $s$ 的中间点 $k$ 有

$$
\sum_{i \in V} f_{k i}-\sum_{j \in V} f_{j k}=0
$$

由（1）式加上对所有 $k \in P$ 的
（2）式得到

$$
\begin{aligned}
& \sum_{(k \in p, i \in V)} f_{k i}-\sum_{(k \in P, j \in V)} f_{j k} \\
& =\sum_{(k \in P, i \in P)} f_{k i}+\sum_{(k \in P, i \in \bar{P})} f_{k i}-\left[\sum_{(k \in P, j \in P)} f_{j k}+\sum_{(k \in P, j \in \bar{P})} f_{j k}\right] \\
& =V_f
\end{aligned}
$$

由于 $\sum_{(k \in P, i \in P)} f_{k i}=\sum_{(k \in P, j \in P)} f_{j k}$ ，
所以

$$
\sum_{(k \in P, i \in \bar{P})} f_{k i}-\sum_{(k \in P, j \in \bar{P})} f_{j k}=V_f
$$

因为 $\sum_{(k \in P, j \in \bar{P})} f_{j k}$ 是非负的，所以有

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

上述证明中，（3）是一个有用的结论，它指出对于任何割 $(P, \bar{P})$ ，流的值等于从 $P$ 中的顶点到 $\bar{P}$ 中的顶点的所有弧上流量之和减去从 $\bar{P}$ 中的顶点到 $P$ 中的顶点的所有弧上流量之和。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：割点与块

下一篇：最大流最小割定理

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