《最大流问题》PPT课件.ppt
1,第4节 网络最大流问题,例 连接某产品产地vs和销地vt的交通网如下：,弧（vi，vj）：从vi到vj的运输线，弧旁数字：这条运输线的最大通过能力,制定一个运输方案，使从vs到vt的产品数量最多。,2,弧旁数字：运输能力。,问题：这个运输网络中，从vs到vt的最大输送量是多少？,3,最大流的基本概念与定理,（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,寻求最大流的标号法（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,(0，+),（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）,
