《最大流问题》PPT课件.ppt

1,第4节 网络最大流问题,例 连接某产品产地vs和销地vt的交通网如下：,弧（vi，vj）：从vi到vj的运输线， 弧旁数字：这条运输线的最大通过能力,制定一个运输方案，使从vs到vt的产品数量最多。,2,弧旁数字： 运输能力。,问题：这个运输网络中，从vs到vt的最大输送量是多少？,3,7.4.1最大流的基本概念与定理,（1）. 网络流,网络流 对于网络G=（V，A，C） ，定义在弧集合A上的 一个函数f = f(vi ,vj) 称为网络流， f(vi , vj) （简称fij）为弧aij A上的流。,容量：在有向图上，每条弧上给出的最大通过能力（最大可能负载）。cij 流量：网络中加在弧上的负载量（实际负载量）。 fij,4,弧旁数字： 容量,弧旁数字： 流量,5,6,（2）. 可行流,可行流 满足下述条件的流 f 称为可行流:,1)容量限制条件: 对每一弧(vi , vj )A 0fij cij,2)平衡条件: 对中间点vi (is,t ),有,V( f ) 称为可行流 f 的流量,即发点的净输出量。,如所有fij=0， 零流。,可行流总是存在的,7,（3）. 最大流,若 V（f *） 为网络可行流，且满足： V（f *）=MaxV（f ）f 为网络D中的任意 一个可行流，则称f *为网络的最大流。,（4）.前向弧与后向弧,设=（x,u，v,A）是网络G中的一条初等链并且定义链的方向是从x到A。若D中有弧（u，v），与方向一致，则称（u，v）为链的前向弧，若D中有弧（u，v），与方向相反,则称（v, u），为链的后向弧。,8,（5）. 增广链,对可行流 f = fij ：,非饱和弧：fij cij,饱和弧：fij =cij,非零流弧：fij 0,零流弧：fij =0,链的方向：若是联结vs和vt的一条链，定义链的方向是从vs到vt 。,9, = (v1,v2,v3,v4,v5,v6 ),+=(v1,v2) ,(v2,v3), (v3 , v4),(v5,v6), - =(v4,v5),10,增广 链 设 f 是一个可行流, 是从vs 到vt 的一条链,若满 足下列条件,称之为关于可行流 f 的一条增广 链。,(vi , vj ) - 0 fij cij 后向弧 是非零流弧，,(vi , vj ) + 0 fij cij 前向弧是 非饱和弧，,11,（6）. 截集与截量,对于有向网络G=(V,A,C） ，若S为V的子集， ，则称弧集 为网络G的一个截集，并将截集中所有弧容量之和称为截容量，即 为截集 的截容量（简称为截量）。,（7）最小截与最小截量,若 是容量网络中所有截集中截量最小的截集，即 则称 为G上的最小截， 为上的最小截量。,12,性质 任何一个可行流的流量V(f)都不会超过任一截集的容量。即,可行流f*，截集(V1*，V1*), 若V(f*)=C( V1*，V1*），,则f*必是最大流， (V1*，V1*) 必是D的最小截集。,定理 若f*是网络G=（V，A，C）上的可行流，则 可行流f*为最大的充要条件为中不存在关 于f*的增广链。,最大流最小截量定理。任一个网络D中，从vs 到 vt的最大流的流量等于分离vs，vt的最小截集的容量。,13,7.4.2寻求最大流的标号法（FordFulkerson）,从任一个可行流 f 出发（若网络中没有给定 f ，则从零流开始），经过标号过程与调整过程。,（一）标号过程,14,标号：,开始，vs 标上（0，），vs 是标号未检查的点，其余点都是未标号点，一般地，取一个标号未检查的点vi ，对一切未标号的点vj 。,（1）若弧（vi，vj）上，fijcij，则给vj 标号(i，l(vj)，,l(vj)=minl (vi), cij-fij, vj 成为标号而未检查的点。,（2）若弧（vj，vi）上，fji0，则给vj 标号(-i， l (vj)，,l (vj)=minl (vi), fji, vj 成为标号而未检查的点。,15,重复上述步骤，一旦vt被标号，则得到一条vs到vt的增广链。若所有标号都已检查过，而vt尚未标号，结束，这时可行流，即最大流。,（二）调整过程,从vt 开始，反向追踪，找出增广链 ，并在上进行流量调整。,（1）找增广链,如vt 的第一个标号为k（或-k），则弧（vk，vt）（或弧（vt，vk) )。检查vk 的第一个标号，若为i（或-i），则(vi,vk) (或(vk,vi) )。再检查vi 的第一个标号,依此下去,直到vs 。被找出的弧构成了增广链 。,16,（2）流量调整,令调整量是 l(vt)，构造新的可行流 f ，,令,去掉所有的标号,对新的可行流 f = fij,重新进入标号过程。,17,例 用标号法求下图网络的最大流。弧旁的数字是( cij , fij)。,解：（一）标号过程。,（1）给vs标上（0，）；,v2,v3,v1,vs,v4,vt,(3，3),(4，3),(1，1),(5，3),(5，1),(2，2),(2，1),(1，1),(3,0),（0，）,在弧（vs，v2）上， fs2=cs2=3, 不满足标号条件。,（vs，4）,18,（3）检查v1，在弧（v2，v1）上，f210， 给v2标号 (-1, l(v2),在弧（v1，v3）上，f13=2， c13=2，不满足标号条件。,（-v1，1）,（4）检查v2，在弧（v3，v2）上，f32=10， 给v3标号 (-2, l(v3), 这里,（-v2，1）,19,在弧（v2，v4）上，f24=3，c24=4，f24c24, 给v4标号(2, l(v4), 其中,（5）检查v3，在弧（v3，vt）上，f3t=1， c3t=2， f3tc3t， 给vt标号 (3, l(vt), 这里,vt得到标号，标号过程结束。,(v2，1),(v3，1),20,（二）调整过程,：从vt 开始逆向追踪，找到增广链。,（vs,v1,v2,v3,vt） =1，,在上进行流量 =1的调整，得 可行流 f 如右 图所示：,21,去掉各点标号，从vs开始，重新标号。,点v1：标号过程 无法进行，所以 f 即为最大流。,V（f ）=3+2=5,（0，）,（vs，3）,22,例 用标号法求下图网络的最大流。弧旁的数字是( cij , fij)。,23,解： 第一轮 标号过程 （1）vs标（0，+），vs为已标号未检查点。 （2）检查vs，给v2标号（vs，l(v2)） ，vs成为已标号已检查的点，v2成为已标号未检查的点。 （3）检查v2，给v1标号（-v2，l(v1)） 。同理给v4标号为（v2，1），v2成为已标号已检查的 点，v1，v4成为已标号未检查的点。 （4）检查v1，给v3标号为（v1，2），v3成为已标号未检 查的点。 （5）检查v3，给vt标号为（ v3 ，2）。 因为vt已被标号，所以说明找到一条增广链。 调整过程 按点的第一个标号，以vt点开始，回溯找到一条增广 链， 如下图红线所示：,24,vt,(0， +),（vs，4）,（-v2，2）,（v2，1）,（v1，2）,（v3，2）,25,vt,在增广链上进行了流量调整。,前向弧,后向弧,于是调整后流量如下图所示。,(0， +),（vs，4）,（-v2，2）,（v2，1）,（v1，2）,（v3，2）,26,vt,27,第二轮： 标号过程 （1）vs标（0，+），vs为已标号未检查点。 （2）检查vs，给v2标号（vs，2），v2成为已标号未检查 的点。 （3）检查v2 ，给v4标号（ v2 ，1）， v4成为已标号未检 查的点。 （4）检查v4 ，给vt标号为（ v4 ，1）， vt被标，转入下 一阶段。 调整过程 根据标号过程，以vt点开始，回溯找到一条增广链，如 下图红线所示。,28,vt,（v2，1）,（v4，1）,29,增广链上的三个弧都为前向弧，于是调整如下：,于是新调整的流量如下图所示。,vt,(0， +),（vs，2）,（v2，1）,（v4，1）,30,第三轮 vs标（0,+）， v2标号（vs，1），检查v2点，标号 过程无法继续下去，于是说明了对于上图所示的新 流，不存在增广链，上图所示的流就是最 大流，算法结束。 最大流量=3+3+2=8 最小截集为（ vs, v1 ），（v2, v3），（v2,v4）， 最小截量为8。,vt,(0， +),（vs，1）,