教案17图论最大流问题ppt课件.ppt

《教案17图论最大流问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四节网络最大流问题例连接某产品产地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，称为

2、弧的容量。称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≤fi

3、j≤cij2)平衡条件:对中间点vi(i≠s,t),有V(f)称为可行流f的流量,即发点的净输出量。如所有fij=0，零流。可行流总是存在的3.增广链对可行流f={fij}：非饱和弧：fij0零流弧：fij=0链的方向：若µ是联结vs和vt的一条链，定义链的方向是从vs到vt。前向弧：弧的方向与链的方向一致，记为µ+。后向弧：弧的方向与链的方向相反，记为µ-。v2v53.34.18.3v3v1v4v65.110.56.311.617.23.25.2µ=(v1,v2,v3,v4,v5

4、,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)∈µ-0

5、集合，记为（S，T）。STv2v53.34.18.3v3v1v4v65.110.56.311.617.23.25.2=(v1,v2,v3)V11=(v4,v5,v6)定义5给一截集（V1，V1），把截集（V1，V1）中所有弧的容量之和称为这个截集的容量（简称为截量），记为C（V1，V1），即不难证明，任何一个可行流的流量V(f)都不会超过任一截集的容量。即可行流f*，截集(V1*，V1*),若V(f*)=C(V1*，V1*），则f*必是最大流，(V1*，V1*)必是D的最小截集。定理1可行流f*是最大流，当且仅当不存在关于f*的

6、增广链。证明：若f*是最大流，设D中存在关于f*的增广链µ，由增广链的定义，可知>0,令不难验证，是一个可行流,且=min令这与f*是最大流的假设矛盾。设D中不存在关于f*的增广链，证明f*是最大流。定义V1*，令vs∈V1*,若vi∈V1*,且弧(vi,,vj)上,fij*0，则令vj∈V1*。因为不存在关于f*的增广链，故vt∈V1*，记V1*=VV1*，得截集（V1*，V1*），显然有所以V(f*)=C（V1*，V1*）。于是f*必是最大流。

7、定理2最大流最小截定理。任一个网络D中，从vs到vt的最大流的流量等于分离vs，vt的最小截集的容量。二、寻求最大流的标号法（Ford—Fulkerson）从任一个可行流f出发（若网络中没有给定f，则从零流开始），经过标号过程与调整过程。（一）标号过程标号：（前点标记，前点到该点的弧流量可调整量）开始，vs标上（0，∞），vs是标号未检查的点，其余点都是未标号点，一般地，取一个标号未检查的点vi，对一切未标号的点vj。（1）若弧（vi，vj）上，fij

8、j-fij],vj成为标号而未检查的点。（2）若弧（vj，vi）上，fji>0，则给vj标号(-i，l(vj))，l(vj)=min[l(vi),fji],vj成为标号而未检查的点。fij