第十二章网络流模型

1、一、基本概念一、基本概念定义定义1：一个有向图：一个有向图G =(V,A)，若对，若对G 的每一个弧的每一个弧(vi,vj) A , 均对应均对应一个非负数一个非负数c (vi,vj) 0 (或简记或简记cij ）,称为此弧段的容量，则称此图称为此弧段的容量，则称此图G 为网络。为网络。定义定义2：定义在弧集：定义在弧集A到非负实数集合上的一个函数到非负实数集合上的一个函数f 称为称为G上的网上的网络流，它表示为络流，它表示为f (vi,vj)| (vi,vj) A ,并称并称f (vi,vj)为弧为弧(vi,vj)上的流量上的流量或流值（简记为或流值（简记为fij )。定义定义3：满足下列条

2、件的流量：满足下列条件的流量f 称为可行流称为可行流（1）容量限制：对每一弧）容量限制：对每一弧(vi,vj) A ，f (vi,vj) c (vi,vj) ；（2）平衡条件：）平衡条件：对中间点，流出量对中间点，流出量=流入量，即对每个流入量，即对每个i (i s, t ) 有有:网络中两个特殊点：发点网络中两个特殊点：发点vs 和收点和收点vt 0AvvjiAvvijijjiff),(),()(),(fvfvAvvsjsjs记记：对于发点对于发点 )(),(fvfvAvvjtttj ：对于收点对于收点称称为为这这个个可可行行流流的的流流量量)( fv定义定义4：所谓最大流问题就是求一个网络

3、流：所谓最大流问题就是求一个网络流f (vi,vj)| (vi,vj) A ,使使它符合下列诸式：它符合下列诸式：AvvcftsifftsffvMaxjiijijjjijijjjsjsj),(,., 0 0 二、最大流的增量算法二、最大流的增量算法称称为为中中顶顶点点的的一一切切弧弧的的集集合合中中顶顶点点指指向向则则从从点点收收的的一一个个子子集集，发发点点中中顶顶点点集集是是网网络络：设设定定义义 P P P,PP,vP, v V A)(V,GP5tsA),(),(| ),(PP,PP, P,P,PP,PP,PCP, , PP,jivvijjijijicCAvvvvvv即：即：中一切弧的容

4、量之和，中一切弧的容量之和，定义为定义为它的容量它的容量割集，记作割集，记作134326554124226收点收点发点发点8341PP,535242PP, 6 5 4P 3 2 1P),(),(),(C，结论结论1：任何割集的容量给出了流量的一个上界，即：任何割集的容量给出了流量的一个上界，即PP,Cv 结论结论2： （最大流最小割集定理）（最大流最小割集定理） min)(maxPP, Cfv增量算法的基本思想：给定网络增量算法的基本思想：给定网络G =(V,A)的一个流之后，如何构造的一个流之后，如何构造g =g(vi,vj),使使f+g的流的流v (f+g)能够比能够比v (f)有所增加。

5、对每条弧（有所增加。对每条弧（vi,vj)来说，只要来说，只要f(vi,vj)0 ，也允许，也允许g 取负值，或者说，在反向弧上取正值。取负值，或者说，在反向弧上取正值。相对增量网：定义相对增量网：定义G 相对相对f 的增量网的增量网G(f)如下：其顶点与如下：其顶点与G 的顶点的顶点相同，其弧由相同，其弧由G 的弧的弧(vi,vj)与与f (vi,vj)的值来构造两条或一条弧如下：的值来构造两条或一条弧如下：（1）正向弧）正向弧(vi,vj) ：构造条件为：构造条件为f (vi,vj)0 ,该弧容量定义为该弧容量定义为c (vi,vj)=f (vi,vj)最大流的增量算法的步骤：最大流的增量

6、算法的步骤：（1）选择一个初始流）选择一个初始流f 。例如，对一切。例如，对一切(vi,vj) A ，f (vi,vj) = 0 。（2）构造）构造G =(V,A) 的相对于的相对于f 的增量网络的增量网络G(f) 。（3）在增量网络）在增量网络G(f)上寻找从发点上寻找从发点vs 到收点到收点vt 的路。如果不存在的路。如果不存在这样的路，转到（这样的路，转到（4）。如果找到一条从）。如果找到一条从vs 到到vt 的路的路 , 以以表示表示上上所有容量所有容量c (vi,vj)的最小值（必为正），的最小值（必为正）， 称为网络流的增量。利用称为网络流的增量。利用修正网络流如下：修正网络流如下

7、：当正向弧当正向弧(vi,vj)时，时，f(vi,vj):=f(vi,vj)+ 当负向弧当负向弧(vi,vj) 时，时，f(vi,vj):=f(vi,vj) 修正修正 f 之后，转（之后，转（2）（4）以所得的）以所得的 f 作为最大流问题的解作为最大流问题的解134326554124226收点收点发点发点以上图为例说明上述网络流算法以上图为例说明上述网络流算法初始流：初始流：f(v1,v2)=4 , f(v1,v3)=1 , f(v2,v3)=2 , f(v2,v4)=1 , f(v2,v5)=1 ,f(v3,v5)=3 , f(v5,v4)=1 , f(v4,v6)=2 , f(v5,v6

8、)=3 ,且流量且流量v = 5构造增量网络构造增量网络G(f) :134326514121123收点收点发点发点4313找找G (f) 从从vs 到到vt 的路的路 及相应增量及相应增量 =(v1,v3),(v3,v2),(v2,v5),(v5,v6) =2 ，修正流，修正流 f ，得新的网络流，得新的网络流f ，其流量，其流量v=713,3432655,34,41,12,24,32,12,06,5收点收点发点发点在新的网络图中，每条弧上有两个在新的网络图中，每条弧上有两个数，第一个数与原图相同，表示容数，第一个数与原图相同，表示容量；第二个数为新流。量；第二个数为新流。对新的网络流，构造新

