解决网络最大流问题

子任务5.2　解决网络最大流问题

5.2.1　任务引入

【任务5-2】　求图5-11所示的网络最大流，弧旁的权数表示（c_ij，f_ij）。

图5-11

5.2.2　任务分析

参看后面的知识建构，则我们可以得出以下结论：

①一个网络D中，任何一个可行流f的流量v（f）都小于或等于这个网络中任何一个截集的截量。并且，如果网络上的一个可行流f^*和网络中的一个截集，满足条件v（f^*）=C，那么f^*一定是D上的最大流，而）一定是D的所有截集中截量最小的一个（即最小截集）。

②网络中的一个可行流f^*是最大流的充分必要条件是，不存在关于f^*的增广链。

③在一个网络D中，最大流的流量等于分离v_s和v_t的最小截集的截量。

由上面的结论可知，我们可以得出一个寻求网络系统最大流的方法：如果网络D中有一个可行流f，只要判断网络是否存在关于可行流f的增广链。如果没有增广链，那么f一定是最大流；如有增广链，那么可以按照上述结论③，不断改进和增大可行流f的流量，最终可以得到网络中的一个最大流。

下面一起来了解求解网络最大流问题的方法：标号法。

从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。

用给顶点标号的方法来定义。在标号过程中，有标号的顶点是中的点，没有标号的点不是中的点。如果v_t有了标号，表示存在一条关于f的增广链。如果标号过程无法进行下去，并且v_t未被标号，则表示不存在关于f的增广链。这样，就得到了网络中的一个最大流和最小截集。

（1）标号过程

在标号过程中，网络中的点分为标号点（分为已检查和未检查两种）和未标号点。每个标号点的标号包括两部分：第一个标号表示这个标号是从哪一点得到的，以便找出增广链；第二个标号是为了用来确定增广链上的调整量θ。

标号过程开始，先给v_s标号（0，+∞）。这时，v_s是标号未检查的点，其他都是未标号点。一般地，取一个标号未检查点v_i，对一切未标号点v_j：

①如果在弧（v_i，v_j）上，f_ij＜c_ij，那么给v_j标号［v_i，l（v_j）］。其中l（v_j）=min［l（v_i），c_ij-f_ij］。这时，v_j成为标号未检查点。

②如果在弧（v_j，v_i）上，f_ji＞0，那么给v_j标号［-v_i，l（v_j）］。其中l（v_j）= min［l（v_i），f_ij］。这时，v_j成为标号未检查点。

于是v_i成为标号已检查的点。重复以上步骤，如果所有的标号都已经检查过，而标号过程无法进行下去，则标号法结束，这时的可行流就是最大流。但是，如果v_t被标上号，表示得到一条增广链μ，转入下一步调整过程。

（2）调整过程

首先按照v_t和其他点的第一个标号，反向追踪，找出增广链μ。例如，令v_t的第一个标号是v_k，则弧（v_k，v_t）在μ上。再看v_k的第一个标号，若是v_i，则弧（v_i，v_k）都在μ上。依次类推，直到v_s为止。这时，所找出的弧就成为网络D的一条增广链μ。取调整量θ=l（v_t），即v_t的第二个标号，

令

非增广矩阵上的各弧流量不变。

再去掉所有的标号，对新的可行流f′=｛f_i′j｝，重新进行标号过程，直到找到网络D的最大流为止。

5.2.3　知识建构

1）网络流基本概念

（1）网络与网络流

网络：设一个赋权有向图D=（V，A），在V中指定一个发点v_s和一个收点v_t，其他的点叫做中间点。对于D中的每一个弧（v_i，v_j）∈A，都有一个权c_ij称为弧的容量。我们把这样的图D叫做一个网络系统，简称网络，记做D=（V，A，C）。

网络流：指在一定条件下渡过一个网络的某种流在各边上的流量的集合。定义在弧集合A上的一个函数：F=｛f（v_i，v_j）｝=｛f_ij｝，则f（v_i，v_j）=f_ij叫做弧在（v_i，v_j）上的流量，简记为f_ij。

如图5-12所示，图（a）上数字为弧容量，图（b）上括号内数字为弧流量。

图5-12

网络系统上流的特点：

①发点的总流出量和收点的总流入量必相等；

②每一个中间点的流入量与流出量的代数和等于零；

③每一个弧上的流量不能超过它的最大通过能力（即容量）。

（2）可行流

可行流：是指满足以下条件的一个网络流。

①容量条件：对于每一个弧（v_i，v_j）∈A，有0≤f_ij≤c_ij

②平衡条件：对于发点v_s，有∑f_sj-∑f_js=v（f）

　　　　　　对于收点v_t，有∑f_tj-∑f_jt=-v（f）

　　　　　　对于中间点，有∑f_ij-∑f_ji=0

