资源描述
最大流问题,给定一个有向图G(V,E),其中仅有一个点的入次为零称为发点(源),记为vs,仅有一个点的出次为零称为收点(汇),记为vt,其余点称为中间点。,基本概念,3,5,1,1,4,2,3,5,2,vs,v2,v1,v3,v4,vt,对于G中的每一个弧(vi,vj),相应地给一个数cij(cij0),称为弧(vi,vj)的容量。我们把这样的D称为网络(或容量网络),记为G(V,E,C)。,所谓网络上的流,是指定义在弧集E上的函数ff(vi,vj),并称f(vi,vj)为弧(vi,vj)上的流量,简记为fij。,3,1,5,2,1,0,1,0,4,1,2,2,3,1,5,2,2,1,vs,v2,v1,v3,v4,vt,标示方式:每条边上标示两个数字,第一个是容量,第二是流量,可行流、可行流的流量、最大流。,可行流是指满足如下条件的流:,(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,使 vsV1 ,vtV2,则把弧集(V1,V2)称为(分离vs和vt的)割集。,显然,若把某一割集的弧从网络中去掉,则从vs到vt便不存在路。所以,直观上说,割集是从vs到vt的必经之路。,3,5,1,1,4,2,3,5,2,vs,v2,v1,v3,v4,vt,注:有向边也称为弧。,对教材P259定义21的解释,vs,v1,v4,v3,vt,v2,边集(vs,v1),(v1,v3),(v2,v3),(v3,vt),(v4,vt)是G的割集。其顶点分别属于两个互补不相交的点集。去掉这五条边,则图不连通,去掉这五条边中的任意1-4条,图仍然连通。,割集的容量(简称割量) 最小割集,割集(V1, V2)中所有起点在V1,终点在V2的边的容量的和称为割集容量。例如下图中所示割集的容量为5,3,5,1,1,4,2,3,5,2,vs,v2,v1,v3,v4,vt,在容量网络的所有割集中,割集容量最小的割集称为最小割集(最小割)。,对于可行流ffij,我们把网络中使fijcij的弧称为饱和弧,使fij0的弧称为非零流弧。,设f是一个可行流,是从vs到vt的一条链,若满足前向弧都是非饱和弧,后向弧都是都是非零流弧,则称是(可行流f的)一条增广链。,3,1,5,2,1,0,1,0,4,1,2,2,3,1,5,2,2,1,vs,v2,v1,v3,v4,vt,若是联结发点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)minl(vi),cij fij,vj成为已标号未检查的点;若有非零弧(vj,vi),则vj标号(-vi,l(vj),其中l(vj)minl(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),vs,v2,v1,v3,v4,vt,(3,3),(5,1),(1,1),(1,1),(4,3),(2,2),(3,0),(5,3),(2,1),vs,v2,v1,v3,v4,vt,在图中给出的可行流的基础上,求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),vs,v2,v1,v3,v4,vt,(vs,3),(-,+),得增广链,标号结束,进入调整过程,无增广链,标号结束,得最大流。同时得最小截。,下图中已经标示出了一个可行流,求最大流,-, ,vs, 3,vs, 4,v2, 4,-v4, 2,v4, 3,如图已经得到增广链,然后进行调整。,调整后的可行流如下图:,-, ,vs, 3,vs, 1,v2, 1,-v4, 1,v3, 1,v5, 1,如图已经得到增广链,然后进行调整。,调整后的可行流如下图:,-, ,vs, 3,如图所示最小割集的容量(即当前可行流的流量),就是最大流的流量。注:用该方法可以同时得到最小割集,即图中连结已标号的点与未标号的点的边集。,具有实际背景的例子,国庆大假期间旅游非常火爆,机票早已订购一空。成都一家旅行社由于信誉好、服务好,所策划的国庆首都游的行情看好,要求参加的游客众多,游客甚至不惜多花机票钱辗转取道它地也愿参加此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此问题。很快,各办事处将其已订购机票的情况传到了总社。根据此资料,总社要作出计划,最多能将多少游客从成都送往北京以及如何取道转机。下面是各办事处已订购机票的详细情况表:,用图来描述就是,发点vs =成都,收点vt =北京。前面已订购机票情况表中的数字即是各边上的容量(允许通过的最大旅客量),当各边上的实际客流量为零时略去不写,以零流作为初始可行流。,利用标号法(经5次迭代)可以得到从成都发送旅客到北京的最大流量如图所示,重,武,昆,上,广,西,郑,沈,京,成,30,10,0,6,12,2,8,0,12,5,10,6,10,10,6,0,0,0,10,8,0,18,10,10,0,W ( f* ) =10+6+12+30+12+10+5 = 85,多个发点多个收点的情形,对于多发点多收点的容量网络的最大流问题可以通过添加两个新点vs与vt扩充为新的单发点与单收点的容量网络的方式解决。,x1 x2 . xm,y1 y2 . yn,vs,vt,+,+,其中vs到各已知点,以及各已知点到vt的弧的容量取为+。,最大匹配问题,考虑工作分配问题。有n个工人,m件工作,每个工人能力不同,各能胜任其中某几项工作。假设每件工作只需一人做,每人只做一件工作。怎样分配才能使尽量多的工作有人做,更多的人有工作做?,该问题用图论的语言可以描述为:在图中,x1, x2, , xn表示工人,y1, y2, , ym表示工作,有向边(xi, yj)表示工人xi胜任工作yj,因此得到一个二部图。,如果记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为最大匹配。,下面的二部图表示了一个匹配问题,它有如下两个最大匹配:,最大匹配问题可以化为最大流问题求解。化的方式类似于多发点多收点问题,具体做法是:,在原二部图中添加两个点vs和vt,其中vs有以它为起点,以X中各点为终点的有向边;连结vt有以它为终点,Y中各点为起点的有向边。并且在这样的图中各边上的容量取为1。若一条边上的流量为1,则表示一个相应的分配。如下图,这样最大匹配问题就化为对上图的网络的最大流问题。,例,有5位求职者和5项工作岗位,这5位求职者各自能胜任的工作如图所示,问如何安排才能实现最大就业?,首先将原图扩充成一个容量网络,其中每边的容量均为1。然后用标号法来求最大流。,-,+,vs,1,vs,1,vs,1,vs,1,vs,1,x1,1,x1,1,x1,1,y1,1,1,1,1,-,+,vs,1,vs,1,vs,1,x2,1,x2,1,y4,1,vs,1,1,1,1,1,1,1,-,+,vs,1,vs,1,vs,1,x3,1,x3,1,y5,1,1,1,1,1,1,1,1,1,1,-,+,vs,1,vs,1,x5,1,x4,1,-y4, 1,x2,1,-y1, 1,x1,1,x1,1,y2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,最大匹配为(省略了最后一步的标号过程):,
展开阅读全文