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

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

1、课程讲授：黄玉诚运筹学中国矿业大学(北京)第六章图与网络分析第一节图的基本知识第二节树第三节最短路问题第四节网络最大流问题第五节最小费用最大流问题9/20/2021第四节网络最大流问题8431763511v1v2v3v5v4v6105图10-23是联结某产品产地v1和销地v6的交通网，每一弧(vi，vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数字表示这条运输线的最大通过能力。现在要求制定一个运输方案使从v1运到v6的产品数量最多。图10-239/20/2021③①②②③③②⑥v1v2v3v5v4v6⑤①图10-24给出了一个运输方案，每条弧旁的数字表示每

2、条运输线上的运输数量。这个方案使8个单位的产品从v1运到v6。在这个运输网络中，从v1到v6的最大输送量是多少呢?8431763511v1v2v3v5v4v6105图10-23图10-249/20/2021一、基本概念与基本定理1、网络与流定义1给一个有向图D=(V,A)，在V中指定了一点，称为发点(记为vs)，和另一点，称为收点(记为vt)，其余的点叫中间点。对于每一个弧(vi，vj)∈A,对应有一个c(vi，vj)≥0(或简写为cij)，称为弧的容量。通常把这样的D叫作一个网络。记作D=(V，A，C)。对D中的任一弧(vi，vj)有流量f(vi，vj)(有时也简记作fij)

3、，称集合f={fij}为网络D上的一个流。9/20/20212、可行流与最大流定义2满足下述条件的流f称为可行流：1）容量限制条件：对每一弧(vi，vj)∈A0≤fij≤cij可行流2）平衡条件：对于中间点：流出量＝流入量，即对每个i(i≠s,t)有9/20/2021对于发点vs，式中v(f)称为这个可行流的流量，即发点的净输出量(或收点的净输入量)。于是对于收点vt，或9/20/2021所谓最大流问题就是在网络中，寻找流量最大的可行流，即：求一个流{fij}使其流量v(f)达到最大，并且满足0≤fij≤cij(vi，vj)∈A最大流可行流总是存在的，例如(fij)=0就是一个

4、流量为0的可行流。9/20/20213、增广链若给一个可行流f={fij}，我们把网络中使fij=cij的弧称为饱和弧，使fij0的弧称为非零流弧。若μ是网络中联结发点vs和收点vt的一条链，我们定义链的方向是从vs到vt，则链上的弧被分为两类：一类是弧的方向与链的方向一致，叫作前向弧。前向弧的全体记为μ+。另一类弧与链的方向相反，称为后向弧。后向弧的全体记为μ-。9/20/2021定义3设f是一个可行流，μ是从vs到vt的一条链，若μ满足下列条件,称之为(关于可行流f的)一条增广链。在弧(vi，vj)∈μ+上，0≤

5、fij0。9/20/20214、截集与截量设S,T∈V，S∩T=Φ，我们把始点在S，终点在T中的所有弧构成的集合，记为(S，T)。定义4给网络D=(V，A，C)，若点集V被剖分为两个非空集合V1和，使vs∈V1，vt∈，则把弧集(V1,)称为是(分离vs和vt的)截集。可以看

6、出，从网络中去掉任一截集，则从vs到vt便不存在路。所以，截集是从vs到的vt必经之路。9/20/2021定义5给一截集(V1,)，把截集(V1,)中所有弧的容量之和称为这个截集的容量(简称为截量)，记为c(V1,)，即任何一个可行流的流量v(f)都不会超过任一截集的容量。即9/20/2021显然，若对于一个可行流f*，网络中有一个截集(V1*,)，使v(f*)=c(V1*,),则f*必是最大流，而(V1*,)必定是D的所有截集中容量最小的一个，即最小截集。9/20/2021定理1可行流f*是最大流的充分必要条件是不存在从vs到vt的(关于f*)增广链。证明：(一)必要性用反证

7、法。可行流f*是最大流，假设存在从vs到的vt的(关于f*)增广链。令：9/20/2021由增广链的定义，可知θ>0,令网络上的另一个流：仍为可行流(即满足容量限制条件与平衡条件)，但的总流量等于的流量加θ，即这与是最大流的前提矛盾。9/20/2021(二)充分性：若不存在关于f*增广链，那么f*是最大流。因为不存在关于f*增广链，那么在这种定义下，。令：则。因此，可以得到一个截集。令：若且则令若且则令用下面方法定义点集9/20/2021显然有那么，可行流f*上的流量则f*必然是最大流。9/