第8章 最大流.pptx

第八章 最大流;内容提要 ;重点与难点 ;学习目的与要求 ; 最大流问题是关于流网络的最简单问题：在不违背容量限制的条件下，把物质从源点传输到汇点的最大速率是多少？ 这个问题可以由有效的算法来解决。本章介绍最大流问题的两种求解方法。分别是Ford-Fulkerson方法、压入与重标记方法。;流网络是一个有向图G=（V，E），其中每条边(u,v)均有一非负容量c(u,v)≥0.如果(u,v)不是E中的边，则假定c(u,v)=0。流网络中有两个特别的顶点：源点s和汇点t。为方便起见，假定每个顶点均处于从源点到汇点的某条路径上。;现在对流给出形式化定义。设G=(V,E)是一个流网络，其容量函数为c。设s为网络的源点，t为汇点。G的流是一个实值函数f:V×V→R,且满足下列三个性质： 容量限制：对所有u,v∈V,要求f(u,v)≤c(u,v) 反对称性：对所有u,v∈V,要求f(u,v)=-f(v,u) 流守恒性：对所有u∈V-{s,t},要求 称f(u,v)是从顶点u到顶点v的流。 f(u,v)可以为正、为零、为负。 流f的值定义为： 即从源点出发的 总流（｜·｜表示流的值，并不表示绝对值或势） ;在最大流问题中，给定一个具有源点s和汇点t的流网络G，希望找出从s到t的最大值流。 ;下面我们看看关于流的三个性质： （1）容量限制说明从一个顶点到另一个顶点的网络流不能超过设定的容量。 （2）反对称性说明从顶点u到顶点v的流是其反向流的取负。 （3）流守恒性说明从非源点或非汇点的顶点出发的总网络流为0. 由此得： 即进入一个顶点的总流为0. ;当(u,v)和(v,u)都不在E中，则u,v之间不可能有网络流。即f(u,v)=f(v,u)=0. 正网络流： 进入一个顶点v的总的正网络流定义为： 离开某个顶点的正网络流定义为： 定义某个顶点处的总的净流为离开该顶点的总的正流量减去进入该顶点的总的正流量。;根据流守恒性，进入某个非源点非汇点顶点的正网络流必须等于离开该是顶点的正网络流。 具有多个源点和多个汇点的流网络：;网络流的一个实例： 可以用流网络把图1所示的卡车运输问题模型化。 Lucky Puck 公司在Vancouver有一家制造冰球的工厂（源点s），在Winnipeg有一个存储产品的仓库（汇点t）。Lucky Puck从另外一家公司租用卡车，把冰球从工厂运到仓库。因为卡车按指定路线（边）在两城市（顶点）间行驶且其容量有限。因此在图1中，Lucky Puck每天在城市u和v之间至多装运 c(u,v)箱产品。Lucky Puck公司无法控制运输路线和卡车的运输能力。他们的目标是确定每天所能运输的最大箱数，并按这一数量进行生产。;网络流的一个实例： 从表面看，将运输“流”模拟成网络流是非常合式的。因为每天从一个城市运输到另一个城市的箱数受到容量限制。此外必须遵守流守恒性质。在一种稳定状态下，球进入运输网络中间某个城市的速度，要等于它们离开该城市的速度，否则就会有球堆积在中间城市中。;但是，在运输和流之间有一点细微差别。Lucky Puck公司可以将球从Edmonton运输到Calgary,也可以从Calgary运输到Edmonton.假设每天运输8箱从Edmonton到Calgary,每天有3箱从Calgary到Edmonton。而将这些运输线路直接表示成网络流似乎很自然，但是实际上不能这样做。因为这样做违背反对称性的要求。;Lucky Puck公司可能会意识到每天从Edmonton运8箱至Calgary以及3箱从Calgary到Edmonton没有意义的。因为这与他们每天从Edmonton运5箱到Calgary,从Calgary运0箱到Edmonton的效果是一样的。这样做可以节省成本。用流f(v1,v2)=5和f(v2,v1)=-5来表示后一种情形。从效果看，从v1到v2每天8箱中的3箱被从v2到v1每天的3箱抵消了。;通常，用抵消处理，可以将两城市间的运输用一个流来表示。该流在两个顶点之间至多一条边上是正的。也就是说，任何在两城市间相互运输球的情况都可以通过抵消将其转化成一个相等情形，球只在一个方向上运输：沿正向流的方向。 以后我们在讨论算法时将隐式地利用抵消处理。;对流的处理： 如果X和Y是顶点的集合，则 将流守恒性表示为对所有u∈V-{s,t},有f(u,V)=0 同时，为方便起见，f(s,V-s)=f(s,V)，项V-s就是指集合V-{s}. ;8.1 流网络;8.1 流网络;8.2 Ford-Fulkerson方法;8.2 Ford-Fulkerson方法;8.2 Ford-Fulkerson方法;8.2 Ford-Fulkerson