《网络最大流问题【一类优选】》由会员分享，可在线阅读，更多相关《网络最大流问题【一类优选】（15页珍藏版）》请在金锄头文库上搜索。
1、给定一个有向图D=(V,A)，在V中指定一点称为发点（记为 ），该点只有出发去的弧，指定另一点称为收点（记为 ），该点只有指向它的弧，其余的点叫做中间点。对于A中的每一条弧 ，对应一个数 （简记 ），称之为弧的容量。通常我们把这样的D叫做网络，记为D=(V,A,C)。（2）网络流：在弧集A上定义一个非负函数 。 是通过弧 的实际流量，简记 ，称 是网络上的流函数，简称网络流或流，称 为网络流的流量。4 网络最大流问题网络最大流问题是网络的另一个基本问题。许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何
2、达到这个最大流量。4.1 基本概念与定理1 1 网络与流定义14 （1）网络：例1 如图7-20是连结某产品产地 和销地 的交通图。弧 表示从 到 的运输线，弧旁的数字表示这条运输线的最大通过能力 ，括号内的数字表示该弧上的实际流 。现要求制定一个运输方案，使从 运到 的产品数量最多。可行流与最大流在运输网络的实际问题中，我们可以看出，对于流有两个基本要求： 一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）；二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也
3、就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。因此有下面所谓的可行流的定义。定义14 对于给定的网络D=（V,A,C）和给定的流 ，若 满足下列条件：（1） 容量限制条件：对每一条弧 ，有 (7.9)（2）平衡条件：对于中间点：流出量=流入量，即对于每一个i (is,t)，有 (7.10)对于出发带点 ，有 (7.11)对于收点 ，有 (7.12)则称 为一个可行流， 称为这个可行流的流量。注意，我们这里所说的出发点 是指只有从 发出去的弧，而没有指向 的弧；收点 是指只有弧指向 ，而没有从它的发出去的弧。可行流总是存在的。例如令所有弧上的流 ，就得到一个可行流，（称为
4、零流），其流量 。如图7-20中，每条弧上括号内的数字给出的就是一个可行流 ，它显然满足定义中的条件（1）和（2）。其流量 。所谓网络最大流问题就是求一个流 ，使得总流量 达到最大，并且满足定义15中的条件（1）和（2），即max (7.13)网络最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个问题的方法较直线性规划的一般方法要简便和直观的多。例2 写出图7-20所表示的网络最大流问题的线性规划模型。解 设 ，则其线性规划模型为 max 3. 增广链在网络D=(V,A,C)中，若给定一个可行流 ，我们把网络中使 的弧称为饱和弧，使 的弧称为非饱和弧。把 的弧称为零流弧，把
5、 的称为非零流弧。如图7-20中的弧都是非饱和弧，而弧 为零流弧。若 是网络中联结发点 和收点 的一条链，我定义链的方向是从 到 S ，则链上的弧被分为两：一类是：弧的方向与链的方向一致，我们称此类和为前向弧，所有前向弧的集合记为 。另一类是：弧的方向与链的方向一致，我们称此类弧为后向弧，所有后向弧的集合记为 。如图7-20中，设是一条从 到 的链，则, 定义15 设 是网络D=(V,A,C)上的一个可行流， 是从 到 的一条链，若 满足下列条件：(1)在弧 (vi,vj)+上，即 中的每一条弧都是非饱和弧；(2)在弧 上，即 中的每一条弧都是非零流弧。则称 是关于 的一条增广链。如前面所说的
6、链就是一条增广链。因为其中+上的弧均非饱和，如(vs,v2) +,fs2=50，。显然这样的增广链不止一条。4.截集与截量定义16 给定网络D=(V,A,C)，若点集V被分割成两个非空集合V1和V2，使得V=V1+V2,V1V2=(空集)，且vsV1,vtV2，则把始点在V1,终点在V2的弧的集合称为分离vs和vt的一个截集，记为(V1,V2)。如图9.26中，设V1=vs,v2,v5，V2=v3,v4,v6,vt则截集为 ,而弧(v3,v2)和(v4,v5)不是该集中的弧。因为这两条弧的起点在V2中，与定义17不符。显然，一个网络的截集是很多的（但只有有限个），例如在图7-20中，还可以取
7、, ，则截集为 另外，若把网络D=(V,A,C)中某截集的弧从网络D中去掉，则从vs到vt便不存在路，所以直观上说，截集是从vs到vt的必经之路。定义17 在网络D=(V,A,C)中，给定一个截集(V1,V2)，则把该截集中所有弧的容量之和，称为这个截集的容量，简称为截量，记为c(V1,V2)，即 C(V1,V2)= (7.16)例如在上面我们所举的两个截集中，有 而 显然，截集不同，其截量也不同。由于截集的个数是有限的，故其中必有一个截集的容量是最小的，称为最小截集，也就是通常所说的“瓶颈”。不难证明，网络D=(V,A,C)中，任何一个可行流f=fij的流量V(f)，都不会超过任一截集的容量
8、，即 v( f ) c(V1,V2) (7.17)如果存在一个可行流f*=f*ij，网络D=(V,A,C)中有一个截集 ，使得 (7.18)则 必是最大流，而 必是D中的最小截集。为了求网络最大流f*，我们也说明下面的重要定理。定理4 在网络D=(V,A,C)中，可行流 是最大流的充要条件是D中不存在关于f*的增广链。证 先证必要性。用反证法。若f*是最大流，假设D中存在着关于f*的增广链，令 (7.19)由增广链的定义可知0，令 (7.20)不难验证 是一个可行流，且有 这与f*是最大流的假定矛盾。再证充分性：即证明设D中不存在关于f*的增广链，f*是最大流。用下面的方法定义：令 若 ，且有
9、 ，则令 ；若 ，且有 ，则令 。因为不存在着关于 的增广链，故 记 ，于是得到一个截集(V*, )。显然有 所以V(f*)=c ，于是f*必是最大流。定理得证。由上述证明中可见，若 是最大流，则网络必定存在一个截集 ，使得(7.18)式成立。定理5 （最大流最小截集定理）对于任意给定的网络D=(V,A,C)，从出发点vs到收点vt的最大流的流量必等于分割 和 的最小截集 的容量，即由定理4可知，若给定一个可行流 ，只要判断网络D有无关于 的增广链。如果有增广链，则可以按定理4前半部分证明中的办法，由公式(7.19)求出调整量Q，再按式（7.20）的方法求出新的可行流。如果流有增广链，则得到最
10、大流。而根据定理4后半部分证明中定义 的办法，可以根据vt是否属于 来判断D中有无关于f的增广链。在实际计算时，我们是用给顶点标号的方法来定义 的，在标号过程中，有标号的顶点表示是 中的点，没有标号的点表示不是 中的点。一旦有了标号，就表明找到一条从vs到vt的增广链；如果标号过程无法进行下去，而vt尚未标号，则说明不存在从vs到vt的增广链，于是得到最大流。这时将已标号的点（至少有一个点vs）放在集合 中，将未标号点（至少有一个点vt）放在集合 中，就得到一个最小截集 。4.2 寻求最大流的标号法（Ford , Fulkerson）从一个可行流出发 （若网络中没有给定 ，则可以设 是零流），
11、经过标号过程与调整过程。1） 1） 标号过程在这个过程中，网络中的点或者是标号点（又分为已检查和未检查两种），或者是未标号点，每个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。标号过程开始，总先给vs标上(0,+)，这时vs是标号而未检查的点，其余都是未标号点，一般地，取一个标号而未检查的点vi，对一切未标号点vj：(1) 在弧上 ， ，则给vj标号 。这里 。这时点vj成为标号而未检查的点。(2) 若在弧 上， ，给vj标号 。这里 。这时点vj成为标号而未检查的点。于是 成为标号而已检查过的点，重复上述步骤，一旦 被标
12、上号，表明得到一条从 到 的增广链 ，转入调整过程。若所有标号都是已检查过，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。2） 2 调整过程首先按 及其它点的第一个标号，利用“反向追踪”的办法，找出增广链。例如设vt的第一个标号为 （或 ），则弧 （或相应地 ）是上的弧。接下来检查 的第一个标号，若为 （或 ），则找出 （或相应地 ）。再检查 的第一个标号，依此下去，直到 为止。这时被找出的弧就构成了增广链 。令调整量是 ，即 的第二个标号。令 去掉所有的标号，对新的可行流 ，重新进入标号过程。下面，以例题说明此算法求解过程。例3 用标号法求图7-20所示网络最大流。弧旁的数是
13、解 :对图7-20中各顶点进行标号。首先给 标(0,+)，即 检查 ：在弧 上，因为 ，又有,所以给 标 ；在弧上 ，因为 ，又有,所以给 标 。检查 ：在弧上 ，因为 ，又有,所以给 标 ；在弧上 ，因为 ，又有,所以给 标 ；在弧 上，因为 ，又有,所以给V3标 。因为前面已给v3标过号 ，这里又给 标 ，它们分别表示两条不同的路线，这里不存在修改标号的问题（与最短路不同）。因为我们的目标是尽快找出一条从vs到vt的增广链，即尽快使终点vt获得标号，所以不必在中途过多停留。也就是说在对已标号点vi进行检查时，每次只检查一个相邻点vj（不论前向弧或后向弧均可），再给标号即可，而不必检查所有与vi相邻的点。事实上，其余的相邻点也不会漏掉，因
