CHAP网络最大流.ppt

离散数学 第十三章 网络最大流 §13.1 网络的流与割 网络的定义 定义12.1.1：设有向图N具有两个非空的顶点子集X、Y，X∩Y=?，并且在弧集A上定义了一个非负整数值的函数C，则称N为一个网络，记为N(X, Y, C)，其中： 1)X和Y中的顶点分别称为源和汇，其它顶点称为中间点。 2)函数C：A→N( N为非负整数集)，称为此网络的容量函数，它在一条弧上的值称为该弧的容量。记为C(?)或C(i, j)，这里?= (i, j)∈A。 一个网络 下面是一个网络： 网络中的一个函数 f 设N是有一个源x和一个汇y的网络，f是定义在弧集A(N)上的一个整数值函数，即f：A→N，V1、V2是V(N)的子集。记 (V1, V2) = {(u, v)∈A(N)|u∈V1, v∈V2}, f (V1, V2) = ∑f (?)，这里?∈(V1, V2)。 特别，当V1= { i }时，将f (V1, V2) 记为f (i, V2)。 流的概念 定义13.1.2：设N(x, y, C) 是一个网络，f是定义在A(N)上的一个整数值的函数。若f满足： ⑴对??∈A(N) ，0≤f (?)≤C(?); (13.1) ⑵对?中间点i有f (i, V)= f (V, i); (13.2) 则称f是网络N的一个流， f (x, V)称为流f 的值，记为f xy。其中： 式(13.1)称为约束条件，即流量不超过容量。 式(13.1)称为守恒条件，即任何中间点的流入等于流出。 流的一个例子 上图给出了一个网络及其流。 弧上的第一个数字是容量，第二个是流。 可以验证该网络满足约束条件和守恒条件。 该网络的流 f 的值 fxy = 8。 最大流 定义13.1.3：设 f 是网络的一个流。如果不存在N的流 f’，使得 f’xy ＞ fxy，则称f 为最大流，记为fmax。 运输网络的一个主要问题就是找出它的一个最大流 f max，最大流表示在尽量满足条件的情况下，网络中各条干线上的最大运输量。 为了解决网络最大流的问题，需要引进割的概念。 割 定义13.1.4：设N = (x, y, C)为一个网络，V1?V(N), x∈V1, y∈?V1=V(N)–V1，称(V1, ?V1)为N的一个割,记为K(V1, ? V1) 由割的定义可知，网络N的一个割既是分离源和汇的弧之集合。记 C (K) = ∑??K C (?)。 称C (K) 为割K的容量。 割的例子 在网络中，若取V1={x, v1, v2}, ?V1={y, v3, v4}，则K1 = {v1v3，v2v4}。 最小割 定义13.1.5：设K是网络N的一个割，若不存在N的其它割K’，使得 C(K’) ＜ C(K), 则称K为N的最小割，记为Kmin。 在上例中K4是N的最小割，其容量为14。 割其实是网络上的咽喉要道，割的容量自然会制约着网络上的流。实际上最小割的容量就是网络的最大流。 割与流 定理3.1.1：设网络N的流 f 的值为fxy，(V1, ?V1)是N的割。于是 fxy = f (V1, ?V1) – f (?V1, V1)。 流值不超过最小割的容量 定理13.1.1说明，网络中任何从源到汇的流的值等于任何割中的流的净值，即割的正向流(从V1到?V1)与逆向流(从?V1到V1)的差值。 推论13.1.1：设(V1, ?V1)是网络的任意一个割，于是 fxy ≤ C (V1, ?V1)。 显然对于任何网络，均有fmax ≤ C(Kmin)。 §13.2 最大流与最小割定理 最大流最小割定理 定理13.2.1(最大流最小割定理)：任何网络中最大流的值等于最小割的容量，即 fmax=C(Kmin)。 最大流最小割定理 证明：… 构造(V1, ?V1)是N的一个割 。 求最大流方法的基本思想 定理13.2.1的证明是构造性的因而也给出了求最大流的方法；即任取一个流，然后设法逐步增大流值，直至不能再增大为止。具体做法是： 按照定理中?的定义寻找从x到y的“链”，使其所有前向弧?满足f (?)＜C(?) (称为未饱和弧) ，后向弧?满足 f (?)＞0。那么就可以使该“链”上的前向弧增加?，后向弧减少?，从而使流值增加了?。这种“链”称为可增广路。 反复这样做，直到网络上不再有可增广路。 求网络最大流的算法 本算法称为标记法。给每个顶点j标记(i, ?, ?(j))，其中i为弧的另一个端点，?为“+”和“–”，分别表示前向弧和后向弧， ?表示该弧能增大的流值。 本算法分两个部分：标记过程和增广过程。 ⑴将源x标记为(x, +, ∞ ) (初始化) ； ⑵进行标记过程，直至汇y被标记，或无顶点可被标记； ⑶若是汇y被标记，