《离散数学第十三章》由会员分享，可在线阅读，更多相关《离散数学第十三章（27页珍藏版）》请在金锄头文库上搜索。
1、第十三章 网络最大流 *1离散数学 13.1 网络的流与割 *2离散数学 网络的定义 4定义12.1.1：设有向图N具有两个非空的顶点子 集X、Y，XY=，并且在弧集A上定义了一 个非负整数值的函数C，则称N为一个网络， 记为N(X, Y, C)，其中： 41)X和Y中的顶点分别称为源和汇，其它顶点称 为中间点。 42)函数C：AN( N为非负整数集)，称为此网 络的容量函数，它在一条弧上的值称为该弧的 容量。记为C()或C(i, j)，这里= (i, j)A。 Date3离散数学 一个网络 4下面是一个网络： x y v1 v5 v6 v4v3 v2 4 6 5 2 4 4 7 1 4 2
2、1 8 4其中：x和y分别为源和汇；v1 v6为中间点； 各弧上标记的整数是该弧的容量函数值，例如 C(x, v1)=4。 Date4离散数学 网络中的一个函数 f 4设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)。 4特别，当V1= i 时，将f (V1, V2) 记为f (i, V2) 。 4函数f 可以看作网络中弧上的实际流量。它们 还需要满足一定的条件才会在网络上形成“流”
3、 。 Date5离散数学 流的概念 4定义13.1.2：设N(x, y, C) 是一个网络，f是定义 在A(N)上的一个整数值的函数。若f满足： 4对A(N) ，0f ()C(); (13.1) 4对中间点i有f (i, V)= f (V, i); (13.2) 4则称f是网络N的一个流， f (x, V)称为流f 的值 ，记为f xy。其中： 4式(13.1)称为约束条件，即流量不超过容量。 4式(13.2)称为守恒条件，即任何中间点的流入 等于流出。 Date6离散数学 流的一个例子 4上图给出了一个网络及其流。 4弧上的第一个数字是容量，第二个是流。 4可以验证该网络满足约束条件和守恒条
4、件。 4该网络的流 f 的值 fxy = f (x, V) =4+4=8。 x v1 v2v4 v3 y 8,4 7,4 5,1 2,0 9,5 9,3 6,1 5,4 10,4 Date7离散数学 最大流 4定义13.1.3：设 f 是网络的一个流。如果不存在 N的流 f，使得 fxy fxy，则称f 为最大流，记 为fmax。 4运输网络的一个主要问题就是找出它的一个最 大流 f max，最大流表示在尽量满足条件的情况 下，网络中各条干线上的最大运输量。 4为了解决网络最大流的问题，需要引进割的概 念。 Date8离散数学 割 4定义13.1.4：设N = (x, y, C)为一个网络，
5、V1V(N), xV1, yV1=V(N)V1， 称(V1, V1)为N的一个割，记为 K=(V1, V1)=(u,v)A(N)|uV1,vV1 。 4由割的定义可知，网络N的一个割即是分离源 和汇的弧之集合。记 C (K) = K C ()。 4称C (K) 为割K的容量。 Date9离散数学 割的例子 x v1 v2v4 v3 y 8,4 7,4 5,1 2,0 9,5 9,3 6,1 5,4 10,4 4在网络中，若取V1=x, v1, v2, V1=y, v3, v4 ，则K1 = v1v3，v2v4。 4这个割的容量为 C(K1) = C(v1v3) + C(v2v4) = 18.
6、4在网络中，取V1=x, V1=y, v1, v2, v3, v4， 则K2 = xv1，xv2。 4这个割的容量为 C(K2) = C(xv1) + C(xv2) = 15. 4在网络中，取V1=x, v1, V1=y, v2, v3, v4， 则K3 = xv2，v1v2，v1v3。 4这个割的容量为 C(K3) = C(xv2) + C(v1v2) + C(v1v3) = 21. 4在网络中，取V1=x, v1, v2, v3, V1=y, v4 ，则K4 = v3y，v2v4。 4这个割的容量为 C(K4) = C(v2v4) + C(v3y) = 14. 4由此可知网络可有多个割，且
7、容量可以不同 。 Date10离散数学 最小割 4定义13.1.5：设K是网络N的一个割，若 不存在N的其它割K，使得 C(K) C(K), 4则称K为N的最小割，记为Kmin。 4在上例中K4是N的最小割，其容量为14。 4割其实是网络上的咽喉要道，割的容量 自然会制约着网络上的流。实际上最小 割的容量就是网络的最大流。 Date11离散数学 割与流 4定理13.1.1：设网络N的流 f 的值为fxy，(V1, V1)是N的割.于是 fxy = f (V1, V1) f (V1, V1) 。 4证明：由流的定义：f (x, V) = fxy；f (V, x) = 0 ； f (v, V) f
8、 (V, v) = 0, vx, y(守恒条件)； 4于是对任意的SV，xS，yS，有 fxy = vS f (v, V) f (V, v) ， 或者 fxy = f (S, V) f (V, S)。 4将V=SS代入可得fxy = f (S, S) f (S, S)。 ？ 4由S的任意性可知定理成立。 4将V = SS代入该式，并注意到SS = ： 4fxy = f(S, V) f(V, S) = f(S, SS) f(SS, S) 4而f(S, SS) = f(S, S)+ f(S, S) f(S, SS) = f(S, S)+ f(S, S)， 4 f(SS, S) = f(S, S)+
9、 f(S, S) f(SS, S) = f(S, S)+ f(S, S)。 4即fxy = f(S, S) f(S, S)。 Date12离散数学 流值不超过最小割的容量 4定理13.1.1说明，网络中任何从源到汇的流的 值等于任何割中的流的净值，即割的正向流(从 V1到V1)与逆向流(从V1到V1)的差值。 4推论13.1.1：设(V1, V1)是网络的任意一个割 ，于是 fxy C (V1, V1)。 4证明：由定理13.1.1知fxy=f(V1, V1)- f(V1, V1) 即fxy f (V1, V1) ,由约束条件知 f (V1, V1) C (V1, V1)，故结论成立。 4显然
10、对于任何网络，均有fmax C(Kmin)。 Date13离散数学 13.2 最大流与最小割定理 *14离散数学 最大流最小割定理 4定理13.2.1(最大流最小割定理)：任何网络中最 大流的值等于最小割的容量，即 fmax=C(Kmin)。 4证明：设f是最大流，按照如下的方法定义N的 顶点子集V1： 4xV1； 4若viV1，且f (vi, vj)C(vi, vj)，则vj V1； 4若viV1，且f (vj, vi)0，则vj V1。 4由V1的定义可以证明，yV1。 ？ 因此(V1, V1)是割。其中：V1=V-V1 4若yV1，则按V1的定义，将有从x到y的“链” (不一定是有向链)
11、。设 =xv1vmy，其中，若 vivi+1A(N)，则称为前向弧；若vi+1viA(N)， 则称为后向弧； 将中前向弧的集合记为+， 后向弧的集合记为。于是有对+中的和 中的均有：f ()C()， f ()0。取 4=min(minC()f()|+, minf()| 4显然0，现将f修改为f： f() = if + then f()+ else if then f() else f() 4不难验证f仍是N的一个流，但是fxy= f xy+ ， 这与f 是最大流矛盾。故y V1。 Date15离散数学 最大流最小割定理 4证明： 构造(V1, V1)是N的一个割 。 4 按V1的定义，若(vi
12、,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。 4从而，由定理13.1.1,有 f xy = C(V1, V1)， 4此时必有f xy = f max=C(Kmin) = C(V1, V1)。证 毕。 Date16离散数学 求最大流方法的基本思想 4定理13.2.1的证明是构造性的因而也给出了求 最大流的方法；即任取一个流，然后设法逐步 增大
13、流值，直至不能再增大为止。具体做法是 ： 4按照定理中的定义寻找从x到y的“链”，使其 所有前向弧满足f ()C() (称为未饱和弧) ，后向弧满足 f ()0。那么就可以使该“链” 上的前向弧增加，后向弧减少，从而使流值 增加了。这种“链”称为可增广路。 4反复这样做，直到网络上不再有可增广路。 Date17离散数学 求网络最大流的算法 4本算法称为标记法。给每个顶点j标记(i, , (j) ，其中i为弧的另一个端点，为“+”和“”，分别 表示前向弧和后向弧， 表示该弧能增大的流值 。 4 本算法分两个部分：标记过程和增广过程。 4将源x标记为(x, +, ) (初始化) ； 4进行标记过程
14、，直至汇y被标记，或无顶点可 被标记； 4若是汇y被标记，则进行增广过程；然后转 重新进行标记过程； 4若是无顶点可被标记，则算法终止。Date18 离散数学 标记过程 4标记过程就是从源到汇寻找一条可增广 路，所谓的标记就是表明该路上的弧是 前向弧还是后向弧，以及可增加的量。 4将源x标记为(x, +, )并注成已标记未检查。 4任取一个已标记未检查的顶点i，若顶点j与i 邻接且尚未标记，则按如下方法标注顶点j： 4当(i, j)A (N)，C(i, j)f (i, j)时，将j标记上 (i, +, (j)，其中(j)=min(i), C(i, j) f (i, j)； 4当(j, i)A
15、(N)，f (j, i)0时，将j标记上(i, , (j)，其中(j)=min(i), f (j, i)； 4将顶点i注成已检查。 4重复, 直到汇y被标记或无顶点可标记。 Date19离散数学 增广过程 4增广过程就是在可增广路上从汇到源修 改该路上各弧的流值。 4令z = y； = (y); 4 若z的标记为(q, +, (j)，则把f (q, z)增 加；若z的标记为(q, , (j)，则把f (z, q)减少；并撤消z的标记； 4令z = q； 4若z = x；则终止增广过程，否则转。 Date20离散数学 求最大流举例 4将x标记为(x, +, ); x v1 v2 v4 v3 y 8,4 7,4 5,1 2,0 9,5 9,3 6,1 5,4 10,4(x, +, ) 4考察x邻接的顶点v1并标记为(x, +, 4 )； (x, +, 4 ) 4考察v1邻接的顶点v3并标记为(1, +, 4 )。 (1, +, 4 ) 4考察v3邻接的顶点y并标记为(3, +, 1 )。 (
