第八章续最大流问题精选文档.ppt
第八章续最大流问题本讲稿第一页，共二十一页 定义7.9.1 设G，是弱连通有向图且C:ER0(其中R0为非负实数集合。)如果加权图G，C满足：i)图中恰有一个结点入度为0，称为源。ii)图中恰有一个结点出度为0，称为汇。则称G，C为网络，C为该网络的容量函数。对G的任意边e,称C(e)为e的容量。基本概念基本概念3511 42352sv2v1v3v4t 本讲稿第二页，共二十一页 所谓网络上的流，是指定义在弧集E上的函数ff(vi,vj)，并称f(vi,vj)为弧(vi,vj)上的流量，简记为fij。3,15,21,01,0 4,12,23,15,22,1sv2v1v3v4t标示方式：每条边上标示两个数字，第一个是容量，第二是流量本讲稿第三页，共二十一页可行流、可行流的流量、最大流。可行流是指满足如下条件的流：（1）容量限制条件：对G中每条边(vi,vj),有（2）平衡条件：对中间点，有：（即中间点vi的物资输入量等于输出量）对收点vt与发点vs，有：（即vs发出的物资总量等于vt接收的物资总量），W是网络的总流量。本讲稿第四页，共二十一页可行流总是存在的，例如f=0就是一个流量为0的可行流。所谓最大流问题就是在容量网络中寻找流量最大的可行流。一个流f=fij，当fij=cij，则称f对边(vi,vj)是饱和的，否则称f对边(vi,vj)不饱和。最大流问题实际上是一个线性规划问题。但利用它与图的密切关系，可以利用图直观简便地求解。本讲稿第五页，共二十一页 给定容量网络G(V,A,E)，若点集V被剖分为两个非空集合V1和V2，使 sV1，tV2，则把弧集(V1,V2)称为（分离s和t的）割割集集。显然，若把某一割集的弧从网络中去掉，则从s到t便不存在路。所以，直观上说，割集是从s到t的必经之路。3511 42352sv2v1v3v4t注：有向边也称为弧。本讲稿第六页，共二十一页割集的例子sv1v4v3tv2边集（s,v1），（v1,v3），（v2,v3），（v3,t），（v4,t）是G的割集。其顶点分别属于两个互补不相交的点集。去掉这五条边，则图不连通，去掉这五条边中的任意1-4条，图仍然连通。本讲稿第七页，共二十一页 定义7.9.5 割集的容量(简称割量)最小割集割集(V1,V2)中所有起点在V1，终点在V2的边的容量的和称为割集容量。例如下图中所示割集的容量为53511 42352sv2v1v3v4t在容量网络的所有割集中，割集容量最小的割集称为最小割集（最小割）。本讲稿第八页，共二十一页 对于可行流ffij，我们把网络中使fijcij的弧称为饱和弧，使fij0的弧称为非零流弧。设f是一个可行流，是从s到t的一条链，若满足前向弧都是非饱和弧,后向弧都是都是非零流弧,则称是（可行流f的）一条增广链。3,15,21,01,0 4,12,23,15,22,1sv2v1v3v4t 若是联结源点s和汇点t的一条链，我们规定链的方向是从s到t，则链上的弧被分成两类：前向弧、后向弧。本讲稿第九页，共二十一页 对最大流问题有下列定理：定理定理7.9.1 7.9.1 容量网络中任一可行流的流量不超过其任一割容量网络中任一可行流的流量不超过其任一割集的容量。集的容量。定理定理7.9.27.9.2（最大流（最大流-最小最小割定理割定理）任一容量网络中，最大）任一容量网络中，最大流的流量等于最小割集的流的流量等于最小割集的割割量。量。推论推论1 可行流可行流f*fij*是最大流，当且仅当是最大流，当且仅当G中不存在关于中不存在关于f*的增广链。的增广链。本讲稿第十页，共二十一页求最大流的标号法求最大流的标号法(Ford,Fulkerson)标号法思想是：先找一个可行流。对于一个可行流，经过标号过程得到从源点s到汇点t的增广链；经过调整过程沿增广链增加可行流的流量，得新的可行流。重复这一过程，直到可行流无增广链，得到最大流。本讲稿第十一页，共二十一页 标号过程:(1)给s标号(-,+)，s成为已标号未检查的点，其余都是未标号点。(2)取一个已标号未检查的点vi，对一切未标号点vj：若有非饱和弧(vi,vj)，则vj标号(vi,l(vj)，其中l(vj)minl(vi),cij fij，vj成为已标号未检查的点；若有非零弧(vj,vi)，则vj标号(-vi,l(vj)，其中l(vj)minl(vi),fji，vj成为已标号未检查的点。vi成为已标号已检查的点。(3)重复步骤(2)，直到t成为标号点或所有标号点都检查过。若t成为标号点，表明得到一条s到t的增广链，转入调整过程；若所有标号点都检查过，表明这时的可行流就是最大流，算法结束。调整过程：在增广链上，前向弧流量增加l(vt)，后向弧流量减少l(vt)。本讲稿第十二页，共二十一页下面用实例说明具体的操作方法：例(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)sv2v1v3v4t(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)sv2v1v3v4t在图中给出的可行流的基在图中给出的可行流的基础上，求础上，求s到到t的最大流。的最大流。(-,+)(s,4)(-v1,1)(-v2,1)(v2,1)(v3,1)(3,3)(5,2)(1,0)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)sv2v1v3v4t(vs,3)(-,+)得增广链，标号结束，进入调整过程 无增广链，标号结束，得最大流。同时得最小割。本讲稿第十三页，共二十一页下图中已经标示出了一个可行流，求最大流-,s,3s,4v2,4-v4,2sv1v2v3v4v5t(4,0)(5,2)(1,0)(4,0)(1,0)(2,2)(3,2)(4,0)(2,0)(5,2)v4,3如图已经得到增广链，然后进行调整。本讲稿第十四页，共二十一页调整后的可行流如下图：vsv1v2v3v4v5t(4,3)(5,2)(1,0)(4,3)(1,0)(2,2)(3,2)(4,0)(2,0)(5,5)-,vs,3vs,1v2,1-v4,1v3,1v5,1如图已经得到增广链，然后进行调整。本讲稿第十五页，共二十一页调整后的可行流如下图：vsv1v2v3v4v5t(4,4)(5,2)(1,0)(4,4)(1,0)(2,2)(3,1)(4,1)(2,1)(5,5)-,vs,3如图所示最小割集的容量（即当前可行流的流量），就是最大流的流量。注：用该方法可以同时得到最小割集，即图中连结已标号的点与未标号的点的边集。本讲稿第十六页，共二十一页具有实际背景的例子国庆大假期间旅游非常火爆，机票早已订购一空。成都一家旅行社由于信誉好、服务好，所策划的国庆首都游的行情看好，要求参加的游客众多，游客甚至不惜多花机票钱辗转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快，各办事处将其已订购机票的情况传到了总社。根据此资料，总社要作出计划，最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表：本讲稿第十七页，共二十一页成都成都重庆重庆武汉武汉上海上海西安西安郑州郑州沈阳沈阳昆明昆明广州广州北京北京成都成都105158121030重庆重庆561525武汉武汉10上海上海158西安西安86郑州郑州148沈阳沈阳18昆明昆明810广州广州82610本讲稿第十八页，共二十一页用图来描述就是成成重重武武昆昆上上广广西西郑郑沈沈京京85101581210305615251015886141881082610源点s=成都，汇点t=北京。前面已订购机票情况表中的数字即是各边上的容量（允许通过的最大旅客量），当各边上的实际客流量为零时略去不写，以零流作为初始可行流。本讲稿第十九页，共二十一页利用标号法（经5次迭代）可以得到从成都发送旅客到北京的最大流量如图所示重重武武昆昆上上广广西西郑郑沈沈京京成成301006122801251061010600010801810100W(f*)=10+6+12+30+12+10+5=85本讲稿第二十页，共二十一页7.9 作业 2本讲稿第二十一页，共二十一页
