中科院研究生院专业基础课：《图论与网络流理论》第九章网络流理论（高随祥）

§9.1 网络与网络流的基本概念 §9.2 最大流最小割定理及求最大流的标号算法 §9.3 求最大流的 Dinic 算法 §9.4 最小费用流问题

团购合买资源类别：文库，文档格式：PDF，文档页数：20，文件大小：472.31KB

§9.1 网络与网络流的基本概念定义 9.1.1 一个网络 N=(V,A)是指一个连通无环弧且满足下列条件的有向图： (1) 有一个顶点子集 X，其每个顶点的入度都为 0； (2) 有一个与 X 不相交的顶点子集 Y，其每个顶点的出度都为 0； (3) 每条弧都有一个非负的权，称为弧的容量。注：上述网络 N 可写作 N=(V, X, Y, A, C)，X 称为网络的发点集或源点集，Y 称为网络的收点集或汇点集，C 称为网络的容量函数。例：定义 9.1.2 网络 N=(V, X, Y, A, C)中的一个(可行)流是指定义在 A 上的一个整值函数 f，使得： (1) 对∀∈ ≤ ≤ a A f a ca ,0 () () ，(容量约束); (2) 对 vV X Y f v f v ( ), ( ) ( ) − + ∀∈ − = ∪ ，(流量守恒)。其中 f ( ) v − 表示点 v 处入弧上的流量之和， f ( ) v + 表示点 v 处出弧上的流量之和。注：(1) 可行流总是存在的，比如 f ≡ 0。 (2) 现实问题中有许多关于网络和流的实例。比如：产销物资输送网络；输油管线网络；通信数据传输网络等。定义 9.1.3 设 f 是网络 N=(V, X, Y, A, C)中的一个可行流，则必有 f ( ) () X fY + − = 。 f ( ) X + (或 f ( ) Y − )称为流 f 的流量，记为Val f 。网络最大流问题：给定网络 N=(V, X, Y, A, C)，求 N 中流量最大的可行流(称为最大流)。注：如果一个网络中的源点集和汇点集都只含一个顶点，则称该网络为单源单汇网络。任一网络 N=(V,X, Y, A, C)都可导出一个单源单汇网络。方法如下： (1) 给 N 添加两个新顶点 s 和 t； (2) 对∀ ∈x X ，从 s 向 x 连一条弧，其容量为∞ (或 ( ) (, ) vN s csv + ∈ ∑ ); (3) 对∀ ∈y Y ，从 y 向 t 连一条弧，其容量为∞ (或 ( ) (,) uN t cut − ∈ ∑ )。新添的顶点 s 和 t 分别称为人工源和人工汇，所得的新网络为 N V stA C ′( ,,, , ) ′ ′′ 。 y1 x2 x1 v2 y3 v1 x3 y2 v3 v4 4 4 4 2 2 2 2 2 2 2 2 2 2 2 2 1 1 3 v1 y v3 v2 v4 x2 x1 3 6 5 2 1 4 3 5 2 2 3

