《离散数学第十三章》由会员分享,可在线阅读,更多相关《离散数学第十三章(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 )。 (