离散数学第十三章.ppt

1、2020/9/4,离散数学,1,第十三章 网络最大流,2020/9/4,离散数学,2,13.1 网络的流与割,2020/9/4,离散数学,3,网络的定义,定义12.1.1：设有向图N具有两个非空的顶点子集X、Y，XY=，并且在弧集A上定义了一个非负整数值的函数C，则称N为一个网络，记为N(X, Y, C)，其中： 1)X和Y中的顶点分别称为源和汇，其它顶点称为中间点。 2)函数C：AN( N为非负整数集)，称为此网络的容量函数，它在一条弧上的值称为该弧的容量。记为C()或C(i, j)，这里= (i, j)A。,2020/9/4,离散数学,4,一个网络,下面是一个网络：,x,y,v1,v5,v

2、6,v4,v3,v2,4,6,5,2,4,4,7,1,4,2,1,8,其中：x和y分别为源和汇；v1 v6为中间点；各弧上标记的整数是该弧的容量函数值，例如C(x, v1)=4。,2020/9/4,离散数学,5,网络中的一个函数 f,设N是有一个源x和一个汇y的网络，f是定义在弧集A(N)上的一个整数值函数，即f：AN ( N为整数集) ，V1、V2是V(N)的子集。记 (V1, V2) = (u, v)A(N)|uV1, vV2, f (V1, V2) = f ()，这里(V1, V2)。 特别，当V1= i 时，将f (V1, V2) 记为f (i, V2)。,函数f 可以看作网络中弧上的

3、实际流量。它们还需要满足一定的条件才会在网络上形成“流”。,2020/9/4,离散数学,6,流的概念,定义13.1.2：设N(x, y, C) 是一个网络，f是定义在A(N)上的一个整数值的函数。若f满足： 对A(N) ，0f ()C(); (13.1) 对中间点i有f (i, V)= f (V, i); (13.2) 则称f是网络N的一个流， f (x, V)称为流f 的值，记为f xy。其中： 式(13.1)称为约束条件，即流量不超过容量。 式(13.2)称为守恒条件，即任何中间点的流入等于流出。,2020/9/4,离散数学,7,流的一个例子,上图给出了一个网络及其流。 弧上的第一个数字是

4、容量，第二个是流。 可以验证该网络满足约束条件和守恒条件。 该网络的流 f 的值 fxy = f (x, V) =4+4=8。,x,v1,v2,v4,v3,y,8,4,7,4,5,1,2,0,9,5,9,3,6,1,5,4,10,4,2020/9/4,离散数学,8,最大流,定义13.1.3：设 f 是网络的一个流。如果不存在N的流 f，使得 fxy fxy，则称f 为最大流，记为fmax。 运输网络的一个主要问题就是找出它的一个最大流 f max，最大流表示在尽量满足条件的情况下，网络中各条干线上的最大运输量。 为了解决网络最大流的问题，需要引进割的概念。,2020/9/4,离散数学,9,割,

5、定义13.1.4：设N = (x, y, C)为一个网络，V1V(N), xV1, yV1=V(N)V1， 称(V1, V1)为N的一个割，记为 K=(V1, V1)=(u,v)A(N)|uV1,vV1 。 由割的定义可知，网络N的一个割即是分离源和汇的弧之集合。记 C (K) = K C ()。 称C (K) 为割K的容量。,2020/9/4,离散数学,10,割的例子,x,v1,v2,v4,v3,y,8,4,7,4,5,1,2,0,9,5,9,3,6,1,5,4,10,4,在网络中，若取V1=x, v1, v2, V1=y, v3, v4，则K1 = v1v3，v2v4。,这个割的容量为 C

