经典网络流教程.ppt

《经典网络流教程.ppt》由会员分享，可在线阅读，更多相关《经典网络流教程.ppt（49页珍藏版）》请在三一文库上搜索。

1、网络流 网络可以被想 象成一些输水 的管道.括号内 右边的数字表 示管道的容量, 左边的数字表 示这条管道的 当前流量。 最大流为5？ 一个简单的例子-网络的最大流问题 a ts b c d (3,4) (2,2) (3,3) (2,2) (1,1) (0,2) (3,3) (3,4) 一些符号和定义 nV表示整个图中的所有结点的集合. nE表示整个图中所有边的集合. nG = (V,E) ,表示整个图. ns表示网络的源点,t表示网络的汇点. n对于每条边(u,v),有一个容量c(u,v) (c(u,v)=0) n如果c(u,v)=0，则表示(u,v)不存在于网络中。 n如果原网络中不存在边

2、(u,v)，则令c(u,v)=0 n对于每条边(u,v),有一个流量f(u,v). 网络流的三个性质 1、容量限制: fu,v=cu,v 2、反对称性：fu,v = - fv,u 3、流量平衡: 对于不是源点也不是汇点的 任意结点,流入该结点的流量和等于流出该 结点的流量和。 结合反对称性,流量平衡也可以写成: 只要满足这三个性质,就是一个合法的网络 流,也称为可行流。可行流至少有一个零流 。 最大流问题 n定义一个网络的流量（记为|f|）= n最大流问题，就是求在满足网络流性质的情况下 ，|f|的最大值。 弧的分类 n若给定一个可行流F=(Fij),我们把网络中Fij=Cij的 弧称作饱和弧

3、， Fij0的弧称作非零流弧 n若P是网络中联结源点s和汇点t的的一条路(不用 管边的有向性)，我们定义路的方向是从Vs到Vt， 则路上的弧被分为两类：一类与路的方向一致， 称为前向弧；另一类和路的方向相反，称为后向 弧 残量网络 n为了更方便算法的实现，一般根据原网络定义一 个残量网络。其中r(u,v)为残量网络的容量。 nr(u,v) = c(u,v) f(u,v) n通俗地讲：就是对于某一条边（也称弧），还能 再有多少流量经过。 nGf残量网络,Ef表示残量网络的边集. (a,b) 表示 (流量f,容量c) v1 t s v2 (2,2) (4,4) (2,4) (0,3) (2,2)

4、v1 t s v2 2 3 2 4 2 2 如果网络中一条边的容量为0,则认为这条边不在残量网络中 。r(s,v1)=0,所以就不画出来了。另外举个例子：r(v1,s) = c(v1,s) f(v1,s) = 0 (-f(s,v1) = f(s,v1) = 4. 图1 原网络图2 残量网络 n从残量网络中可以清 楚地看到： n因为存在边(s,v2) = 3,我们知道从S到v2 还可以再增加3单位的 流量； n因为存在边(v1,t) = 2,我们知道从v1到t还 可以再增加2单位的流 量。 v1 t s v2 2 3 2 4 2 2 为什么要建立后向弧 n其中像(v1,s)这样的边 称为后向弧,

5、它表示从 v1到s还可以增加4单位 的流量。 n但是从v1到s不是和原 网络中的弧的方向相反 吗？显然“从v1到s还可 以增加4单位流量”这条 信息毫无意义。那么， 有必要建立这些后向弧 吗？ v1 t s v2 2 3 2 4 2 2 为什么要建立后向弧 n显然，例1中的画出来的不是一个最大流。 n但是，如果我们把s - v2 - v1 - t这条路径经过的弧 的流量都增加2,就得到了该网络的最大流。 n注意到这条路径经过了一条后向弧:(v2,v1)。 n如果不设立后向弧，算法就不能发现这条路径。 n从本质上说，后向弧为算法纠正自己所犯的错误提供了可 能性，它允许算法取消先前的错误的行为（让

6、2单位的流 从v1流到v2) 可改进路（增广路） n可改进路定义：在残 量网络中的一条从s通 往t的路径，其中任意 一条弧(u,v)，都有 ru,v0。（每一条 前向弧都是非饱和弧 ，每一条后向弧都是 非零流弧） n绿色的即为一条可改 进路。 v1 t s v2 2 3 2 4 2 2 可改进路算法 n可改进路算法：每次用BFS找一条可改进路，然 后沿着这条路径修改流量值（实际修改的是残 量网络的边权），使得总流量变得更大，修正 的方法是： 1、不属于可改进路P的弧一概不变 2、对于可改进路P上的所有前向弧加上a，后向 弧减去a，这里a是一个可改进量。a既要尽量大 ，又要保证变化后0=Fij

