《网络流算法专题》.ppt

该【《网络流算法专题》 】是由【相惜】上传分享，文档一共【52】页，该文档可以免费在线阅读，需要了解更多关于【《网络流算法专题》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。图论算法---最大流问题长沙市雅礼中学朱全民编辑课件运输网络现在想将一些物资从S运抵T,必须经过一些中转站。连接中转站的是公路,每条公路都有最大运载量。每条弧代表一条公路,弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T?4248473621STV1V2V3V4公路运输图编辑课件根本概念这是一个典型的网络流模型。为了解答此题,我们先了解网络流的有关定义和概念。假设有向图G=(V,E)满足以下条件:有且仅有一个顶点S,它的入度为零,即d-(S)=0,这个顶点S便称为源点,或称为发点。有且仅有一个顶点T,它的出度为零,即d+(T)=0,这个顶点T便称为汇点,或称为收点。每一条弧都有非负数,叫做该边的容量。边(vi,vj)的容量用cij表示。那么称之为网络流图,记为G=(V,E,C)编辑课件可行流可行流 对于网络流图G,每一条弧(i,j)都给定一个非负数fij,这一组数满足以下三条件时称为这网络的可行流,用f表示它。(i,j)有fij≤ 除源点S和汇点T以外的所有的点vi,恒有: ∑j(fij)=∑k(fjk) 该等式说明中间点vi的流量守恒,输入与输出量相等。3. 对于源点S和汇点T有, ∑i(fSi)=∑j(fjT)=V(f)编辑课件可增广路给定一个可行流f={fij}。假设fij=Cij,称<vi,vj>为饱和弧;否那么称<vi,vj>为非饱和弧。假设fij=0,称<vi,vj>为零流弧;否那么称<vi,vj>为非零流弧。定义一条道路P,起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧,正向弧的全体记为P+;把P上所有与P方向相悖的弧定义为反向弧,反向弧的全体记为P-。譬如在图中,P=(S,V1,V2,V3,V4,T),那么 P+={<S,V1>,<V1,V2>,<V2,V3>,<V4,T>} P-={<V4,V3>}给定一个可行流f,P是从S到T的一条道路,如果满足: fij是非饱和流,并且<i,j>∈P+,fij是非零流,并且<i,j>∈P- 那么就称P是f的一条可增广路。之所以称作“可增广〞,是因为可改进路上弧的流量通过一定的规那么修改,可以令整个流量放大。编辑课件剩余图(剩余网络)剩余图G’=(V,E’)流量网络G=(V,E)中,对于任意一条边(a,b),假设flow(a,b)<capacity(a,b)orflow(b,a)>0那么(a,b)∈E’可以沿着a--->b方向增广编辑课件剩余图中,从源点到汇点的每一条路径都对应一条增广路Capacity=5Capacity=6Capacity=2Flow=2Flow=2Flow=2有向图32224剩余图剩余图中,每条边都可以沿其方向增广剩余图的权值代表能沿边增广的大小编辑课件G=(V,E,C)是的网络流图,设U是V的一个子集,W=V\U,满足S∈U,T∈W。即U、W把V分成两个不相交的集合,且源点和汇点分属不同的集合。对于弧尾在U,弧头在W的弧所构成的集合称之为割切,用〔U,W〕表示。把割切〔U,W〕中所有弧的容量之和叫做此割切的容量,记为C〔U,W〕,即:割切编辑课件割切例如上例中,令U={S,V1},那么W={V2,V3,V4,T},那么,C(U,W)=<S,V2>+<V1,V2>+<V1,V3>+<V1,V4>=8+4+4+1=17编辑课件流量算法的根本理论定理1:对于的网络流图,设任意一可行流为f,任意一割切为(U,W),必有:V(f)≤C(U,W)。定理2:可行流f是最大流的充分必要条件是:f中不存在可改进路。定理3:整流定理。 如果网络中所有的弧的容量是整数,那么存在整数值的最大流。定理4:最大流最小割定理。 最大流等于最小割,即maxV(f)=minC(U,W)。编辑课件