5.8.7 运输网络

1. 运输网络

一个连通有向图称为运输网络,如果它有两个加标号的顶点 $Q$ (称为源点) 和 $S$ (称为汇点),具有下列性质:

a) 存在一条从 $S$ 到 $Q$ 的弧 $u_1$ ,其中 $u_1$ 是仅有的以 $S$ 为始点及仅有的以 $Q$ 为终点的弧.

b) 每个与 $u_1$ 不同的弧 $u_i$ 被指派一个实数 $c\left(u_i\right)\ge 0$ . 这个数称为它的容量. 弧 $u_1$ 有容量 $\mathrm{\infty }$ .

若函数 $\phi$ 对每条弧指派一个实数,并且对于每个顶点 $v$ ,等式

$$\begin{array}{}\text{(5.325a)}& \sum _{\left(u,v\right)\in G}\phi \left(u,v\right)=\sum _{\left(v,w\right)\in G}\phi \left(v,w\right)\end{array}$$

成立,则称它为 $G$ 上的流. 将和

$$\begin{array}{}\text{(5.325b)}& \sum _{\left(Q,v\right)\in G}\phi \left(Q,v\right)\end{array}$$

称为流的强度. 如果对于 $G$ 的每条弧 $u_i$ 有 $0\le \phi \left(u_i\right)\le c\left(u_i\right)$ ,那么称流 $\phi$ 是与容量相容的.

关于运输网络的例子, 见 553 页.

2. 福特 (Ford)-富尔克森 (Fulkerson) 极大流算法

应用极大流算法我们可以确认给定的流 $\phi$ 是否极大.

设 $G$ 是运输网络, $\phi$ 是与容量相容的强度为 $v_1$ 的流. 下面给出的算法包含给顶点标号后的步骤, 以及完成这些步骤后我们可以了解基于所选取的标号步骤有多少流的强度可以改进.

a) 对源点 $Q$ 标号,并令 $\epsilon \left(Q\right)=\mathrm{\infty }$ .

b) 如果存在弧 $u_i=\left(x,y\right)$ ,其中 $x$ 被标号而 $y$ 未标号,并且 $\phi \left(u_i\right)<c\left(u_i\right)$ , 那么给 $y$ 和(x, y)标号,并且令 $\epsilon \left(y\right)=min\left\{\epsilon \left(x\right),c\left(u_i\right)-\phi \left(u_i\right)\right\}$ ,然后重复步骤 b), 不然实施步骤 c).

c) 如果存在弧 $u_i=\left(x,y\right)$ ,其中 $x$ 未标号而 $y$ 被标号,并且 $\phi \left(u_i\right)>0$ 以及 $u_i\ne u_1$ ,那么给 $x$ 和(x, y)标号,代以 $\epsilon \left(x\right)=min\left\{\epsilon \left(y\right),\phi \left(u_i\right)\right\}$ ,并返回继续实施步骤 $\mathrm{b})$ (如果此步骤可行),不然算法结束.

若 $G$ 的汇点 $S$ 被标号,那么 $G$ 中的流可以改进适当的量 $\epsilon \left(S\right)$ . 如果汇点未被标号, 那么这个流是极大的.

极大流: 对于图 5.62 中的图, 权是紧贴着边写的. 图 5.63 中的加权图给出一个与这些容度相容的强度 13 的流. 它是一个极大流.

运输网络: 某种产品由 $p$ 个企业 $F_1,F_2,\cdots ,F_p$ 生产,有 $q$ 个用户 $V_1,V_2,\cdots ,V_q$ . 在某个期间, $F_i$ 生产 $s_i$ (单位) 产品, $V_j$ 需要 $t_j$ (单位) 产品,并且在该期间可以由 $F_i$ 向 $V_j$ 运送 $c_{ij}$ (单位) 产品. 在此期间是否可能满足所有要求? 对应的图见图 5.64.