第九章网络流理论 流 什么是流? 流就是永恒。 当生命停止,呼吸不再, 流,并未结束。 因为一个生命的终止是另一个生命的开始, 因为地球仍在运转, 太阳还在发光, 时间还在奔流。 个体的生命有限, 宇宙的生命无穷 流 与时光共存, 和无限相伴。 流是风,流是雨, 流是奔腾的江河, 流是起伏的山川。 流是婀娜的小草, 在微风中摇曳。 流是我缥缈的思绪, 在缥缈的地方遨游
第九章 网络流理论 流 什么是流？ 流就是永恒。 当生命停止，呼吸不再， 流，并未结束。 因为一个生命的终止是另一个生命的开始， 因为地球仍在运转， 太阳还在发光， 时间还在奔流。 个体的生命有限， 宇宙的生命无穷， 流， 与时光共存， 和无限相伴。 流是风，流是雨， 流是奔腾的江河， 流是起伏的山川。 流是婀娜的小草， 在微风中摇曳。 流是我缥缈的思绪， 在缥缈的地方遨游
§91网络与网络流的基本概念 定义9.1.1一个网络N=(V,A)是指一个连通无环弧且满足下列条件的有向图 (1)有一个顶点子集X,其每个顶点的入度都为0 (2)有一个与Ⅹ不相交的顶点子集Y,其每个顶点的出度都为0 (3)每条弧都有一个非负的权,称为弧的容量。 注:上述网络N可写作N=(V,X,Y,A,C),X称为网络的发点集或源点集,Y称为网络的 收点集或汇点集,C称为网络的容量函数。 例 14|3 定义9.2网络N=(V,X,Y,A,C中的一个(可行)流是指定义在A上的一个整值函数/, 使得: (1)对va∈A,0≤f(a)≤c(a),(容量约束) (2)对vv∈V-(X∪Y),∫(v)=f(v),(流量守恒) 其中∫(ν)表示点ν处入弧上的流量之和,∫(v)表示点v处出弧上的流量之和 注:(1)可行流总是存在的,比如∫≡0。 (2)现实问题中有许多关于网络和流的实例。 比如:产销物资输送网络;输油管线网络;通信数据传输网络等。 定义9.3设∫是网络N=(VX,Y,A,C)中的一个可行流,则必有∫+(X)=f()。 ∫(X)(或∫(Y)称为流∫的流量,记为alf。 网络最大流问题:给定网络N=(V,X,Y,A,C,求N中流量最大的可行流(称为最大流) 注:如果一个网络中的源点集和汇点集都只含一个顶点,则称该网络为单源单汇网络。任 一网络N=(VX,Y,A,C)都可导出一个单源单汇网络。方法如下: (1)给N添加两个新顶点s和t; (2)对x∈x,从s向x连一条弧,其容量为∞(或∑c(s) (3)对vy∈y,从y向t连一条弧,其容量为∞(或∑c(u1)。 新添的顶点s和t分别称为人工源和人工汇,所得的新网络为NW',s,t,A,C)
§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.14设N=(V,x,yAC)是一个单源单汇网络。SV,S=V-S。用(S,S)表示尾 在S中而头在§中的所有弧的集合(即从S中的点指向S之外点的所有弧之集)。若x∈S, 而y∈S,则称弧集(S,S)为网络N的一个割。一个割(S,S)的容量是指(S,S)中各条弧的 容量之和,记为Cap(S,S)。 例:对网络 4 令S={x,n1,"2,"3,"s},则割(S,S)={4,V,4,v3}。 注:一个网络N可能有多个割,各个割的容量不一定相等。其中容量最小的割称为N的 最小割 引理911对网络N中任一流∫和任一割(S,S),均有 al∫=∫(S)-f(S) 证明:设∫是网络N=(V,x,y,A,C)中的流,(S,S)是N的一个割,由流的定义, f(x)=lal∫,f(x)=0,f(v)-f(v)=0,(vv∈-{x})。 故 af=∫(x)-f(x)+∑[()-f()=∑()-f() VES-Ix! =∑Cf(,)-∑f(u)=∑∑f(v,u)-∑∑fan,) v∈S r∈Su veS I ∑∑∫(,)+∑∑f(v,u)-∑∑f(a)-∑∑f(u) VES HES v∈SweS v∈SeS r∈SgS 上式中第一式和第三式都表示S内部弧上流量之和,故相等;第二式表示从S的顶点指向 S之外点的所有弧上流量之和,因此它等于∫(S);第四式表示从S之外的顶点指向S中 点的所有弧上的流量之和,因此等于f(S)。从而anlf=f(S)-f(S)。证毕。 定义91.5.对弧a,若f(a)=0,则称a是∫零的 若∫(a)>0,则称a是f正的; 若f(a)=c(a),则称a是∫饱和的; 若f(a)<c(a,则称a是∫非饱和的
此后的讨论中主要考虑单源单汇网络。 定义 9.1.4 设 N=(V, x, y, A, C)是一个单源单汇网络。S V ⊆ ，SVS = − 。用(, ) S S 表示尾 在 S 中而头在S 中的所有弧的集合(即从 S 中的点指向 S 之外点的所有弧之集)。若 x ∈ S ， 而 y ∈ S ，则称弧集(, ) S S 为网络 N 的一个割。一个割(, ) S S 的容量是指(, ) S S 中各条弧的 容量之和，记为 Cap (, ) S S 。 例：对网络 令 1235 S xv v v v = {, , , , }，则割(, ) S S 14 34 54 56 = {, , , } vv vv vv vv 。 注：一个网络 N 可能有多个割，各个割的容量不一定相等。其中容量最小的割称为 N 的 最小割。 引理 9.1.1 对网络 N 中任一流 f 和任一割(, ) S S ，均有 Val f f S f S () () + − = − . 证明：设 f 是网络 N=(V, x, y, A, C)中的流，(, ) S S 是 N 的一个割，由流的定义， f ( ) , ( ) 0, ( ) ( ) 0, ( { }) x Val f f x f v f v v S x + − +− = = − = ∀∈ − 。 故 { } ( ) ( ) [ ( ) ( )] [ ( ) ( )] [ ( , ) ( , )] ( , ) ( , ) ( , ) ( , ) ( , ) ( , ). vS x vS vS u u vS u vS u v Su S v Su S v Su S v Su S Val f f x f x f v f v f v f v f vu f uv f vu f uv f vu f vu f uv f uv + − +− +− ∈− ∈ ∈ ∈∈ ∈∈ ∈∉ ∈∈ ∈∉ =−+ − = − = −= − =+−− ∑ ∑ ∑ ∑ ∑ ∑∑ ∑∑ ∑∑ ∑∑ ∑∑ ∑∑ 上式中第一式和第三式都表示 S 内部弧上流量之和，故相等；第二式表示从 S 的顶点指向 S 之外点的所有弧上流量之和，因此它等于 f ( ) S + ；第四式表示从 S 之外的顶点指向 S 中 点的所有弧上的流量之和，因此等于 f ( ) S − 。从而Val f f S f S () () + − = − 。 证毕。 定义 9.1.5. 对弧 a，若 f a() 0 = ，则称 a 是 f 零的； 若 f a() 0 > ，则称 a 是 f 正的； 若 f () () a ca = ，则称 a 是 f 饱和的； 若 f () () a ca < ，则称 a 是 f 非饱和的。 v1 v4 v7 v3 v6 v5 v8 4 1 3 3 1 2 4 3 2 3 2 2 2 2 5 6 5 5 x y v2
定理9.LJ.对冈络N中任一可行流f和任一割K=(S,S),均有valf≤Cφpk。其中等式成 立当且仅当(S,S)中每条弧都是f饱和的而且(S,S)中每条弧都是∫零的 证明:因∫是可行流,故 f(S)=∑f(a)≤∑c(a)=CapK,并且f(S)=∑f(a)≥0。 由引理9.1.1,alf=f(S)-f(S)≤CqpK,可见第 个结论成立。另外注意到∫(S)=CpK当且仅当 (S,S)中每条弧都是∫饱和的;而∫(S)=0当且仅当 K (S,S)中每条弧都是∫零的,故定理的第二个结论也成立。证毕。 注:网络N的一个割K称为最小割,如果网络N中不存在割K使得CφpK'< Capk。 推论91设∫是网络N的一个最大流,K是N的一个最小割,则alf≤CqpK 证明显然。 推论912设∫是N的一个可行流,K是N的一个割,若alf=Cqpk,则∫是最大流而 K是最小割 证明:由推论91.1,alf≤alf≤CapK'≤CqpK,因alf=CqpK,故由上式知, Val=val, Capk=CapK 证毕
定理 9.1.1. 对网络 N 中任一可行流 f 和任一割 K=(, ) S S ，均有Val f CapK ≤ 。其中等式成 立当且仅当(, ) S S 中每条弧都是 f 饱和的而且(, ) S S 中每条弧都是 f 零的。 证明：因 f 是可行流，故 () () () aK aK f S f a c a CapK + ∈ ∈ = ≤= ∑ ∑ ，并且 (,) () () 0 a SS f S fa − ∈ = ∑ ≥ 。 由引理 9.1.1, ( ) ( ) Val f f S f S CapK + − =−≤ , 可见第 一个结论成立。另外注意到 f ( ) S CapK + = 当且仅当 (, ) S S 中每条弧都是 f 饱和的；而 f S() 0 − = 当且仅当 (, ) S S 中每条弧都是 f 零的，故定理的第二个结论也成立。证毕。 注：网络 N 的一个割 K 称为最小割，如果网络 N 中不存在割 K′使得CapK CapK ′ < 。 推论 9.1.1 设 * f 是网络 N 的一个最大流，K* 是 N 的一个最小割，则 * * Val f CapK ≤ . 证明显然。 推论 9.1.2 设 f 是 N 的一个可行流，K 是 N 的一个割，若Val f CapK = ，则 f 是最大流而 K 是最小割。 证明：由推论 9.1.1， * * Val f Val f CapK CapK ≤≤ ≤ ，因Val f CapK = ，故由上式知， * Val f Val f = ， * CapK CapK = 。 证毕。 S S K
§92最大流最小割定理及求最大流的标号算法 最大流最小割定理 题:给定网络N=(V,x,y,AC),如何求N中的最大流 定义921设P=xV1…vky是网络N=(V,x,y,AC)中一条xy路(无向),若弧(v,v)∈A,则称 此弧为路P的一条正向弧(或称前向弧,顺向弧),若弧(v1,V)∈A,则称此弧为路P的一条反向弧 (或称后向弧,逆向弧) 例如:在右图所示的路P上,所有弧都是正向弧 yvo 在路Q上,弧(v1,n2)和(v2,v6)是正向弧,而(v2,V4)和 (v4,v3)是反向弧。可见,一条弧是正向弧还是反向弧 与路有关。 定义9.22设∫是网络N=(V,x,y,A,C)中的一可行流,P是N中一条x-y路。如果对于P上任一条弧 a,都有 (1)若弧a是P的正向弧,则4(a)c(a)-f(a)>0; (2)若弧a是P的反向弧,则(a)f(a)>0 则称P是流∫的一条可增路。沿路P可增加的流量为Δ(P)=minΔ∫(a),称为路P上流的增量或可 增量。 例如:在下图中,每条弧上括号内的数字表示弧的容量,括号外的数字是当前流的流量。图(1)中虚 线所示的路P是一条可增路。因(v1,v3)=6-1=5,4(v3,v4)=2,4(v4,V2)=5 f(V2,v6)=4-0=4,故路P上的可增量A(P)=min{5,2,5,4}=2。沿P增流后的流网络如图(2) 所示。 4 (x) 2(3) (3) 图(1) 由此可见,如果能找到N中一条∫可增路,则可沿着P修改流的值,得到一个流值更大的新流∫,修 改办法如下: f(a)+4(P,若a是P的正向弧 f(a={f(a)-4(P,若a是P的反向弧 a不在P上 修改后的流值为:Ialf=lalf+△(P)。 这给出了求网络N的最大流的一个途径:反复找N中的可增路,沿可增路将流量扩大,直到找不 出可增路为止。直观上想,此时应该已达到最大流。下面的定理证实了这一点
§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
定理9.21N(V,x,y,A,C)中的流∫是N的最大流当且仅当N中不存在∫可增路。 证明::必要性:若N有∫可増路,则∫不是最大流,因为沿P按(*)式修改流可得流值更大的流∫。 充分性:设N中不存在∫可增路,我们来证明∫是最大流。令 S={v∈|从源x到v有可增路}∪{x} 则ygS,而x∈S,从而K=(S,S)是N中的一个割见割定义)。 对(S,S)中的任一条弧a=(u,v),必定∫(a)=c(a),(否则,若f(a)f(,v),则给v标号 (v)=min{a)2(u2y)-f(uy)},[称为已标未查顶点] 否则,不给ν标号。 (2)对u的尚未标号的入邻点v(即(v,u)∈A),若f(v,u)>0,则将v标号 l(v)=min{(af(v,a)},[称为已标未查顶点] 否则,不给ν标号
定理 9.2.1 NV x y AC (,,,, )中的流 f 是 N 的最大流当且仅当 N 中不存在 f 可增路。 证明：：必要性：若 N 有 f 可增路，则 f 不是最大流，因为沿 P 按(*)式修改流可得流值更大的流 ˆ f 。 充分性：设 N 中不存在 f 可增路，我们来证明 f 是最大流。令 S vV = ∈ { |从源 x 到 v 有可增路} {} ∪ x ， 则 y ∉ S ，而 x ∈ S ，从而 K SS = (, )是 N 中的一个割(见割定义)。 对 (, ) S S 中的任一条弧 a uv = (,) ，必定 f () () a ca = ，(否则，若 f () () a ca ，则给 v 标号： lv lu cuv f uv ( ) min ( ), ( , ) ( , ) = − { }，[v 称为已标未查顶点]； 否则，不给 v 标号。 (2) 对 u 的尚未标号的入邻点 v (即( ) v,u A ∈ )，若 f vu (, ) 0 > ，则将 v 标号： lv lu f vu ( ) min ( ), ( , ) = { }，[v 称为已标未查顶点]； 否则，不给 v 标号
当检查完u的所有邻点之后,u称为已标已查顶点。 反复进行上述标、查过程,最终必出现两种结果之 ()汇点y获得标号,此时已得到∫可增路。沿该路增流。 (i)y点未获得标号,但已没有已标未查顶点(所有已标顶点都已被查,没有更多的新标号顶点) 此时当前的流∫即为最大流[设当前已标已查的顶点之集为S,则(S,S)为最小割 例如:网络M(V,x,y,A,O及其上一个流f,(括号内数字是弧容量)。 35(9) v15(9) 0(5) 0(2)k6为y2c 2379)v2 情况():获得一条∫可增路 情况(i):已得到最大流和最小割 求网络最大流的Ford- Fulkerson标号算法 输入:网络N(V,x,y,A,C) 输出:网络N中一个最大流。 第0步(初始化):对a∈A,令∫(a)=0 第1步:给源点x标号(x,∞)。L:={x},S=Φ。其中L表示已标未査集,S表示已标已查集 第2步:任取l∈L,检查u的每个尚未标号的邻点v (1)若v∈N'(u),w尚未标号且C(u,yv)>f(u,v),则给v标号(u,+,l(v),其中 l(v)=min{(au),C(l,y)-f(l,v)}。令L:=LU{v}。 (2)若v∈N(a),ν尚未标号且f(v,u)>0,则给ν标号(u,-,l(v),其中 l(v)=min{(au),f(v,u)}。令L:=LU{v}。 第3步:重复第2步,直到汇点y被标号,或y未被标号但L=Φ为止。 若是后者,算法结束,当前流是最大流 若是前者,转下步。 2 第5步:若〓的标号为(w,+,l(=),则令f(W,=)=f(,)+l(y) 若的标号为(V,-,l(二=),则令∫(=,w)=f(二,w)-l(y) 注:不论二是哪个点,此处总是l(y),因1⑦)是最大的可增量(沿可增路)。 第6步:若W≠x,则令x=w,转第5步; 否则,去掉所有的顶点标号,转第1步
当检查完 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(5) 增流 O(8 0(2) +,7) +5 0(10) 2(x,+7)09)v4(2+,7 2n+,5)7(9)n4 (x,+,1) 增流 增流 7(10) 9(10) v2(n+,3)7(9)v4(2+,2) v2,+,1)9(9)v4 定理9.2.2标号算法结束时所得的流是最大流 证明:算法结束时,L=Φ,所有已标顶点都已查,S是所有已标已查顶点的集合。S≠Φ(因 y∈S)。按照标号规则,对va∈(S,S),f(a)=C(a);对va∈(S,S),f(a)=0,(否则可得到新的 标号顶点,算法不会终止)。从而 val f f(a) f(a) f(a) C(a)=Cap(s,S) 由推论9.1,2,∫是最大流,而(S,S)是最小割。证毕 、 Emends-Karp修改标号法: Ford- Fulkerson标号法的缺陷 (1)当弧容量为无理数时,可以构造出例子说明算法不能在有限步终止 见 C H. Papadimitry等著,《 Combinatorial Optimization- Algorithms& Complexity》s63 或谢政著,《网络算法与复杂性理论》,国防科技大学出版社,2003年。 (2)即使弧容量都是有理数或整数,标号算法也不是一个有效算法。 例 可见,标号算法的计算量并不完全依赖于问题的规模v和E,还依赖于容量函数。它不是多项式时 间算法
例： 定理 9.2.2 标号算法结束时所得的流是最大流。 证明：算法结束时， L = Φ ，所有已标顶点都已查，S 是所有已标已查顶点的集合。 S ≠ Φ (因 y ∈ S )。 按照标号规则，对∀∈ = a SS f a Ca ( , ), ( ) ( ) ；对∀a SS fa ∈ = ( , ), ( ) 0 ，(否则可得到新的 标号顶点，算法不会终止)。从而 (,) (,) (,) (,) () () () () (, ) a SS a SS a SS a SS Val f f a f a f a C a Cap S S ∈∈ ∈ ∈ =−=== ∑∑∑∑ 由推论 9.1.2，f 是最大流，而(, ) S S 是最小割。证毕。 三、Edmends－Karp 修改标号法： Ford－Fulkerson 标号法的缺陷： (1) 当弧容量为无理数时，可以构造出例子说明算法不能在有限步终止。 见 C.H.Papadimitry 等著，《Combinatorial Optimization－Algorithms & Complexity》§6.3， 或谢政著，《网络算法与复杂性理论》，国防科技大学出版社，2003 年。 (2) 即使弧容量都是有理数或整数，标号算法也不是一个有效算法。 例： 可见，标号算法的计算量并不完全依赖于问题的规模ν 和ε ，还依赖于容量函数。它不是多项式时 间算法。 v4 v1 v5 v3 x y v2 v6 m m m m m m m m 1 v4 v1 v3 x y v2 0(7) 0(9) 0(8) 0(5) 0(9) 0(2) 0(6) 0(10) 0(5) (x,+,7) (v2,+,7) (x,+,8) (x,+,∞) (v4,+,7) (v1,+,8) v4 v1 v3 x y v2 7(7) 7(9) 0(8) 0(5) 0(9) 0(2) 0(6) 7(10) 0(5) (v1,+,5) (x,+,8) (x,+,∞) (v3,+,5) (v1,+,8) 增流 v4 v1 v3 x y v2 7(7) 7(9) 5(8) 0(5) 5(9) 0(2) 0(6) 7(10) 5(5) (v1,+,3) (v2,+,2) (x,+,3) (x,+,∞) (v4,+,2) (v1,+,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) (v1,+,1) (x,+,1) (x,+,∞) (v1,+,1) 增流 增流
Emends-Karp修改标号法: 在Ford- Fulkerson标号算法的第2步检查已标顶点时,采用“先标先查”规则。 例 1000Y31000 1000 v21000v4100016 ①先标先查规则,相当于执行广探法 ②先标先査规则执行的结果相当于求x到y的最短可增路(层层推进策略) ③ Emends-Kap修改标号法是有效算法弧容量是有理数时),其计算复杂性为O(vE2) §93求最大流的 Dinic算法 增量网络 定义9.3.1对于网络N=(V,x,y,A,C)和N上的一个可行流f,构造一个新的网络N(f=(V,x,y,A(f C),其中A(f)及容量函数C定义如下 (1)若(,v)∈A且f(u,v)0,则(v,a)∈A(∫),且C'(v,a)=f(l,v) 这样构造的网络N(∫称为网络N关于流∫的增量网络。 例: 2(3) 网络N及其一个可行流∫,弧上括号 增量网络N 外数字为流量,括号内数字为容量。 注 (1)对应于N的每条饱和弧(,v),N(O中只有一条弧(v,4),c(v,u)=c(l,v)=f(l,v); 对应于N的每条零流弧(,v),N()中只有一条弧(u,y),c(u,v)=c(,v)=c(u,v)-f(u,v) 对应于N的每条非零流非饱和弧(u,v),N(f)中有两条弧(u,v)和(v,u),c(l,v)=c(u,v)-f(,v) c(v, u)=f(u, v) (2)N()中每条弧的容量恰为N中相应弧的流可增量。 (3)严格来讲,增量网络不符合前述网络的定义(无出度为0的点(源)和入度为0的点(汇),但因它是在 原网络N基础上定义的,有明显的源和汇的痕迹,因此我们仍将其看作网络,其中x和y分别为源和 汇,该网络上的一个可行流∫定义为满足
Edmends－Karp 修改标号法： 在 Ford－Fulkerson 标号算法的第 2 步检查已标顶点时，采用“先标先查”规则。 例： 注： ① 先标先查规则，相当于执行广探法； ② 先标先查规则执行的结果相当于求 x 到 y 的最短可增路(层层推进策略)； ③ Edmends－Karp 修改标号法是有效算法(弧容量是有理数时)，其计算复杂性为 2 O( ) ν ⋅ε 。 §9.3 求最大流的 Dinic 算法 一、增量网络 定义 9.3.1 对于网络 N = (V, x, y, A, C)和 N 上的一个可行流 f，构造一个新的网络 N ( f )= (V, x, y, A( f ), C′ )，其中 A( f )及容量函数 C′ 定义如下： (1) 若( ) u,v A ∈ 且 f (,) (,) uv Cuv ，则(, ) ( ) vu A f ∈ ，且C vu f uv ′(, ) (, ) = 。 这样构造的网络 N ( f )称为网络 N 关于流 f 的增量网络。 例： 注： (1) 对应于 N 的每条饱和弧(u, v)，N ( f )中只有一条弧(v, u)，c vu cuv f uv ′(, ) (, ) (, ) = = ； 对应于 N 的每条零流弧(u, v)，N ( f )中只有一条弧(u, v)， c uv cuv cuv f uv ′(,) (,) (,) (,) = = − ； 对应于 N 的每条非零流非饱和弧(u, v)，N ( f )中有两条弧(u, v)和(v, u), c uv cuv f uv ′(,) (,) (,) = − , c vu f uv ′(, ) (, ) = 。 (2) N ( f )中每条弧的容量恰为 N 中相应弧的流可增量。 (3) 严格来讲，增量网络不符合前述网络的定义(无出度为 0 的点(源)和入度为 0 的点(汇))，但因它是在 原网络 N 基础上定义的，有明显的源和汇的痕迹，因此我们仍将其看作网络，其中 x 和 y 分别为源和 汇，该网络上的一个可行流 f 定义为满足 网络 N 及其一个可行流 f ，弧上括号 外数字为流量，括号内数字为容量。 2(2) 1(2) 2(3) 0(1) 2(3) 0(2) 1(3) x y 增量网络 N(f)。 2 1 1 1 1 2 2 x y 1 1 2 2 v3 v2 v4 v1 1000 1000 1000 1000 v5 x y v6 1000 1000 1000 1000 1
f∫(x)-f-(x)≥0 f(y)=f+(y)-f(y)≤0 f(u)=f(a)-f(l)=0 的流 定理93.1设∫是网络N中的一个可行流。则 (1)N中∫可增路与N()中的x-y有向路一一对应。 (2)N中∫可增路P的可增流值4(P)等于N()中对应的x-y有向路P上最小的弧容量 证明:显然 定理93.2设∫”是网络N中的最大流,厂是N中的一个可行流,则增量网络N(f)中的最大流的流值为 lalf-alf。 证明:考虑N(∫)中的任一个割(S,S),对V(l,v)∈(S,S),要么c(l,v)=∫(V,l);要么 v)=c(l,v)-f(u,v)【见注(1)】 令:A1={(l,v)∈(S,S)lc(u,v)=f(v,)}, 4=(05100(::)(:: 非零非饱和弧 则A1∩A2=p且A1UA2=A( 零流弧 (n)=∑c(nv)+∑c(n,) N N ∑f(,n)+∑(c(nr)-f(2) ∑c(un)+∑f(v,)-∑f(u,") S, S)+f(S)-f(S)=Cap(S, S)-Valf 当∫给定后 min Cap(S,S)= min Cap(S,S)-alf。由最大流最小割定理,alf”=lal∫”-half 其中广”表示N()中的最大流 二、网络顶点的分层 设网络N=(,x,y,A,C,令:V={∈Vkx到v的最短有向路的长为l}。设x到y的最短有向路 的长为n,则(1)x∈l0,y∈Vn;(2)V1∩V=,(≠)。H中的顶点称为网络N的第层顶点 注:这里有向路的长指有向路上有向边的数目。最短有向路指含有向边数最少的有向路 例 网络N 网络N的分层 V={x},V={v1,v2},F2={v
() () () 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
