最大流 标号法

最大流问题给定一个有向图G＝(V,E)，其中仅有一个点的入次为零称为发点（源），记为vs，仅有一个点的出次为零称为收点（汇），记为vt，其余点称为中间点。基本概念351142352vsv2v1v3v4vt对于G中的每一个弧(vi,vj)，相应地给一个数cij（cij≥0），称为弧(vi,vj)的容量。我们把这样的D称为网络（或容量网络），记为G＝(V,E,C)。所谓网络上的流，是指定义在弧集E上的函数f＝{f(vi,vj)}，并称f(vi,vj)为弧(vi,vj)上的流量，简记为fij。3,15,21,01,04,12,23,15,22,1vsv2v1v3v4vt标示方式：每条边上标示两个数字，第一个是容量，第二是流量可行流、可行流的流量、最大流。可行流是指满足如下条件的流：（1）容量限制条件：对G中每条边(vi,vj),有ijijcf0（2）平衡条件：对中间点，有：kkijijff（即中间点vi的物资输入量等于输出量）对收点vt与发点vs，有：Wffjjtisi（即vs发出的物资总量等于vt接收的物资总量），W是网络的总流量。可行流总是存在的，例如f={0}就是一个流量为0的可行流。所谓最大流问题就是在容量网络中寻找流量最大的可行流。一个流f={fij}，当fij=cij，则称f对边(vi,vj)是饱和的，否则称f对边(vi,vj)不饱和。最大流问题实际上是一个线性规划问题。但利用它与图的密切关系，可以利用图直观简便地求解。给定容量网络G＝(V,A,E)，若点集V被剖分为两个非空集合V1和V2，使vs∈V1，vt∈V2，则把弧集(V1,V2)称为（分离vs和vt的）割集。显然，若把某一割集的弧从网络中去掉，则从vs到vt便不存在路。所以，直观上说，割集是从vs到vt的必经之路。351142352vsv2v1v3v4vt注：有向边也称为弧。对教材P259定义21的解释vsv1v4v3vtv2边集（vs,v1），（v1,v3），（v2,v3），（v3,vt），（v4,vt）是G的割集。其顶点分别属于两个互补不相交的点集。去掉这五条边，则图不连通，去掉这五条边中的任意1-4条，图仍然连通。割集的容量(简称割量)最小割集割集(V1,V2)中所有起点在V1，终点在V2的边的容量的和称为割集容量。例如下图中所示割集的容量为5351142352vsv2v1v3v4vt在容量网络的所有割集中，割集容量最小的割集称为最小割集（最小割）。对于可行流f＝{fij}，我们把网络中使fij＝cij的弧称为饱和弧，使fijcij的弧称为非饱和弧；把使fij＝0的弧称为零流弧，使fij0的弧称为非零流弧。设f是一个可行流，μ是从vs到vt的一条链，若μ满足前向弧都是非饱和弧,后向弧都是都是非零流弧,则称μ是（可行流f的）一条增广链。3,15,21,01,04,12,23,15,22,1vsv2v1v3v4vt若μ是联结发点vs和收点vt的一条链，我们规定链的方向是从vs到vt，则链上的弧被分成两类：前向弧、后向弧。对最大流问题有下列定理：定理1容量网络中任一可行流的流量不超过其任一割集的容量。定理2（最大流-最小割定理）任一容量网络中，最大流的流量等于最小割集的割量。推论1可行流f*＝{fij*}是最大流，当且仅当G中不存在关于f*的增广链。求最大流的标号法标号法思想是：先找一个可行流。对于一个可行流，经过标号过程得到从发点vs到收点vt的增广链；经过调整过程沿增广链增加可行流的流量，得新的可行流。重复这一过程，直到可行流无增广链，得到最大流。标号过程:(1)给vs标号(-,+∞)，vs成为已标号未检查的点，其余都是未标号点。(2)取一个已标号未检查的点vi，对一切未标号点vj：若有非饱和弧(vi,vj)，则vj标号(vi,l(vj))，其中l(vj)＝min[l(vi),cij–fij]，vj成为已标号未检查的点；若有非零弧(vj,vi)，则vj标号(-vi,l(vj))，其中l(vj)＝min[l(vi),fji]，vj成为已标号未检查的点。vi成为已标号已检查的点。(3)重复步骤(2)，直到vt成为标号点或所有标号点都检查过。若vt成为标号点，表明得到一条vs到vt的增广链，转入调整过程；若所有标号点都检查过，表明这时的可行流就是最大流，算法结束。调整过程：在增广链上，前向弧流量增加l(vt)，后向弧流量减少l(vt)。下面用实例说明具体的操作方法：例(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt在图中给出的可行流的基础上，求vs到vt的最大流。(-,+∞)(vs,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)vsv2v1v3v4vt(vs,3)(-,+∞)得增广链，标号结束，进入调整过程无增广链，标号结束，得最大流。同时得最小截。下图中已经标示出了一个可行流，求最大流[-,∞][vs,3][vs,4][v2,4][-v4,2]vsv1v2v3v4v5vs(4,0)(5,2)(1,0)(4,0)(1,0)(2,2)(3,2)(4,0)(2,0)(5,2)[v4,3]如图已经得到增广链，然后进行调整。调整后的可行流如下图：vsv1v2v3v4v5vs(4,3)(5,2)(1,0)(4,3)(1,0)(2,2)(3,2)(4,0)(2,0)(5,5)[-,∞][vs,3][vs,1][v2,1][-v4,1][v3,1][v5,1]如图已经得到增广链，然后进行调整。调整后的可行流如下图：vsv1v2v3v4v5vs(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发点vs=成都，收点vt=北京。前面已订购机票情况表中的数字即是各边上的容量（允许通过的最大旅客量），当各边上的实际客流量为零时略去不写，以零流作为初始可行流。利用标号法（经5次迭代）可以得到从成都发送旅客到北京的最大流量如图所示重武昆上广西郑沈京成301006122801251061010600010801810100W(f*)=10+6+12+30+12+10+5=85多个发点多个收点的情形对于多发点多收点的容量网络的最大流问题可以通过添加两个新点vs与vt扩充为新的单发点与单收点的容量网络的方式解决。x1x2...xmy1y2...ynvsvt+∞+∞其中vs到各已知点，以及各已知点到vt的弧的容量取为+∞。最大匹配问题考虑工作分配问题。有n个工人，m件工作，每个工人能力不同，各能胜任其中某几项工作。假设每件工作只需一人做，每人只做一件工作。怎样分配才能使尽量多的工作有人做，更多的人有工作做？该问题用图论的语言可以描述为：在图中，x1,x2,…,xn表示工人，y1,y2,…,ym表示工作，有向边(xi,yj)表示工人xi胜任工作yj，因此得到一个二部图。…x1x2x3xn…y1y2y3ym如果记X={x1,x2,…,xn}，Y={y1,y2,…,ym}，则该二部图可记为G=(X,Y,E)，而上述的工作匹配问题就是：在图G中找一个边集E的子集，使得这个子集中任意两条边没有公共端点，最好的方案就是要使得该子集中的边数达到最大。定义：对于二部图G=(X,Y,E)，M是边集E的一个子集，如果M中的任意两条边没有公共端点，则称M是图G的一个匹配（也称对集）。M中任意一条边的端点v称为（关于M的）饱和点，G中的其他顶点称为非饱和点。若不存在另一匹配M1使得|M1||M|，则称M为最大匹配。下面的二部图表示了一个匹配问题x1x2x3x4y1y2y3y4y5x1x2x3x4y1y2y3y4y5x1x2x3x4y1y2y3y4y5它有如下两个最大匹配：最大匹配问题可以化为最大流问题求解。化的方式类似于多发点多收点问题，具体做法是：在原二部图中添加两个点vs和vt，其中vs有以它为起点，以X中各点为终点的有向边；连结vt有以它为终点，Y中各点为起点的有向边。并且在这样的图中各边上的容量取为1。若一条边上的流量为1，则表示一个相应的分配。如下图…x1x2x3xn…y1y2y3ymvsvt这样最大匹配问题就化为对上图的网络的最大流问题。例x1y1有5位求职者和5项工作岗位，这5位求职者各自能胜任的工作如图所示，问如何安排才能实现最大就业?x2x3x4y2y3y4y5x5vsvs首先将原图扩充成一个容量网络，其中每边的容量均为1。然后用标号法来求最大流。x1y1x2x3x4y2y3y4y5x5vsvs[-,+∞][vs,1][vs,1][vs,1][vs,1][vs,1][x1,1][x1,1][x1,1][y1,1]x1y1x2x3x4y2y3y4y5x5vsvs111[-,+∞][vs,1][vs,1][vs,1][x2,1][x2,1][y4,1][vs,1]x1y1x2x3x4y2y3y4y5x5vsvs111111[-,+∞][vs,1][vs,1][vs,1][x3,1][x3,1][y5,1]x1y1x2x3x4y2y3y4y5x5vsvs111111111[-,+∞][vs,1][vs,1][x5,1][x4,1][-y4,1][x2,1][-y1,1][x1,1][x1,1][y2,1]x1y1x2x3x4y2y3y4y5x5vsvs11111111111111最大匹配为(省略了最后一步的标号过程):x1y1x2x3x4y2y3y4y5x5