§9.2 最大流最小割定理及求最大流的标号算法一、最大流最小割定理问题：给定网络 N V x y AC = (,,,, ) ，如何求 N 中的最大流？定义 9.2.1 设 P xv v y = 1… k 是网络 N V x y AC = (,,, , ) 中一条 x-y 路(无向)，若弧 1 (, ) i i vv A + ∈ ，则称此弧为路 P 的一条正向弧(或称前向弧，顺向弧)，若弧 1 ( ,) i i vv A + ∈ ，则称此弧为路 P 的一条反向弧 (或称后向弧，逆向弧)。例如：在右图所示的路 P 上，所有弧都是正向弧；在路 Q 上，弧(v1, v3)和 (v2, v6)是正向弧，而(v2, v4)和 (v4, v3)是反向弧。可见，一条弧是正向弧还是反向弧与路有关。定义 9.2.2 设 f 是网络 N V x y AC = (,,,, ) 中的一可行流，P 是 N 中一条 x-y 路。如果对于 P 上任一条弧 a G ，都有 (1) 若弧a G 是 P 的正向弧，则 Δ −> f a ca f a () () () 0 GG G ； (2) 若弧a G 是 P 的反向弧，则 Δ > fa fa () () 0 G G . 则称 P 是流 f 的一条可增路。沿路 P 可增加的流量为 ( ) min ( ) a P f P fa ∈ Δ = Δ G ，称为路 P 上流的增量或可增量。例如：在下图中，每条弧上括号内的数字表示弧的容量，括号外的数字是当前流的流量。图（1）中虚线所示的路 P 是一条可增路。因 1 3 Δfvv (, ) 61 5 = −= ， 3 4 Δfv v (, ) 2 = ， 4 2 Δ = fv v (, ) 5 ， 2 6 Δ =−= fv v (,) 40 4 ，故路 P 上的可增量 Δf P( ) min{5, 2,5, 4} 2 = = 。沿 P 增流后的流网络如图(2) 所示。图(1) 图(2) 由此可见，如果能找到 N 中一条 f 可增路，则可沿着 P 修改流的值，得到一个流值更大的新流 ˆ f ，修改办法如下： () () ˆ() () () ( ), a P a P P fa fP fa fa fP fa a + Δ = −Δ ⎧ ⎪ ⎨ ⎪ ⎩ G G G G G G G 若是的正向弧若是的反向弧不在上，， (*) 修改后的流值为： ˆ Val f Val f f P = +Δ ( ) 。这给出了求网络 N 的最大流的一个途径：反复找 N 中的可增路，沿可增路将流量扩大，直到找不出可增路为止。直观上想，此时应该已达到最大流。下面的定理证实了这一点。 P Q v2 v5 x y v3 v4 v1 v6 v2 v5 (x) (y) v3 v4 v1 v6 4(4) 3(6) 1(1) 0(3) 2(3) 3(5) 3(5) 0(1) 2(4) 5(5) v2 v5 (x) (y) v3 v4 v1 v6 4(4) 1(6) 1(1) 2(3) 2(3) 5(5) 3(5) 0(1) 0(4) 5(5) P

当检查完 u 的所有邻点之后，u 称为已标已查顶点。反复进行上述标、查过程，最终必出现两种结果之一： (i) 汇点 y 获得标号，此时已得到 f 可增路。沿该路增流。 (ii) y 点未获得标号，但已没有已标未查顶点(所有已标顶点都已被查，没有更多的新标号顶点)。此时当前的流 f 即为最大流[设当前已标已查的顶点之集为 S，则(, ) S S 为最小割] 例如：网络 N(V, x, y, A, C)及其上一个流 f,（括号内数字是弧容量）。情况(i)：获得一条 f 可增路情况(ii)：已得到最大流和最小割求网络最大流的 Ford－Fulkerson 标号算法：输入：网络 NV x y AC (,,,, ) 输出：网络 N 中一个最大流。第 0 步(初始化)：对∀ ∈a A ，令 f a() 0 = ；第 1 步：给源点 x 标号(, ) x ∞ 。 L xS : { }, = =Φ 。其中 L 表示已标未查集，S 表示已标已查集。第 2 步：任取u L ∈ ，检查 u 的每个尚未标号的邻点 v。 (1) 若 vNu( ) + ∈ ， v 尚未标号且 Cuv f uv (,) (,) > ，则给 v 标号 ( , , ( )) u lv + ，其中 lv lu Cuv f uv ( ) min{ ( ), ( , ) ( , )} = − 。令 LLv : {} = ∪ 。 (2) 若 vNu( ) − ∈ ， v 尚未标号且 f vu (, ) 0 > ，则给 v 标号 ( , , ( )) u lv − ，其中 lv lu f vu ( ) min{ ( ), ( , )} = 。令 LLv : {} = ∪ 。第 3 步：重复第 2 步，直到汇点 y 被标号，或 y 未被标号但 L = Φ 为止。若是后者，算法结束，当前流是最大流；若是前者，转下步。第 4 步：令 z y = 。第 5 步：若 z 的标号为( , , ( )) w lz + ，则令 f (,) (,) () wz f wz ly = + ；若 z 的标号为( , , ( )) w lz − ，则令 f (, ) (, ) ( ) zw f zw ly = − 。注：不论 z 是哪个点，此处总是 l (y)，因 l (y)是最大的可增量 (沿可增路)。第 6 步：若 w x ≠ ，则令 z w = ，转第 5 步；否则，去掉所有的顶点标号，转第 1 步。 v4 v1 v3 x y v2 7(7) 7(9) 5(8) 0(5) 5(9) 0(2) 0(6) 7(10) 5(5) 2 2 3 3 3 ∞ v4 v1 v3 x y v2 7(7) 9(9) 7(8) 2(5) 5(9) 0(2) 0(6) 9(10) 5(5) 1 1 1 ∞