6、(K1) = C(v1v3) + C(v2v4) = 18.,在网络中，取V1=x, V1=y, v1, v2, v3, v4，则K2 = xv1，xv2。,这个割的容量为 C(K2) = C(xv1) + C(xv2) = 15.,在网络中，取V1=x, v1, V1=y, v2, v3, v4，则K3 = xv2，v1v2，v1v3。,这个割的容量为 C(K3) = C(xv2) + C(v1v2) + C(v1v3) = 21.,在网络中，取V1=x, v1, v2, v3, V1=y, v4，则K4 = v3y，v2v4。,这个割的容量为 C(K4) = C(v2v4) + C(v3y

7、) = 14.,由此可知网络可有多个割，且容量可以不同。,2020/9/4,离散数学,11,最小割,定义13.1.5：设K是网络N的一个割，若不存在N的其它割K，使得 C(K) C(K), 则称K为N的最小割，记为Kmin。 在上例中K4是N的最小割，其容量为14。 割其实是网络上的咽喉要道，割的容量自然会制约着网络上的流。实际上最小割的容量就是网络的最大流。,2020/9/4,离散数学,12,割与流,定理13.1.1：设网络N的流 f 的值为fxy，(V1, V1)是N的割.于是 fxy = f (V1, V1) f (V1, V1)。,证明：由流的定义：f (x, V) = fxy；f (

8、V, x) = 0； f (v, V) f (V, v) = 0, vx, y(守恒条件)； 于是对任意的SV，xS，yS，有 fxy = vS f (v, V) f (V, v) ， 或者 fxy = f (S, V) f (V, S)。 将V=SS代入可得fxy = f (S, S) f (S, S)。,？,由S的任意性可知定理成立。,将V = SS代入该式，并注意到SS = ： fxy = f(S, V) f(V, S) = f(S, SS) f(SS, S) 而f(S, SS) = f(S, S)+ f(S, S) f(S, SS) = f(S, S)+ f(S, S)， f(SS,

9、S) = f(S, S)+ f(S, S) f(SS, S) = f(S, S)+ f(S, S)。 即fxy = f(S, S) f(S, S)。,2020/9/4,离散数学,13,流值不超过最小割的容量,定理13.1.1说明，网络中任何从源到汇的流的值等于任何割中的流的净值，即割的正向流(从V1到V1)与逆向流(从V1到V1)的差值。 推论13.1.1：设(V1, V1)是网络的任意一个割，于是 fxy C (V1, V1)。 证明：由定理13.1.1知fxy=f(V1, V1)- f(V1, V1) 即fxy f (V1, V1) ,由约束条件知 f (V1, V1) C (V1, V1

10、)，故结论成立。 显然对于任何网络，均有fmax C(Kmin)。,2020/9/4,离散数学,14,13.2 最大流与最小割定理,2020/9/4,离散数学,15,最大流最小割定理,定理13.2.1(最大流最小割定理)：任何网络中最大流的值等于最小割的容量，即 fmax=C(Kmin)。,证明：设f是最大流，按照如下的方法定义N的顶点子集V1： xV1； 若viV1，且f (vi, vj)C(vi, vj)，则vj V1； 若viV1，且f (vj, vi)0，则vj V1。 由V1的定义可以证明，yV1。,？,因此(V1, V1)是割。其中：V1=V-V1,若yV1，则按V1的定义，将有从

