2014 ACM 图论4 网络流-1

《2014 ACM 图论4 网络流-1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM程序设计实训(二)图模型——最大流华南师大讲稿问题例1：下图是输油管道网，vs为起点，vt为终点，v1，v2，v3，v4,v5,v6为中转站，边上的数字表示该管道的最大输油能力（也称容量），记为cij，问应如何安排各管道输油量，才能使从到的总输油量最大？v5v14543v4233vvstv53252vv63华南师大讲稿最大流问题最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有商品流、人流、车流、货物流、供水系统中有水流，金融系统中有现金流，通信系统中有信息流，等等。华南师大讲稿华南师大讲稿•

2、如果把上面的网络流模型理解为配送情况，我们可以将图中的流值解释为发送商品的数量，于是这个图就描述从0到5发送4个商品的过程有三步：•首先：从0到1发出2个商品，并从0到2也发出2个商品，在这些顶点上均留有2个商品。•其次，从1到3、从1到4、从2到3以及2到4分别发出了1个商品，使得3和4均留有2个商品。•第三，通过从3到5以及4到5各自发出2个商品，这样5就留有了4个商品，从而完成了整个传送。华南师大讲稿问题1（单点对单点）例1：下图是输油管道网，vs为起点，vt为终点，v1，v2，v3，v4,v5,v6

3、为中转站，边上的数字表示该管道的最大输油能力（也称容量），记为cij，问应如何安排各管道输油量，才能使从到的总输油量最大？v5v14543v4233vvstv53252vv63华南师大讲稿问题2（多点对多点）•例2：一个计算机厂家有两个生产点x1,x2，两个送货点y1,y2，如下图所示，各边表示该路线最大货物运送量，或者容量。•问题：厂家希望找出，每边的运送量不会超出其容量限制，通过这个交通网络能够运送的最大货物量。华南师大讲稿一.网络最大流的有关概念1.有向图与容量网络对图中每条边规定指向的图称为有向图，

4、有向图的边称为弧，记作(vi,vj)，表示方向从点vi指向点vj，有向图是点与弧的集合，记作D(V,A)。弧(vi,vj)的最大通过能力，称为该弧的容量，记为c(vi,vj)，或简记为cij。定义了弧容量的网络称为容量网络。华南师大讲稿一.网络最大流的有关概念容量网络通常规定一个发点(源点，记为s)一个收点(汇点，记为t)，网络中其余的点称为中间点。从发点到收点之间允许通过的最大流量称为最大流。多个收(发)点的网络可以转换为只含一个收(发)点。华南师大讲稿2.流与可行流流是指加在网络各条弧上的一组负载量，对

5、加在弧(vi,vj)上的负载量记作f(vi,vj)，或简记作fij，若网络上所有的fij=0，这个流称为零流。华南师大讲稿2.流与可行流可行流：网络中满足下述条件(1)、(2)的流为：(1)容量限制条件:对所有弧有0≤f(vi,vj)≤c(vi,vj)(2)中间点平衡条件：∑f(vi,vj)-∑(vj,vi)=0(i≠s,t)•零流是可行流。华南师大讲稿3.流量与最大流流量：网络中从s→t的负载量，用v(f)，则v(f)f(vs,vj)f(vj,vt)jj•求最大流就是求v(f)的最大值。华南师大讲

6、稿二.割和流量割是指将容量网络中的发点和收点分割开，并使s→t的流中断的一组弧的集合。弧旁数字为cij(fij)上图KK将网络上的点分割成V={S,v1,v2}和V={v3,v4,t}两个集合,并有s∈V,t∈V,称弧的集合(V,V)={(v1,v3),(v2,v4)}是一个割。注意，这里不包含(v3,v2)。割的容量是组成它的集合中各弧容量之和，用c(V,V)表示，c(V,V)c(v,v)ij华南师大讲稿(i,j)(V,V)用f(V,V)表示通过割(V,)V中所有V→V方向弧的流量的总和，f(V,V

7、)表示通过割中所有V→V方向弧的流量的总和，则有：f(V,V)f(vi,vj),f(V,V)f(vj,vi)(i,j)(V,V)(j,i)(V,V)从s→t的流量等于通过割的从V→V的流量减去V→V的流量，有：v(f)f(V,V)f(V,V)用v*(f)表示网络中从s→t的最大流，则有***v(f)f(V,V)f(V,V)最大流v*(f)应小于最小割的容量(用c*(V,)V表示)****v(f)f(V,V)f(V,V)c(V,V)上例中最大流不会超过14.{(3,t),(2,4)}

8、为网络的最小割.华南师大讲稿三.最大流最小割定理如果在网络的发点和收点之间能找到一条链，在这条链上所有指向为s→t的弧（称前向弧，记作μ+），存在f0(非零)，这样的链称增广链。当有增广链存在时，找出cifi,对min0f,对i再令f,对所有iffi,对所有华南师大讲稿f,对非增广链上的