教案_图论4

第四节网络最大流问题例连接某产品产地v1和销地v6的交通网如下：v2v5348v3v1v4v65106111735弧（vi，vj）：从vi到vj的运输线，弧旁数字：这条运输线的最大通过能力,制定一个运输方案，使从v1到v6的产品数量最多。弧旁数字：运输能力。问题：这个运输网络中，从v1到v6的最大输送量是多少？v2v5313v3v1v4v61536222一、基本概念与定理1.网络与流定义1给定一个有向图D=（V，A），在V中指定一点vs称为发点，指定另一点vt称为收点，其余点称中间点。任意弧(vi，vj)∈A，有cij≥0，称为弧的容量。称D为一个容量网络。记为D=（V，A，C）。流:定义在弧集A上的一个函数f={f(vi,vj)}，并称f(vi,vj)为弧(vi,vj)上的流量。简记f={fi,j}弧旁数字：容量(a)图是一个网络v2v5348v3v1v4v65106111735v2v5313v3v1v4v61536222弧旁数字：流量cijfijvivjv2v53.14.08.3v3v1v4v65.010.56.311.617.43.25.32.可行流与最大流定义2满足下述条件的流f称为可行流:1)容量限制条件:对每一弧(vi,vj)∈A0≤fij≤cij2)平衡条件:对中间点vi(i≠s,t),有0A),(A),(ijjivvjivvijff)V(:A),(A),(fffvsjjsvvjsvvsjs)V(:A),(A),(fffvtjjtvvjtvvtjtV(f)称为可行流f的流量,即发点的净输出量。如所有fij=0，零流。可行流总是存在的3.增广链对可行流f={fij}：非饱和弧：fijcij饱和弧：fij=cij非零流弧：fij0零流弧：fij=0链的方向：若µ是联结vs和vt的一条链，定义链的方向是从vs到vt。前向弧：弧的方向与链的方向一致，记为µ+。后向弧：弧的方向与链的方向相反，记为µ-。v2v53.34.18.3v3v1v4v65.110.56.311.617.23.25.2µ=(v1,v2,v3,v4,v5,v6)µ+={(v1,v2),(v2,v3),(v3,v4),(v5,v6)}µ-={(v5,v4)}v2v53.34.18.3v3v1v4v65.110.56.311.617.23.25.2定义3设f是一个可行流,µ是从vs到vt的一条链,若µ满足下列条件,称之为(关于可行流f的)一条增广链。(vi,vj)∈µ-0fij≤cij后向弧是非零流弧，(vi,vj)∈µ+0≤fijcij前向弧是非饱和弧，v1v2v3v4v5v68.46.06.53.35.44.截集与截量设S，TV，ST=，始点在S，终点在T中的所有弧的集合，记为（S，T）。ST定义4网络D=(V,A,C）,若点集V被剖分为两个非空集合V1和V1,使vs∈V1，vt∈V1，则把弧集(V1，V1)称为是分离vs和vt的截集。v2v53.34.18.3v3v1v4v65.110.56.311.617.23.25.2=(v1,v2,v3)V1V1=(v4,v5,v6)定义5给一截集（V1，V1），把截集（V1，V1）中所有弧的容量之和称为这个截集的容量（简称为截量），记为C（V1，V1），即)V,(V),(1111)V,C(Vjivvijc定理1可行流f*是最大流，当且仅当不存在关于f*的增广链。二、寻求最大流的标号法（Ford—Fulkerson）从任一个可行流f出发（若网络中没有给定f，则从零流开始），经过标号过程与调整过程。（一）标号过程未标号点未检查已检查标号点网络中的点标号：（前点标记，前点到该点的弧流量可调整量）开始，vs标上（0，∞），vs是标号未检查的点，其余点都是未标号点，一般地，取一个标号未检查的点vi，对一切未标号的点vj。（1）若弧（vi，vj）上，fijcij，则给vj标号(i，l(vj))，l(vj)=min[l(vi),cij-fij],vj成为标号而未检查的点。（2）若弧（vj，vi）上，fji0，则给vj标号(-i，l(vj))，l(vj)=min[l(vi),fji],vj成为标号而未检查的点。fijcijvivj(i,l(vj))l(vj)=min[l(vi),cij-fij],fji0vivj(-i,l(vj))l(vj)=min[l(vi),fji]重复上述步骤，一旦vt被标号，则得到一条vs到vt的增广链。若所有标号都已检查过，而vt尚未标号，结束，这时可行流，即最大流。（二）调整过程从vt开始，反向追踪，找出增广链µ，并在µ上进行流量调整。（1）找增广链如vt的第一个标号为k（或-k），则弧（vk，vt）∈µ（或弧（vt，vk)∈µ)。检查vk的第一个标号，若为i（或-i），则(vi,vk)∈µ(或(vk,vi)∈µ)。再检查vi的第一个标号,依此下去,直到vs。被找出的弧构成了增广链µ。（2）流量调整令调整量是l(vt)，构造新的可行流f′，令uvvfuvvfuvvffjiijjiijjiij'ij),(),(),(-去掉所有的标号,对新的可行流f′={fij′},重新进入标号过程。例用标号法求下图网络的最大流。弧旁的数字是(cij,fij)。解：（一）标号过程。（1）给vs标上（0，∞）；v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，∞）415minmin111,)fc(),v(l)v(lsss在弧（vs，v2）上，fs2=cs2=3,不满足标号条件。（2）检查vs，在弧（vs，v1）上，fs1=1，cs1=5，fs1cs1,给v1标号(s,l(v1)),其中（s，4）（3）检查v1，在弧（v2，v1）上，f210，给v2标号(-1,l(v2)),,,f),v(l)v(l114minmin2112在弧（v1，v3）上，f13=2，c13=2，不满足标号条件。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，∞）（s，4）（-1，1）（4）检查v2，在弧（v3，v2）上，f32=10，给v3标号(-2,l(v3)),这里,11,1min),(min)(3223fvlvl（-2，1）在弧（v2，v4）上，f24=3，c24=4，f24c24,给v4标号(2,l(v4)),其中,,min)fc(),v(l)v(l111min242424（5）检查v3，在弧（v3，vt）上，f3t=1，c3t=2，f3tc3t，给vt标号(3,l(vt)),这里,,min)fc(),v(lmin)v(lttt111333vt得到标号，标号过程结束。v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，∞）（s，4）（-1，1）（-2，1）(2，1)(3，1)（二）调整过程：从vt开始逆向追踪，找到增广链。µ（vs,v1,v2,v3,vt）=1，在µ上进行流量=1的调整，得可行流f′如右图所示：v2v3v1vsv4vt(3，3)(4，3)(1，1)(5，3)(5，1)(2，2)(2，1)(1，1)(3,0)（0，∞）（s，4）（-1，1）（-2，1）(2，1)(3，1)v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)去掉各点标号，从vs开始，重新标号。点v1：标号过程无法进行，所以f′即为最大流。V（f′）=3+2=5v2v3v1vsv4vt(3，3)(4，3)(1，0)(5，3)(5，2)(2，2)(2，2)(1，0)(3,0)（0，∞）（s，3）截集：[V1，V1]=[（vs，v2），（v1，v3）]V（f′）=C[V1，V1]=5V1=(vs,v1)V1=(v2,v3,v4,vt)问题：(v2,v1)是不是截集[V1，V1]中的弧？例1下图中，从三口油井①、②、③经管道将油输至脱水处理厂⑦和⑧，中间经④、⑤、⑥三个泵站。已知图中弧旁数字为各管道通过的最大能力（吨/小时），求从油井每小时能输送到处理厂的最大流量。87654321201030102015302050102050多源、多汇的最大流问题单源、单汇。s208015t6050xv1v6v2v4v5v3y141694197226125313156例2v2v5v34931064343482v1v5v4vtvs练习例3某产品从仓库运往市场销售。已知各仓库的可供量、各市场的需求量及从i仓库至j仓库的路径的运输能力如下表（表中0代表无路可通），试求从仓库可运往市场的最大流量？市场j仓库i1234可供量ABC300201001001040405052020100需求量20206020多源、多汇的最大流问题。3010401050ABC4321510401020s1002020t60202020