() () () 0 () () () 0 () () () 0 fx f x f x fy f y f y fu f u f u + − + − + − ⎧ = − ≥ ⎪ ⎨ = − ≤ ⎪ = − = ⎩ 的流。定理 9.3.1 设 f 是网络 N 中的一个可行流。则 (1) N 中 f 可增路与 N ( f )中的 x − y 有向路一一对应。 (2) N 中 f 可增路 P 的可增流值 Δf ( ) P 等于 N ( f )中对应的 x − y 有向路 P G 上最小的弧容量。证明：显然。定理 9.3..2 设 * f 是网络 N 中的最大流，f 是 N 中的一个可行流，则增量网络 N ( f )中的最大流的流值为 * Val f Val f − 。证明：考虑 N ( f )中的任一个割 (, ) S S ，对 ∀ ∈ (,) (, ) uv SS ，要么 c uv f vu ′(,) (, ) = ；要么 c uv cuv f uv ′(,) (,) (,) = − 【见注 (1)】。令： {( , ) ( , ) | ( , ) ( , )} A1 =∈ = uv SS c uv f vu ′ ， {( , ) ( , ) | ( , ) ( , ) ( , )} A uv SS c uv cuv f uv 2 =∈ = − ′ 则 A A 1 2 ∩ = φ 且 ( ) A A Af 1 2 ∪ = 。故 (,)( , ) (, ) (,) uv SS Cap S S c u v ∈ ′ ′ = ∑ = (,) (,) (,) (,) 1 2 uv A uv A c uv c uv ∈ ∈ ∑ ∑ ′ ′ + (,) (,) ( , ) ( ( , ) ( , )) 1 2 uv A uv A f vu cuv f uv ∈ ∈ =+− ∑ ∑ (,) (,) (,) (, ) (, ) (, ) 21 2 uv A uv A uv A cuv f vu f uv ∈∈ ∈ =+ − ∑∑ ∑ = Cap S S ( , ） f () () S fS − + + − = − Cap S S Val f (, ) 。当 f 给定后 min ( , ) min ( , ) C ap S S Cap S S Val f ′ = − 。由最大流最小割定理， * * Val f Val f Val f = − . 其中 * f 表示 N f ( ) 中的最大流。二、网络顶点的分层：设网络 N = (V, x, y, A, C)，令： { | V vV i = ∈ x 到 v 的最短有向路的长为 i}。设 x 到 y 的最短有向路的长为 n，则 (1) , 0 n x ∈ ∈ V yV ；(2) V V i j ∩ = φ ，( ) j i ≠ 。Vi 中的顶点称为网络 N 的第 i 层顶点。注：这里有向路的长指有向路上有向边的数目。最短有向路指含有向边数最少的有向路。例： { }, { , }, { , , , } 0 1 12 2 3 4 5 V xV vv V v v v y = = = S S u v u v u v u v N N(f) 非零非饱和弧饱和弧零流弧非零非饱和弧 S S u v u v u v u v ∈A1 ∈A1 ∈A2 ∈A2 网络 N 网络 N 的分层。 v1 x y v3 v2 v4 v5 v1 x y v3 v2 v4 v5

点击进入文档下载页（PDF格式）

共20页，试读已结束，阅读完整版请下载

点击下载（PDF格式）

浏览记录