最大流 标号法.ppt

最大流问题; 给定一个有向图G＝(V,E)，其中仅有一个点的入次为零称为发点（源），记为vs，仅有一个点的出次为零称为收点（汇），记为vt，其余点称为中间点。; 所谓网络上的流，是指定义在弧集E上的函数f＝{f(vi,vj)}，并称f(vi,vj)为弧(vi,vj)上的流量，简记为fij。;可行流、可行流的流量、最大流。;可行流总是存在的，例如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的）割集。;对教材P259定义21的解释; 割集的容量(简称割量) 最小割集; 对于可行流f＝{fij}，我们把网络中使fij＝cij的弧称为饱和弧，使fijcij的弧称为非饱和弧；把使fij＝0的弧称为零流弧，使fij0的弧称为非零流弧。; 对最大流问题有下列定理： 定理1 容量网络中任一可行流的流量不超过其任一割集的容量。 定理2（最大流-最小割定理）任一容量网络中，最大流的流量等于最小割集的割量。 推论1 可行流f*＝{fij*}是最大流，当且仅当G中不存在关于f*的增广链。 ;求最大流的标号法; 标号过程: (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)。 ;下面用实例说明具体的操作方法：例;下图中已经标示出了一个可行流，求最大流;调整后的可行流如下图：;调整后的可行流如下图：;具有实际背景的例子;;用图来描述就是;利用标号法（经5次迭代）可以得到从成都发送旅客到北京的最大流量如图所示;多个发点多个收点的情形;最大匹配问题;如果记X={x1, x2, …, xn}，Y={y1, y2, …, ym}，则该二部图可记为G=(X, Y, E)，而上述的工作匹配问题就是：在图G中找一个边集E的子集，使得这个子集中任意两条边没有公共端点，最好的方案就是要使得该子集中的边数达到最大。;下面的二部图表示了一个匹配问题;最大匹配问题可以化为最大流问题求解。化的方式类似于多发点多收点问题，具体做法是：;例;x1;x1;x1