第九章网络流理论 流 什么是流? 流就是永恒。 当生命停止,呼吸不再, 流,并未结束。 因为一个生命的终止是另一个生命的开始, 因为地球仍在运转, 太阳还在发光, 时间还在奔流。 个体的生命有限, 宇宙的生命无穷 流 与时光共存, 和无限相伴。 流是风,流是雨, 流是奔腾的江河, 流是起伏的山川。 流是婀娜的小草, 在微风中摇曳。 流是我缥缈的思绪, 在缥缈的地方遨游
第九章 网络流理论 流 什么是流？ 流就是永恒。 当生命停止，呼吸不再， 流，并未结束。 因为一个生命的终止是另一个生命的开始， 因为地球仍在运转， 太阳还在发光， 时间还在奔流。 个体的生命有限， 宇宙的生命无穷， 流， 与时光共存， 和无限相伴。 流是风，流是雨， 流是奔腾的江河， 流是起伏的山川。 流是婀娜的小草， 在微风中摇曳。 流是我缥缈的思绪， 在缥缈的地方遨游
§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