最后更新: 2025-01-22 10:08 查看: 25 次反馈刷题

网络最大流

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

定义 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$ 中的顶点的所有弧上流量之和。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：割点与块

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

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