大学精品课件：第八章（续）-最大流问题.ppt

1、最大流问题 给给定一个有向图定一个有向图G G(V,E)(V,E)，其中仅有一个点的入次其中仅有一个点的入次为零为零称为称为发点发点（源）（源），记为记为v vs s，仅有仅有一个点一个点的出次为的出次为零称为零称为收点（汇）收点（汇），记为，记为v vt t，其余点称为中间点。其余点称为中间点。基本概念基本概念3511 42352vsv2v1v3v4vt 对于对于G G中的每一个弧中的每一个弧(v vi i,v,vj j)，相应相应地给地给一个数一个数c cijij（c cijij00），），称为弧称为弧(v vi i,v,vj j)的的容量容量。我们把这样的。我们把这样的D D称称为为网络

2、（或容量网络）网络（或容量网络），记为，记为G G(V,E,C)(V,E,C)。所谓网络上的所谓网络上的流流，是指定义在弧集，是指定义在弧集E E上的函数上的函数f ff(vf(vi i,v,vj j)，并称并称f(vf(vi i,v,vj j)为为弧弧(v vi i,v,vj j)上的上的流量流量，简记为，简记为f fijij。3,15,21,01,0 4,12,23,15,22,1vsv2v1v3v4vt标示方式：每条边上标示两个数字，第一个是容量，第二标示方式：每条边上标示两个数字，第一个是容量，第二是流量是流量可行流、可行流的流量、最大流。可行流是指满足如下条件的流：（1）容量限制条件

3、：对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 G(V,A,E)(V,A,E)，若

4、点集若点集V V被被剖剖分分为两个非空集合为两个非空集合V V1 1和和V V2 2，使使 v vs sVV1 1，v vt tVV2 2，则把则把弧集弧集(V V1 1,V,V2 2)称为（分离称为（分离v vs s和和v vt t的）的）割割集集。显然，若把某一显然，若把某一割割集的弧从网络中去掉，集的弧从网络中去掉，则从则从v vs s到到v vt t便不存在路。所以，直观上说，便不存在路。所以，直观上说，割割集是从集是从v vs s到到v vt t的必经之路。的必经之路。3511 42352vsv2v1v3v4vt注：有向边也称为弧。注：有向边也称为弧。对教材P259定义21的解释vs

5、v1v4v3vtv2边集（vs,v1），（v1,v3），（v2,v3），（v3,vt），（v4,vt）是G的割集。其顶点分别属于两个互补不相交的点集。去掉这五条边，则图不连通，去掉这五条边中的任意1-4条，图仍然连通。割集的容量(简称割量)最小割集割集(V1,V2)中所有起点在V1，终点在V2的边的容量的和称为割集容量。例如下图中所示割集的容量为53511 42352vsv2v1v3v4vt在容量网络的所有割集中，割集容量最小的割集称为最小割集（最小割）。对于可行流ffij，我们把网络中使fijcij的弧称为饱和弧，使fij0的弧称为非零流弧。设f是一个可行流，是从vs到vt的一条链，若满足前

6、向弧都是非饱和弧,后向弧都是都是非零流弧,则称是（可行流f的）一条增广链。3,15,21,01,0 4,12,23,15,22,1vsv2v1v3v4vt 若是联结发点vs和收点vt的一条链，我们规定链的方向是从vs到vt，则链上的弧被分成两类：前向弧、后向弧。对最大流问题有下列定理：定理定理1 1 容量网络中任一可行流的流量容量网络中任一可行流的流量不超过其任一割集的容量。不超过其任一割集的容量。定理定理2 2（最大流（最大流-最小最小割定理割定理）任一任一容容量网络中量网络中，最大流的流量等于最小，最大流的流量等于最小割割集集的的割割量。量。推论推论1 可行流可行流f*fij*是最大流，是

7、最大流，当且当且仅当仅当G中不存在关于中不存在关于f*的增广链。的增广链。求最大流的标号法求最大流的标号法 标号法思想是：标号法思想是：先找一个可行流。先找一个可行流。对于一个可行流，经过对于一个可行流，经过标号过程标号过程得到得到从发点从发点vs到收点到收点vt的增广链；经过的增广链；经过调整调整过程过程沿增广链增加可行流的流量，得沿增广链增加可行流的流量，得新的可行流。重复这一过程，直到可新的可行流。重复这一过程，直到可行流无增广链，得到最大流。行流无增广链，得到最大流。标号过程:(1)给vs标号(-,+)，vs成为已标号未检查的点，其余都是未标号点。(2)取一个已标号未检查的点vi，对一

8、切未标号点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)

9、(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)(-,+)得增广链，标号结束，得增广链，标号结束，进入调整过程进入调整过程 无增广链，标号

10、结束，得无增广链，标号结束，得最大流。同时得最小截。最大流。同时得最小截。下图中已经标示出了一个可行流，求最大流-,vs,3vs,4v2,4-v4,2vsv1v2v3v4v5vs(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,3vs,1v2,1-v4,1v3,1v5,1如图已经得到增广链，然后进行调整。调整后的可行流如下图：vsv1v2v3v4

11、v5vs(4,4)(5,2)(1,0)(4,4)(1,0)(2,2)(3,1)(4,1)(2,1)(5,5)-,vs,3如图所示最小割集的容量（即当前可行流的流量），就是最大流的流量。注：用该方法可以同时得到最小割集，即图中连结已标号的点与未标号的点的边集。多个发点多个收点的情形对于多发点多收点的容量网络的最大流问题可以通过添加两个新点vs与vt扩充为新的单发点与单收点的容量网络的方式解决。x1x2.xmy1y2.ynvsvt+其中vs到各已知点，以及各已知点到vt的弧的容量取为+。最大匹配问题考虑工作分配问题。有n个工人，m件工作，每个工人能力不同，各能胜任其中某几项工作。假设每件工作只需一

12、人做，每人只做一件工作。怎样分配才能使尽量多的工作有人做，更多的人有工作做？该问题用图论的语言可以描述为：在图中，x1,x2,xn表示工人，y1,y2,ym表示工作，有向边(xi,yj)表示工人xi胜任工作yj，因此得到一个二部图。x1x2x3xny1y2y3ym如果记X=x1,x2,xn，Y=y1,y2,ym，则该二部图可记为G=(X,Y,E)，而上述的工作匹配问题就是：在图G中找一个边集E的子集，使得这个子集中任意两条边没有公共端点，最好的方案就是要使得该子集中的边数达到最大。定义：对于二部图G=(X,Y,E)，M是边集E的一个子集，如果M中的任意两条边没有公共端点，则称M是图G的一个匹配

13、（也称对集）。M中任意一条边的端点v称为（关于M的）饱和点，G中的其他顶点称为非饱和点。若不存在另一匹配M1使得|M1|M|，则称M为最大匹配。下面的二部图表示了一个匹配问题x1x2x3x4y1y2y3y4y5x1x2x3x4y1y2y3y4y5x1x2x3x4y1y2y3y4y5它有如下两个最大匹配：最大匹配问题可以化为最大流问题求解。化的方式类似于多发点多收点问题，具体做法是：在原二部图中添加两个点vs和vt，其中vs有以它为起点，以X中各点为终点的有向边；连结vt有以它为终点，Y中各点为起点的有向边。并且在这样的图中各边上的容量取为1。若一条边上的流量为1，则表示一个相应的分配。如下图x

14、1x2x3xny1y2y3ymvsvt这样最大匹配问题就化为对上图的网络的最大流问题。例x1y1有5位求职者和5项工作岗位，这5位求职者各自能胜任的工作如图所示，问如何安排才能实现最大就业?x2x3x4y2y3y4y5x5vsvs首先将原图扩充成一个容量网络，其中每边的容量均为1。然后用标号法来求最大流。x1y1x2x3x4y2y3y4y5x5vsvs-,+vs,1vs,1vs,1vs,1vs,1x1,1x1,1x1,1y1,1x1y1x2x3x4y2y3y4y5x5vsvs111-,+vs,1vs,1vs,1x2,1x2,1y4,1vs,1x1y1x2x3x4y2y3y4y5x5vsvs111111-,+vs,1vs,1vs,1x3,1x3,1y5,1x1y1x2x3x4y2y3y4y5x5vsvs111111111-,+vs,1vs,1x5,1x4,1-y4,1x2,1-y1,1x1,1x1,1y2,1x1y1x2x3x4y2y3y4y5x5vsvs11111111111111最大匹配为(省略了最后一步的标号过程):x1y1x2x3x4y2y3y4y5x5