离散数学第十三章.ppt

第十三章 网络最大流 *1离散数学 §13.1 网络的流与割 *2离散数学 网络的定义 4定义12.1.1：设有向图N具有两个非空的顶点子 集X、Y，X∩Y=，并且在弧集A上定义了一 个非负整数值的函数C，则称N为一个网络， 记为N(X, Y, C)，其中： 41)X和Y中的顶点分别称为源和汇，其它顶点称 为中间点 42)函数C：A→N( 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 1 8 4其中：x和y分别为源和汇；v1~ v6为中间点； 各弧上标记的整数是该弧的容量函数值，例如 C(x, v1)=4 Date4离散数学 网络中的一个函数 f 4设N是有一个源x和一个汇y的网络，f是定义在 弧集A(N)上的一个整数值函数，即f：A→N ( N为整数集) ，V1、V2是V(N)的子集记 (V1, V2) = {(u, v)∈A(N)|u∈V1, v∈V2}, f (V1, V2) = ∑f ()，这里∈(V1, V2)。

4特别，当V1= { i }时，将f (V1, V2) 记为f (i, V2) 4函数f 可以看作网络中弧上的实际流量它们 还需要满足一定的条件才会在网络上形成“流” Date5离散数学 流的概念 4定义13.1.2：设N(x, y, C) 是一个网络，f是定义 在A(N)上的一个整数值的函数若f满足： 4⑴对∈A(N) ，0≤f ()≤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该网络的流 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’，使得 f’xy ＞ fxy，则称f 为最大流，记 为fmax 4运输网络的一个主要问题就是找出它的一个最 大流 f max，最大流表示在尽量满足条件的情况 下，网络中各条干线上的最大运输量 4为了解决网络最大流的问题，需要引进割的概 念 Date8离散数学 割 4定义13.1.4：设N = (x, y, C)为一个网络， V1V(N), x∈V1, y∈V1=V(N)–V1， 称(V1, V1)为N的一个割，记为 K=(V1, V1)={(u,v)∈A(N)|u∈V1,v∈V1} 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. 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由此可知网络可有多个割，且容量可以不同 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 (V, v) = 0, v≠x, y(守恒条件)； 4于是对任意的SV，x∈S，y∈S，有 fxy = ∑v∈S [ f (v, V) – f (V, v)] ， 或者 fxy = f (S, V) – f (V, S) 4将V=S∪S代入可得fxy = f (S, S) – f (S, S) ？ 4由S的任意性可知定理成立 4将V = S∪S代入该式，并注意到S∩S = ： 4fxy = f(S, V) – f(V, S) = f(S, S∪S) –f(S∪S, S) 4而f(S, S∪S) = f(S, S)+ f(S, S) – f(S, S∩S) = f(S, S)+ f(S, S)， 4 f(S∪S, S) = f(S, S)+ f(S, S) – f(S∩S, 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显然对于任何网络，均有fmax ≤ C(Kmin) Date13离散数学 §13.2 最大流与最小割定理 *14离散数学 最大流最小割定理 4定理13.2.1(最大流最小割定理)：任何网络中最 大流的值等于最小割的容量，即 fmax=C(Kmin) 4证明：设f是最大流，按照如下的方法定义N的 顶点子集V1： 4⑴x∈V1； 4⑵若vi∈V1，且f (vi, vj)＜C(vi, vj)，则vj ∈V1； 4⑶若vi∈V1，且f (vj, vi)＞0，则vj ∈V1 4由V1的定义可以证明，y∈V1 ？ 因此(V1, V1)是割其中：V1=V-V1 4若y∈V1，则按V1的定义，将有从x到y的“链” (不一定是有向链)设 =xv1…vmy，其中，若 vivi+1∈A(N)，则称为前向弧；若vi+1vi∈A(N)， 则称为后向弧； 将中前向弧的集合记为+， 后向弧的集合记为–。

于是有对+中的和– 中的均有：f ()＜C()， f ()＞0取 4=min(min{C()–f()|∈+}, min{f()| ∈–}} 4显然＞0，现将f修改为f’： f’() = if ∈+ then f()+ else if ∈– then f() –  else f() 4不难验证f’仍是N的一个流，但是f’xy= f xy+ ， 这与f 是最大流矛盾故y ∈V1 Date15离散数学 最大流最小割定理 4证明：… 构造(V1, V1)是N的一个割 4 按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 4从而，由定理13.1.1,有 f xy = C(V1, V1)， 4此时必有f xy = f max=C(Kmin) = C(V1, V1)。

证 毕 Date16离散数学 求最大流方法的基本思想 4定理13.2.1的证明是构造性的因而也给出了求 最大流的方法；即任取一个流，然后设法逐步 增大流值，直至不能再增大为止具体做法是 ： 4按照定理中的定义寻找从x到y的“链”，使其 所有前向弧满足f ()＜C() (称为未饱和弧) ，后向弧满足 f ()＞0那么就可以使该“链” 上的前向弧增加，后向弧减少，从而使流值 增加了这种“链”称为可增广路 4反复这样做，直到网络上不再有可增广路 Date17离散数学 求网络最大流的算法 4本算法称为标记法给每个顶点j标记(i, , (j)) ，其中i为弧的另一个端点，为“+”和“–”，分别 表示前向弧和后向弧， 表示该弧能增大的流值 4 本算法分两个部分：标记过程和增广过程 4⑴将源x标记为(x, +, ∞ ) (初始化) ； 4⑵进行标记过程，直至汇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 (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 )。