9、的网络增量对新的网络流，构造新的网络增量G(f) ，而在，而在G(f)上已找不到从上已找不到从vs 到到vt 的路。的路。734PP,5321PP,6542P1,3,P),(),(,C其流量其流量对应的割集：对应的割集：此时对图中的流此时对图中的流 f ，其流量为，其流量为7，所有它是最大流，所有它是最大流三、最小费用的增量算法三、最小费用的增量算法已知条件：在网络已知条件：在网络G =(V,A) 中，已知发点中，已知发点vs 和收点和收点vt ；流量；流量v ；容；容量量c (vi,vj)| (vi,vj) A ;每条弧每条弧(vi,vj)所相应的代价所相应的代价l (vi,vj) ，它的含

10、，它的含义是单位流量所相应的费用。义是单位流量所相应的费用。定义定义6 ：所谓最小费用问题就是：要找出：所谓最小费用问题就是：要找出f (vi,vj)| (vi,vj) A ,使得：使得：AvvvvcvvftsiAvvvvfAvvvvfvAvvvvfAvvvvftsvvfvvlzMinjijijijijijjjijijsjsjjjsjsAvvjijiji),(),(,),( | ),(),( | ),(),( | ),(),( | ),(.),(),(),(, ),0 0 最小费用的增量算法的基本思想：利用增量网络的最短路来修正网最小费用的增量算法的基本思想：利用增量网络的最短路来修正网络流络

11、流 f ，使流量有所增加的情况下，仍保持为最小费用流。增量网，使流量有所增加的情况下，仍保持为最小费用流。增量网络的构造与前面方法相同，但要补充弧的代价如下：络的构造与前面方法相同，但要补充弧的代价如下：（1）正向弧）正向弧(vi,vj) 上，有上，有c (vi,vj)= c (vi,vj) f (vi,vj) ， l (vi,vj) =l (vi,vj) （2）反向弧）反向弧(vi,vj) 上，有上，有c (vi,vj)=f (vi,vj) ，l (vi,vj) =l(vi,vj) 最小费用流的增量算法的理论根据：最小费用流的增量算法的理论根据：设设 f 是网络是网络G = (V,A)的最小

12、费用流，的最小费用流，f 的流量为的流量为v ， 是增量网是增量网G(f)上从上从发点发点vs 到收点到收点vt 的以的以l( , )为代价的最短路，为代价的最短路， 为为 上所上所有弧的容量的最小值。又设有弧的容量的最小值。又设0 ，考虑沿，考虑沿 增加流量增加流量 ，用适当方，用适当方式修正式修正 f 。那么，修正后的网络流必是流量为。那么，修正后的网络流必是流量为v + 的最小费用流。的最小费用流。例例2：求右图中最小费用最大流，：求右图中最小费用最大流，图中每条弧图中每条弧 边上第边上第1个数是费用，个数是费用，第第2个数是容量。个数是容量。v1vtvsv3v2（2，4）（1，7）（6

13、，2）（2，5）（3，10）（1，8）（4，10）取初始流量取初始流量f =0为初始为初始可行流可行流构造增量网络构造增量网络G(f)，并，并以以lij 为权，求从为权，求从vs 到到vt 的最短路（双箭头）的最短路（双箭头）v1vtvsv3v2（2，4）（1，7）（6，2）（2，5）（3，10）（1，8）（4，10）v1vtvsv3v20005550在在G (f)中中 从从vs 到到vt 的最的最短路短路 为为 =(vs,v2),(v2,v1),(v1,vt) =5，修正流，修正流 f ，得新，得新的网络流的网络流f ，其流量，其流量v=5v1vtvsv3v2（2，4）（-1，5）（6，2）

14、（-2，5）（3，10）（1，3）（4，10）（1，2）（-1，5）v1vtvsv3v20005572在在G (f)中中 从从vs 到到vt 的最的最短路短路 为为 =(vs,v1),(v1,vt) =2 ，修正流，修正流 f ，得新，得新的网络流的网络流f ，其流量，其流量v=7v1vtvsv3v2（2，4）（-1，7）（6，2）（-2，5）（3，10）（1，3）（4，8）（-1，5）（-4，2）在在G (f)中中 从从vs 到到vt 的最的最短路短路 为为 =(vs,v2),(v2,v3),(v3,vt) =3 ，修正流，修正流 f ，得新，得新的网络流的网络流f ，其流量，其流量v=10v1vtvsv3v23035872v1vtvsv3v2（2，1）（-1，7）（6，2）（-2，5）（3，7）（-1，8）（4，8）（- 4，2）（- 2，3）（- 3，3）在在G (f)中中 从从vs 到到vt 的最的最短路短路 为为 =(vs,v1),(v1,v2), (v2,v3),(v3,vt) =1 ，修正流，修正流 f ，得新，得新的网络