7、2证明: 显然.假设有增广路径,由于增 广路径的容量至少为1,所以用这个增广路径 增广过后的流的流量肯定要比f的大,这与f 是最大流矛盾. 结论2(点集总流量为零) n不包含s和t的点集,与它相关联的边上的流量之和为0. n证明: f(X,V) = = (由流量平衡) = 0 结论3 n任意割的流量等于整个网络的流量. n证明: nf(S,T) = f(S,V) f(S,S) (由辅助定理1) = f(S,V) (由辅助定理1) = f(S,V) + f(S s,V) (同上) = f(s,V) (由辅助定理2) = |f| (由|f|的定义) 结论4 n网络的流量小于等于任意一个割的容量.(

8、注意这个与辅助 定理3的区别.这里是容量) n即|f| = c(S,T) n证明: |f| = f(S,T) = (由定义) 3证明: 定义S = s v | 在残量网络中s到v有一 条路径 ; T = V- S. 则 (S,T) 是一个割. n|f| = f(S,T) (由辅助定理3) n而且,r(S,T) = 0. 假设不为0,则在残量网络中, 两个集合 间必定有边相连,设在S的一端为v,在T的一端为u. 那么,s 就可以通过v到达u,那么根据S的定义,u就应该在S中.矛盾 . 所以,|f| = f(S,T) = c(S,T) r(S,T) = c(S,T) 1、f是最大流 2、残量网络中

9、找不到增广路径 3、|f| = c(S,T) n3 - 1证明: |f| 0),那么|f|+d肯定不能满足上面 的条件. 1、f是最大流 2、残量网络中找不到增广路径 3、|f| = c(S,T) 标号法寻求可改进路（Ford-Fulkerson算法） 从一个可行流F出发（可以设为零流），经过标号过程和调整过程。 标号过程: 网络中的顶点或者是标号点(分为已检查和未检查两种)，或者是未标 号点，每个标号点分为两部分(标号从哪个顶点得到，确定可改进量a)。 标号过程开始，总先给Vs标上(0, +)，这时是标号而未检查的顶 点，其余都是未标号点。取一个标号而未检查的标号Vi ，对一切未标号点 Vj