其中发点的总流量（或收点的总流量）v（f）称为这个可行流的流量。

（3）最大流

最大流：是指在一个网络中，流量最大的可行流。

图5-13

可行流中f_ij=c_ij的弧称为饱和弧，f_ij＜c_ij的弧称为非饱和弧。f_ij＞0的弧为非零流弧，f_ij=0的弧叫做零流弧。

如图5-13所示，（v₄，v₃）是饱和弧，其他的弧是非饱和弧，并且都是非零流弧。

设μ是网络D中连接发点v_s和收点v_t的一条链。定义链的方向是从v_s到v_t，于是链μ上的弧被分为两类：一是弧的方向与链的方向相同，称为前向弧，前向弧的集合记做μ⁺；二是弧的方向与链的方向相反，称为后向弧，后向弧的集合记做μ^-。如图5-13所示，则在链（v_s，v₁，v₂，v₃，v₄，v_t）中，μ⁺=｛（v_s，v₁），（v₁，v₂），（v₂，v₃），（v₄，v_t）｝，μ^-=｛（v₄，v₃）｝。

增广链：f是一个可行流，如果链μ满足以下条件：

①在弧（v_i，v_j）∈μ⁺上，有0≤f_ij＜c_ij，即μ⁺中的每一条弧是非饱和弧。

②在弧（v_i，v_j）∈μ^-上，有0＜f_ij≤c_ij，即μ^-中的每一条弧是非零流弧。则称μ为从v_s到v_t的关于f的一条增广链。

例如在图5-13中，链μ=（v_s，v₁，v₂，v₃，v₄，v_t）就是一条增广链。

2）网络的截集和截集容量

（1）网络的截集

（2）截集容量

设一个截集，则截集中所有弧的容量之和，称为这个截集的容量，记为C，即C=∑c_ij。

［示例］如图5-14所示。

图5-14

则：S=（v_s，v₂）

（S，S）=（v_s，v₁），（v₂，v₄），（v₂，v₃）　C= c_s1+ c₂₄+ c₂₃= 7+6+5=18

［示例］如图5-15所示。

图5-15

5.2.4　任务实施

用标号法对任务5-2进行任务实施。

步骤一　标号过程

（1）首先给v_s标号（0，+∞）。

（2）看v_s：在弧（v_s，v₂）上，f_s2=c_s3=3，不具备标号条件。在弧（v_s，v₁）上，f_s1=1＜c_s1=5，故给v₁标号［v_s，l（v₁）］，其中l（v₁）=min［l（v_s），（c_s1-f_s1）］=min［+∞，5-1］=4。

（3）看v₁：在弧（v₁，v₃）上，f₁₃=c₁₃=2，不具备标号条件。在弧（v₂，v₁）上，f₂₁=1＞0，故给v₂标号［-v₁，l（v₂）］，其中l（v₂）=min［l（v₁），f₂₁］=min［4，1］=1。

（4）看v₂：在弧（v₂，v₄）上，f₂₄=3＜c₂₄=4，故给v₄标号［v₂，l（v₄）］）。其中：l（v₄）=min［l（v₂），（c₂₄-f₂₄）］=min［1，1］=1。在弧（v₃，v₂）上，f₃₂=1＞0，故给v₃标号［-v₂，l（v₃）］。其中：l（v₃）=min［l（v₂），f₃₂］=min［1，1］=1。

（5）在v₃，v₄中任意选一个，比如v₃，在弧（v₃，v_t）上，f_3t=1＜c_3t=2，故给v_t标号［v₃，l（v_t）］，其中：l（v_t）=min［l（v₃），（c_3t-f_3t）］=min［1，1］=1。因为v_t被标上号，根据标号法，转入调整过程。

步骤二　调整过程

从v_t开始，按照标号点的第一个标号，用反向追踪的方法，找出一条从v_s到v_t的增广链μ，如图5-16中双箭线所示。

图5-16

不难看出，μ⁺=｛（v_s，v₁），（v₃，v_t）｝，μ^-=｛（v₂，v₁），（v₃，v₂）｝，取θ=1，在μ上调整f，得到

其他的f_ij不变。

调整后的可行流，如图5-17所示，再对这个可行流重新进行标号过程，寻找增广链。

图5-17

首先给v_s标号（0，+∞），给v₁标号（v_s，3）。看v₁，在弧（v₁，v₃）上，f₁₃=c₁₃，弧（v₂，v₁）上，f₂₁=0，均不符合标号条件。因此标号过程无法进行下去，不存在从v_s到v_t的增广链，算法结束。

这时，网络中的可行流f′即是最大流，最大流的流量v（f′）=f_s1+f_s2=5。同时，也找出D的最小截集，其中S^*=｛v_s，v₁｝是标号的集合，｛v，v，₂₃v₄，v_t｝是未标号的集合。