11、x到y的“链” (不一定是有向链)。设 =xv1vmy，其中，若vivi+1A(N)，则称为前向弧；若vi+1viA(N)，则称为后向弧； 将中前向弧的集合记为+，后向弧的集合记为。于是有对+中的和中的均有：f ()C()， f ()0。取 =min(minC()f()|+, minf()| 显然0，现将f修改为f： f() = if + then f()+ else if then f() else f() 不难验证f仍是N的一个流，但是fxy= f xy+ ，这与f 是最大流矛盾。故y V1。,2020/9/4,离散数学,16,最大流最小割定理,证明： 构造(V1, V1)是N的一个割 。

12、,按V1的定义，若(vi,vj)(V1, V1)，则 f (vi,vj) = C(vi,vj)，(由V1的定义(2)和约束条件）若(vj,vi)(V1, V1)，则f (vj,vi) = 0， (由V1的定义(3)）否则vj将在V1中。于是有 f (V1, V1) = C(V1, V1)， f (V1, V1) = 0。 从而，由定理13.1.1,有 f xy = C(V1, V1)， 此时必有f xy = f max=C(Kmin) = C(V1, V1)。证毕。,2020/9/4,离散数学,17,求最大流方法的基本思想,定理13.2.1的证明是构造性的因而也给出了求最大流的方法；即任取一个

13、流，然后设法逐步增大流值，直至不能再增大为止。具体做法是： 按照定理中的定义寻找从x到y的“链”，使其所有前向弧满足f ()C() (称为未饱和弧) ，后向弧满足 f ()0。那么就可以使该“链”上的前向弧增加，后向弧减少，从而使流值增加了。这种“链”称为可增广路。 反复这样做，直到网络上不再有可增广路。,2020/9/4,离散数学,18,求网络最大流的算法,本算法称为标记法。给每个顶点j标记(i, , (j)，其中i为弧的另一个端点，为“+”和“”，分别表示前向弧和后向弧， 表示该弧能增大的流值。 本算法分两个部分：标记过程和增广过程。 将源x标记为(x, +, ) (初始化) ； 进行标记

14、过程，直至汇y被标记，或无顶点可被标记； 若是汇y被标记，则进行增广过程；然后转重新进行标记过程； 若是无顶点可被标记，则算法终止。,2020/9/4,离散数学,19,标记过程,标记过程就是从源到汇寻找一条可增广路，所谓的标记就是表明该路上的弧是前向弧还是后向弧，以及可增加的量。,将源x标记为(x, +, )并注成已标记未检查。 任取一个已标记未检查的顶点i，若顶点j与i邻接且尚未标记，则按如下方法标注顶点j： 当(i, j)A (N)，C(i, j)f (i, j)时，将j标记上(i, +, (j)，其中(j)=min(i), C(i, j) f (i, j)； 当(j, i)A (N)，f

15、 (j, i)0时，将j标记上(i, , (j)，其中(j)=min(i), f (j, i)； 将顶点i注成已检查。 重复, 直到汇y被标记或无顶点可标记。,2020/9/4,离散数学,20,增广过程,增广过程就是在可增广路上从汇到源修改该路上各弧的流值。 令z = y； = (y); 若z的标记为(q, +, (j)，则把f (q, z)增加；若z的标记为(q, , (j)，则把f (z, q)减少；并撤消z的标记； 令z = q； 若z = x；则终止增广过程，否则转。,2020/9/4,离散数学,21,求最大流举例,将x标记为(x, +, );,x,v1,v2,v4,v3,y,8,4,

16、7,4,5,1,2,0,9,5,9,3,6,1,5,4,10,4,(x, +, ),考察x邻接的顶点v1并标记为(x, +, 4 )；,(x, +, 4 ),考察v1邻接的顶点v3并标记为(1, +, 4 )。,(1, +, 4 ),考察v3邻接的顶点y并标记为(3, +, 1 )。,(3, +, 1 ),到达了汇y； = (y)=1，进行增广过程。,5, 5,9, 4,8, 5,2020/9/4,离散数学,22,求最大流举例,x,v1,v2,v4,v3,y,8,5,7,4,5,1,2,0,9,5,9,4,6,1,5,5,10,4,(x, +, ),考察x邻接的顶点v2并标记为(x, +, 3

17、)；,(x, +, 3),考察v2邻接的顶点v4并标记为(2, +, 3 )。,(2, +, 3),考察v4邻接的汇y并标记为(4, +, 3)。,(4, +, 3),到达了汇y； = (y)=3，进行增广过程。,10,7,9,8,7,7,2020/9/4,离散数学,23,求最大流举例,x,v1,v2,v4,v3,y,8,5,7,7,5,1,2,0,9,8,9,4,6,1,5,5,10,7,(x, +, ),考察x邻接的顶点v1并标记为(x, +, 3)；,(x, +, 3),考察v1邻接的顶点v2并标记为(1, +, 3)；,(1, +, 3),考察v2邻接的顶点v4并标记为(2, +, 1

18、 )。,(2, +, 1),考察v4邻接的汇y并标记为(4, +, 1)。,(4, +, 1),到达了汇y； = (y)=1，进行增广过程。,10,8,9,9,5,2,8,6,2020/9/4,离散数学,24,求最大流举例,x,v1,v2,v4,v3,y,8,6,7,7,5,1,2,0,9,9,9,4,6,1,5,5,10,8,5,2,(x, +, ),考察x邻接的顶点v1并标记为(x, +, 2)；,(x, +, 2),考察v1邻接的顶点v3并标记为(1, +, 2 )。,(1, +, 2),考察v3邻接的顶点v4并标记为(3, , 1 )。,(3, , 1),考察v4邻接的汇y并标记为(4, +, 1)。,(4, +, 1),到达了汇y； = (y)=1，进行增广过程。,10,9,6,0,9,5,8,7,2020/9/4,离散数学,25,求最大流举例,x,v1,v2,v4,v3,y,8,7,7,7,5,1,2,0,9,9,9,5,6,0,5,5,10,9,5,2,这时，网络中不再存在可增广路。这就是该网络的最大流。,V1 = x, v1, v2, v3, V1 = y, v4, 割(V1, V1) = v2v4, v3y为最小割，它的容量为14。于是，该网络的最大流