网络最大流问题

-给定一个有向图D=(V,A)，在V中指定一点称为发点记为，该点只有出发去的弧，指定另一点称为收点记为，该点只有指向它的弧，其余的点叫做中间点。对于A中的每一条弧，对应一个数简记，称之为弧的容量。通常我们把这样的D叫做网络，记为D=(V,A,C)。2网络流：在弧集A上定义一个非负函数。是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。4 网络最大流问题网络最大流问题是网络的另一个根本问题。许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何到达这个最大流量。4.1 根本概念与定理1 1网络与流定义14 1网络：例1如图7-20是连结*产品产地和销地的交通图。弧表示从到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。现要求制定一个运输方案，使从运到的产品数量最多。可行流与最大流在运输网络的实际问题中，我们可以看出，对于流有两个根本要求：一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力即该弧的容量；二是起点发出的流的总和称为流量，必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。因此有下面所谓的可行流的定义。定义14对于给定的网络D=V,A,C和给定的流，假设满足以下条件：（1） 容量限制条件：对每一条弧，有 (7.9)2平衡条件：对于中间点：流出量=流入量，即对于每一个i (is,t)，有 (7.10)对于出发带点，有 (7.11)对于收点，有 (7.12)则称为一个可行流，称为这个可行流的流量。注意，我们这里所说的出发点是指只有从发出去的弧，而没有指向的弧；收点是指只有弧指向，而没有从它的发出去的弧。可行流总是存在的。例如令所有弧上的流，就得到一个可行流，称为零流，其流量。如图7-20中，每条弧上括号内的数字给出的就是一个可行流，它显然满足定义中的条件1和2。其流量。所谓网络最大流问题就是求一个流，使得总流量到达最大，并且满足定义15中的条件1和2，即ma* (7.13)网络最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个问题的方法较直线性规划的一般方法要简便和直观的多。例2写出图7-20所表示的网络最大流问题的线性规划模型。解设，则其线性规划模型为 ma* 3. 增广链在网络D=(V,A,C)中，假设给定一个可行流，我们把网络中使的弧称为饱和弧，使的弧称为非饱和弧。把的弧称为零流弧，把的称为非零流弧。如图7-20中的弧都是非饱和弧，而弧为零流弧。假设是网络中联结发点和收点的一条链，我定义链的方向是从到S，则链上的弧被分为两：一类是：弧的方向与链的方向一致，我们称此类和为前向弧，所有前向弧的集合记为。另一类是：弧的方向与链的方向一致，我们称此类弧为后向弧，所有后向弧的集合记为。如图7-20中，设是一条从到的链，则, 定义15设是网络D=(V,A,C)上的一个可行流，是从到的一条链，假设满足以下条件：(1)在弧(vi,vj)+上，即中的每一条弧都是非饱和弧；(2)在弧上，即中的每一条弧都是非零流弧。则称是关于的一条增广链。如前面所说的链就是一条增广链。因为其中+上的弧均非饱和，如(vs,v2)+,fs2=50，。显然这样的增广链不止一条。4.截集与截量定义16给定网络D=(V,A,C)，假设点集V被分割成两个非空集合V1和V2，使得V=V1+V2,V1V2=(空集)，且vsV1,vtV2，则把始点在V1,终点在V2的弧的集合称为别离vs和vt的一个截集，记为(V1,V2)。如图中，设V1=vs,v2,v5，V2=v3,v4,v6,vt则截集为,而弧(v3,v2)和(v4,v5)不是该集中的弧。因为这两条弧的起点在V2中，与定义17不符。显然，一个网络的截集是很多的但只有有限个，例如在图7-20中，还可以取,，则截集为另外，假设把网络D=(V,A,C)中*截集的弧从网络D中去掉，则从vs到vt便不存在路，所以直观上说，截集是从vs到vt的必经之路。定义17在网络D=(V,A,C)中，给定一个截集(V1,V2)，则把该截集中所有弧的容量之和，称为这个截集的容量，简称为截量，记为c(V1,V2)，即 C(V1,V2)= (7.16)例如在上面我们所举的两个截集中，有而显然，截集不同，其截量也不同。由于截集的个数是有限的，故其中必有一个截集的容量是最小的，称为最小截集，也就是通常所说的瓶颈。不难证明，网络D=(V,A,C)中，任何一个可行流f=fij的流量V(f)，都不会超过任一截集的容量，即 v( f ) c(V1,V2) (7.17)如果存在一个可行流f*=f*ij，网络D=(V,A,C)中有一个截集，使得 (7.18)则必是最大流，而必是D中的最小截集。为了求网络最大流f*，我们也说明下面的重要定理。定理4在网络D=(V,A,C)中，可行流是最大流的充要条件是D中不存在关于f*的增广链。证先证必要性。用反证法。假设f*是最大流，假设D中存在着关于f*的增广链，令 (7.19)由增广链的定义可知0，令 (7.20)不难验证是一个可行流，且有这与f*是最大流的假定矛盾。再证充分性：即证明设D中不存在关于f*的增广链，f*是最大流。用下面的方法定义：令假设，且有，则令；假设，且有，则令。因为不存在着关于的增广链，故记，于是得到一个截集(V*,)。显然有所以V(f*)=c，于是f*必是最大流。定理得证。由上述证明中可见，假设是最大流，则网络必定存在一个截集，使得(7.18)式成立。定理5最大流最小截集定理对于任意给定的网络D=(V,A,C)，从出发点vs到收点vt的最大流的流量必等于分割和的最小截集的容量，即由定理4可知，假设给定一个可行流，只要判断网络D有无关于的增广链。如果有增广链，则可以按定理4前半局部证明中的方法，由公式(7.19)求出调整量Q，再按式的方法求出新的可行流。如果流有增广链，则得到最大流。而根据定理4后半局部证明中定义的方法，可以根据vt是否属于来判断D中有无关于f的增广链。在实际计算时，我们是用给顶点标号的方法来定义的，在标号过程中，有标号的顶点表示是中的点，没有标号的点表示不是中的点。一旦有了标号，就说明找到一条从vs到vt的增广链；如果标号过程无法进展下去，而vt尚未标号，则说明不存在从vs到vt的增广链，于是得到最大流。这时将已标号的点至少有一个点vs放在集合中，将未标号点至少有一个点vt放在集合中，就得到一个最小截集。4.2 寻求最大流的标号法Ford , Fulkerson从一个可行流出发假设网络中没有给定，则可以设是零流，经过标号过程与调整过程。1） 1标号过程在这个过程中，网络中的点或者是标号点又分为已检查和未检查两种，或者是未标号点，每个标号点的标号包含两局部：第一个标号说明它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。标号过程开场，总先给vs标上(0,+)，这时vs是标号而未检查的点，其余都是未标号点，一般地，取一个标号而未检查的点vi，对一切未标号点vj：(1) 在弧上，则给vj标号。这里。这时点vj成为标号而未检查的点。(2) 假设在弧上，给vj标号。这里。这时点vj成为标号而未检查的点。于是成为标号而已检查过的点，重复上述步骤，一旦被标上号，说明得到一条从到的增广链，转入调整过程。假设所有标号都是已检查过，而标号过程进展不下去时，则算法完毕，这时的可行流就是最大流。2） 2调整过程首先按及其它点的第一个标号，利用反向追踪的方法，找出增广链。例如设vt的第一个标号为或，则弧或相应地是上的弧。接下来检查的第一个标号，假设为或，则找出或相应地。再检查的第一个标号，依此下去，直到为止。这时被找出的弧就构成了增广链。令调整量是，即的第二个标号。令去掉所有的标号，对新的可行流，重新进入标号过程。下面，以例题说明此算法求解过程。例3 用标号法求图7-20所示网络最大流。弧旁的数是解 :对图7-20中各顶点进展标号。首先给标(0,+)，即检查：在弧上，因为，又有,所以给标；在弧上，因为，又有,所以给标。检查：在弧上，因为，又有,所以给标；在弧上，因为，又有,所以给标；在弧上，因为，又有,所以给V3标。因为前面已给v3标过号，这里又给标，它们分别表示两条不同的路线，这里不存在修改标号的问题与最短路不同。因为我们的目标是尽快找出一条从vs到vt的增广链，即尽快使终点vt获得标号，所以不必在中途过多停留。也就是说在对已标号点vi进展检查时，每次只检查一个相邻点vj不管前向弧或后向弧均可，再给标号即可，而不必检查所有与vi相邻的点。事实上，其余的相邻点也不会漏掉，因为以后还要通过检查这些点来找出新的增广链。以下我们就按这种思路进展。检查：在弧上，因为，又有.所以给标.至此，终点已获得标号，于是找出一条从到的增广链。再由标号的第一局部用反向追踪法找出路线，即见图7-21。进展调查：这时的调整量.再按公式调整。由于上各弧均为前向弧，故得，.见图7-21.其余的不变.对这个新的可行流再进入标号过程，寻找新增广链。开场给标，检查，给标，检查：在弧上，因为见图7-21，故该弧已饱和，标号无法进展下去。在弧上，因为，又有所以给标，检查：在弧上，因为，又有所以给标，检查：在弧上，因为，又有，所以给标.于是又得到一条增广链(见图7-22)进展调整：这时。调整结果如图所示。再重新标号求新的增广链.开场给标，检查，给标。检查，给标，检查，给标，检查，因已是饱和弧见图7-22。标号无法进展。但在弧上，.又有，所以给标.于是又得到一条增广链：.再进展调整见图7-23.再重新进展标号求新的增广链：开场给标0，+，检查，给标.检查：这时弧均已饱和。而在弧上，因，又有所以给标，说明弧为后向弧.检查，给标。检查，给标。于是又得到一条增广链：.再进展调整见图7-24。再重新进展标号求新的增广链：开场给标(0,+)，检查，给标。检查，这时和均为前向弧，都已饱和，弧为后向弧，且为零流弧。故标号无法进展。但在弧上因为。又有.所以给标.检查,给标。检查，因为已饱和见图7-24。而在弧上，因为，又有.所以给标，再检查，给标。于是又得到一条增广链：.再进展调整见图7-25。再重新进展标号求新的增广链。开场给标(0,+)，检查，给标。检查，因为已饱和，而为弧上标号还可以继续进展，给标。检查。给标。于是又得到一条增广链再进展调整见图7-26。再重新进展标号：开场给标(0,+)，检查：这时弧已饱和。标号无法进展。而还可以标号。再检查，如前所述，标号也无法进展。至此已求得最大流。我们将最大流表示在图7-27中。最大流量为与此同时，可找到最小截集，其中为最后一轮已标号点的集合，为未标号点的集合，即最小截量为所以。图7-27由上述可见，用标号法找增广链以求最大流的结果，同时也得到一个最小截集。最小截集的容量的大小影响总的运输量的提高。因此，为提高总的运输量，必须首先考虑增大最小截集中各弧的容量，提高它们的通过能力。反之，一旦最小截集中弧的通过能力降低，必然会使得运输量减少。前面讨论都是对一个发点、一个收点的网络最大流问题。对于多个发点和收点的情形，我们可以采取虚设一个总发点和总收点，从总发点到各发点均以弧相联，并且令这些弧的容量均为或*一具体值根据情况而定。同样，从各个收点到总收点亦以弧相联，也令这些弧的容量为或*一具体值。这样，原来的发点与收点都变成了转运点，原来的问题就转变成一个发点一个收点的网络图。例如图7-28所示是两个发点两个收点的网络，可以转换成一个发点一个收点的网络，见图7-29所示。图7-29第一节第二节第三节第四节返回. z.