10、 ： 在Vi的全部相邻顶点都已标号后， Vi成为标号而已检查过的顶点。重 复上述步骤，一旦Vt被标上号，表明得到一条从Vs到Vt的可改进路P， 转入调整过程。 标号法寻求可改进路（Ford-Fulkerson算法） 调整过程： 采用“倒向追踪”的方法，从Vt开始，利用第一个标号找出可改进路P，并以 Vt的第二个标号L (Vt)作为改进量a，改进P上的流量。 例如：设Vt的第一个标号为Vk(或-Vk)，则弧(Vk,Vt)(或(Vt,Vk)是P上的 弧，接下来再检查Vk的第一个标号，如此继续下去.，直到查倒Vs为止。 这时被找出的弧构成了P。 令改进量a=L(Vt)，即Vt的第二个标号。 去掉所有

11、的标号，对新的可行流Fij，重新进入标号过程。直到标号过程无法 继续。 例1 求如下网络的最大流 V2 VtVs V1 V4 V3 (3,3) (1,5) (3,4) (3,5) (1,1) (1,1) (2,2) (1,2) (0,3) 标号法分析例1 1.标号过程 (1)首先给Vs标上(0,+) (2)检查Vs。弧(Vs,V2)上，Fs2=Cs2=3，不满 足标号条件；弧(Vs,V1)上，Fs1=10，则 给V2记下标号为(-V1,L(V2)，其中L(V2) minL(V1),F21=min4,1=1 标号法分析例1 (4)检查V2。弧(V2,V4)上，F24=3C24=4， 则给V4标号

12、(V2,L(V4)，其中 L(V4)=minL(V2),C24-F24=min1,1=1 同理，标注V3为(-V2,1). (5)在V3，V4中任选一个进行检查，如V4。弧 (V4,Vt)上， F4t=30时有上下界的网络不一定 存在可行流了。 那么如何判断一个有上下界的网络有无可行流呢 ？ 容量有上下界的网络的最大流 算法思路：将原网络转换为一个附加网络。 1.新增加两个顶点 和 ，分别称为附加源和附加汇 2.对原网络N的每个顶点U加一条新弧 ，这条 弧的容量为以U为尾的弧的容量下限之和。 3.对原网络N的每个顶点U加一条新弧 ，这条 弧的容量为以U为头的弧的容量下限之和。 4.原网络的弧仍

13、保留，弧容量修正为C(e) -B(e) 5.再添两条新弧e=st,e=ts。其容量均为 6.用标号法求此新网络的最大流，若结果能使流出 的一 切弧都满载，则原网络有可行流F(e) F(e) B(e)， 否则无可行流。 7.在原网络中运用标号法将可行流放大，从而得出最大流 。 容量有上下界的网络的最大流 例原网络，第一个数字为 B(e)，第二个为C(e) 容量有上下界的网络的最大流 按照上述算法求得 附加网络，并用标 号法求此网络的最 大流。 发现从 流出的流 都满载，所以有可 行流。 容量有上下界的网络的最大流 按照F(e) F(e) B(e) 将此最大流还原为原 网络的最大流 容量有上下界的

14、网络的最大流 用标号法进行可行流放大，得到最大流10 容量有上下界的网络的最小流 n按照前述附加网络方法求得可行流，只不过在放 大可行流时，以t为源点，s为汇点进行，倒向求 出的最大流为从s到t到的最小流。 最小费用最大流问题 n求运输量最大且费用最少 的运输方案 n求一个最大流，使得此式 取最小值 最小费用最大流问题 算法思想： 若F是所有可行流中费用最小的，而P是关于F的 所有可改进路中费用最小的，沿着P取调整F最大 ，则得到的流为最小费用最大流。 最小费用最大流问题 步骤： 1.取F(0)=0; 2.若第k-1步得到最小费用流F(k-1)，则构造赋权有向图 W(F(k-1)，在W(F(k

15、-1)中，寻求从Vs到Vt的最短路径。 若不存在最短路(即最短路为+)，则F(k-1)为最小费用最大 流；若存在最短路，则为可改进路P，在P上对F(k-1)进行调 整。 3.其中，赋权有向图W(F(k)的构造规则为：其顶点是原网络 的顶点，而每条弧变为两个方向相反的弧，定义权值Wij为 最小费用最大流问题 4.在P上对F(k-1)进行调整的方法为： 5.得到新流F(k)，再对F(k)重复上述步骤，直到 不存在最短路径。 最小费用最大流问题例 最小费用最大流问题例 最小费用最大流问题例 最小费用最大流问题例 最小费用最大流问题例 作业 n本课算法的实现 n标号法 n容量有上下界网络的最大流 n容量有上下界网络的最小流 n最小费用最大流