流网实例 1.例1:管道中的流体 第九讲 Maximum flow 2.例2:电网中的电流 极大流 3.例3:通信网络中的信息流 4.例4:装配线上的零件流 清华大学 宋斌恒 清华大学就件学院末恒 请华大学轼件学院宋斌恒 概念 12/12 11/16 15/20 1.有向边:传输物质的管道 2.容量:每条管道有静态容量:单位时间 101/4/7 内可以通过物质的最大数量,如每天可 以通过100万立方米的石油管道 8/13 3.点:管道连接点,满足流量守恒律 清华大学软件学院宋恒 請华大学轼件学院宋斌包 流网的定义 Kirchhoffs电流定律 1.流网G=(VE)是一个具有非负边权的有向图 边权c(uV)叫做容量,如果(uv)不属于E,我 1.流量守恒定律: 们约定其容量c(uv)=0 流入同一节点的总流量等于流出同一节点总 2.在流网上有两个特殊点源s和汇t 流量 2.对于电流就是 Kirchhoffs定律 3.对于每个点v,都有一条从s经过v到达t的路 3.极大流问题:计算流网中满足约束(上 述守恒律)的从源到汇的最大流量 南华大学软件学院宋就恒 请华大学狱件学院宋斌恒
1 清华大学 软件学院 宋斌恒 1 第九讲. Maximum Flow 极大流 清华大学 宋斌恒 清华大学 软件学院 宋斌恒 2 流网实例 1. 例1：管道中的流体 2. 例2：电网中的电流 3. 例3：通信网络中的信息流 4. 例4：装配线上的零件流 清华大学 软件学院 宋斌恒 3 概念 1. 有向边：传输物质的管道 2. 容量：每条管道有静态容量：单位时间 内可以通过物质的最大数量，如每天可 以通过100万立方米的石油管道 3. 点：管道连接点，满足流量守恒律 清华大学 软件学院 宋斌恒 4 1 3 2 4 s t 清华大学 软件学院 宋斌恒 5 Kirchhoff’s 电流定律 1.流量守恒定律： 1.流入同一节点的总流量等于流出同一节点总 流量 2.对于电流就是Kirchhoff’s 定律 3.极大流问题：计算流网中满足约束（上 述守恒律）的从源到汇的最大流量。 清华大学 软件学院 宋斌恒 6 流网的定义 1. 流网G=(V,E)是一个具有非负边权的有向图， 边权c(u,v)叫做容量，如果(u,v)不属于E，我 们约定其容量c(u,v)＝0。 2. 在流网上有两个特殊点源s和汇t。 3. 对于每个点v，都有一条从s经过v到达t的路 径
极大流问题 续 1.给定流网G=(VE)、流网上的容量c(uv),和源 s、汇t,求流使得其流值取得极大 4.流Flow:G上的一个流是一个实函数f: 2.相关概念扩充 V×V→R,它满足 1.容量约束:对所有u,v,f(u,v)≤cuy) 1.一个顶点v的总流入量:∑uev, fuvpofqu,v) 2.一个顶点v的总流出量:Euev, fly.upof(v,u) 2.反对称:对所有uw,f(uy)=-fv,u) 3.总净流量=总流出量一总流入量 3.流守恒:对所有u∈V-{st}∑vevf(uv)=0 4守恒律的另一种表述:在非源非汇点,总流出量 4.流的值:1=∑、evfv 总流入量 f(u,v)叫做从u到v的流,其值可正可负 清华大学就件学院末恒 请华大学轼件学院宋斌恒 多源多汇问题 多实际问题是多源 题【见下页图】,也就 是说流网中有多个源,有多个汇,这样的问题如何 16 解决? 灯单加的标灌题的徒多丁间题转 1.添加人工源s和人工汇t两个节点, 2.添加s到原问题所有源对应的顶点的有向边,并赋予 3.添加原问题所有汇对应顶点到t到有向边,并赋予∞ 4.于是原问题就变成了标准单源单汇问题。Why equivalent? 清华大学软件学院宋恒 (a)件学院来 流的运算 设f是流函数,X和Y是Ⅴ[G]的子集 定义:f(X,Y)=∑ 我们有 1.守恒律:对任意u属于V-{s,t有f(uV=0【如何 2. f(s, v-sFf( 3.fx,x)=0 4. f(X, Y-f(Y, X) 5.如果X∩Y=φ,我们有 清华大学 (6 2.t2,x+1zY=从学段宋玻如
2 清华大学 软件学院 宋斌恒 7 续 4. 流Flow：G上的一个流是一个实函数f： V×VÆR, 它满足 1. 容量约束：对所有u,v, f(u,v)≤c(u,v) 2. 反对称：对所有u,v, f(u,v)＝－f(v,u) 3. 流守恒：对所有u∈V-{s,t} ∑v∈Vf(u,v)=0 4. 流f的值：|f| = ∑v∈Vf(s,v) 5. f(u,v)叫做从u到v的流，其值可正可负 清华大学 软件学院 宋斌恒 8 极大流问题 1.给定流网G=(V,E)、流网上的容量c(u,v)，和源 s、汇t，求流f使得其流值取得极大 2.相关概念扩充 1.一个顶点v的总流入量： ∑u∈V，f(u,v)>0f(u,v) 2.一个顶点v的总流出量： ∑u∈V，f(v,u)>0f(v,u) 3.总净流量 ＝总流出量 －总流入量 4.守恒律的另一种表述：在非源非汇点，总流出量 ＝总流入量 清华大学 软件学院 宋斌恒 9 多源多汇问题 许多实际问题是多源多汇问题【见下页图】，也就 是说流网中有多个源，有多个汇，这样的问题如何 解决？ 我们通过添加人工源和汇的方法将多源多汇问题转 化为单源单汇的标准问题： 【见下下页图】 1. 添加人工源s和人工汇t两个节点， 2. 添加s到原问题所有源对应的顶点的有向边，并赋予 ∞权， 3. 添加原问题所有汇对应顶点到t到有向边，并赋予∞ 权， 4. 于是原问题就变成了标准单源单汇问题。Why equivalent？ 清华大学 软件学院 宋斌恒 10 s2 t1 t2 t3 s1 s3 s4 s5 清华大学 软件学院 宋斌恒 11 s2 t1 t2 t3 s1 s3 s4 s5 s t 清华大学 软件学院 宋斌恒 12 流的运算 设f是流函数，X和Y是V[G]的子集， 定义：f(X,Y)=∑x∈X, y∈Y f(x,y) 那么我们有： 1. 守恒律：对任意u属于V-{s,t}有 f(u,V)=0【如何 证？】 2. f(s,V-s)=f(s,V) 3. f(X,X)=0 4. f(X,Y)=-f(Y,X) 5. 如果X∩Y=φ，我们有： 1. f(X,Z)+f(Y,Z)=f(X ∪ Y, Z) 2. f(Z,X)+f(Z,Y)=f(Z,X ∪ Y)
流的值 Residual networks s Definition of residual networks aLet f be a flow in G. a residual network induce f(V, V-s by f is a flow network G =(V, ED, such that f(v, t)+f(V, V-S-t) Cdu,vc(u, vhf(u, v) f(V,t) (u, v)in Er is the residual 如果(u,v)和(v,u)都不属于E,利用定义证明 the residual capacity f(u, vFf(v, uFO 清华大学就件学院末恒 请华大学轼件学院宋斌恒 Compute a residual network from a flow network and a flow f 12/12 11/16 15/20 12/12 15/20 101/4/7 0/101/4 8/13 4/4 l/14 清华大学软件学院宋恒 請华大学轼件学院宋斌包 12/12 1/4 12/13 南华大学软件学院宋就恒 请华大学软件学院宋斌智
3 清华大学 软件学院 宋斌恒 13 流的值 |f| = f(s,V) = f(V,V)-f(V-s,V) = f(V,V-s) = f(V,t)+f(V,V-s-t) = f(V,t) 课堂练习： 如果(u,v)和(v,u)都不属于E，利用定义证明 f(u,v)=f(v,u)=0 清华大学 软件学院 宋斌恒 14 Residual networks Definition of residual networks Let f be a flow in G, a residual network induced by f is a flow network Gf =(V, Ef ), such that • Cf (u,v)=c(u,v)-f(u,v) • Ef ={(u,v): Cf (u,v)>0} We call (u,v) in Ef is the residual edge and Cf is the residual capacity 清华大学 软件学院 宋斌恒 15 Compute a residual network from a flow network and a flow f 1 3 2 4 s t 清华大学 软件学院 宋斌恒 16 1 3 2 4 s t 清华大学 软件学院 宋斌恒 17 1 3 2 4 s t 清华大学 软件学院 宋斌恒 18 1 3 2 4 s t
Lemma 26.2 s Let g=(v,E)be a flow network with source 113 sink t, and f be a flow in G. Let Gr be the residual network of g induced(诱导)by f Let f be a flow in g. then f+f is a fl in g with fIfI+IfI 清华大学就件学院末恒 请华大学轼件学院宋斌恒 Augmenting paths(增广路径) 素 Skew symmetry a Given a flow network G=(V,E)and a flow f s Capacity constrain an augmenting path p is a simple path from 成 Value of f+f s to t m Residual capacity of an augmenting path p cdu,v): (u, v) is on pi 清华大学软件学院宋恒 請华大学轼件学院宋斌包 low f, induced by p is a flow in g and its value ater than f sThe following function fp 什fHfF (p) If (u, v)is on p fp(u,v)=-c,(p)If(v, u)is onp 0 other wise 南华大学软件学院宋就恒 请华大学狱件学院宋斌恒
4 清华大学 软件学院 宋斌恒 19 1 3 2 4 s t 清华大学 软件学院 宋斌恒 20 Lemma 26.2 Let G=(V,E) be a flow network with source s and sink t, and f be a flow in G. Let Gf be the residual network of G induced(诱导) by f. Let f’ be a flow in Gf , then f+f’ is a flow in G with |f+f’|=|f|+|f’| 清华大学 软件学院 宋斌恒 21 Proof. Skew symmetry Capacity constrain Value of f+f’ 清华大学 软件学院 宋斌恒 22 Augmenting paths(增广路径) Given a flow network G=(V,E) and a flow f, an augmenting path p is a simple path from s to t. Residual capacity of an augmenting path p is given by cf (p)=min{cf (u,v): (u,v) is on p} 清华大学 软件学院 宋斌恒 23 Flow fp induced by p The following function fp: is a flow in Gf . other wise If (v,u) is on p If (u, v) is on p 0 ( ) ( ) ( , ) ⎪ ⎩ ⎪ ⎨ ⎧ = − c p c p f u v f f p 清华大学 软件学院 宋斌恒 24 f+fp is a flow in G and its value is greater than f. | f+fp |=| f |+| fp |>| f|
Cuts of flow networks Cut sA cut(S, T)divides the flow G=(E, V) into 1116 15/20 two parts S and T, where S nT=o, and S∪T=E,s∈S,t∈T 4 1/4 7/7 A Net flow across a cut(s, T) is defined to be f(s, T), the capacity of(S, T)is c(S, 票c(S,T=∑u∈sy∈rc(uv) 1I14 病f(S,D=∑u∈ Svet f(uv) 清华大学就件学院末恒 请华大学轼件学院宋斌恒 Lemma 26.5 Corollary 26.6 素f(S,T= f(S,D≤c(S,T af(S,T)=f(S,v)r-f(s, S) s Notes the definition of f and c f(s,V f(s, V)+(S-S,V) 清华大学软件学院宋恒 請华大学轼件学院宋斌包 Theorem 26.7(Max-flow min-cut 赛 Proof M1)e(2): If there exists an augmenting path p in theorem) the residual network G, then there is a induced sIf f is a flow in a flow network G=(V, E) flow f on g. hence there exists another flow f+f source s and sink t, then the following on G such that its flow is bigger than f, which is a conditions are equivalent 2(2)2(3): Because Gr contains no augmenting path, 1.f is a maximum flow in g hence there are no path from s to t in ge. Let 2.The residual network Gr contains no 3.fFc(S, T) for some cut(S, T)of G >Then the partition(S,T)is a cut, 南华大学软件学院宋就恒 请华大学狱件学院宋斌恒 5
5 清华大学 软件学院 宋斌恒 25 Cuts of flow networks ÅS TÆ 1 2 3 4 s t 清华大学 软件学院 宋斌恒 26 Cut A cut (S,T) divides the flow G=(E,V) into two parts S and T, where S ∩T=φ, and S∪T=E, s∈S, t∈T. Net flow across a cut (S,T) is defined to be f(S,T), the capacity of (S,T) is c(S,T) c(S,T)=∑u ∈S,v ∈Tc(u,v) f(S,T)=∑u ∈S,v ∈T f(u,v) 清华大学 软件学院 宋斌恒 27 Lemma 26.5 f(S,T)=|f| Proof: f(S,T) = f(S,V)-f(S,S) = f(S,V) = f(s,V)+f(S-s,V) = f(s,V) = |f| 清华大学 软件学院 宋斌恒 28 Corollary 26.6 f(S,T)≤c(S,T) Notes: the definition of f and c. 清华大学 软件学院 宋斌恒 29 Theorem 26.7(Max-flow min-cut theorem) If f is a flow in a flow network G=(V,E) with source s and sink t, then the following conditions are equivalent: 1.f is a maximum flow in G 2.The residual network Gf contains no augmenting paths 3.|f|=c(S,T) for some cut (S,T) of G 清华大学 软件学院 宋斌恒 30 Proof: (1)Î(2): If there exists an augmenting path p in the residual network Gf , then there is a induced flow fp on Gf , hence there exists another flow f+fp on G such that its flow is bigger than f, which is a contradiction that f is a maximum flow on G. (2)Î(3): Because Gf contains no augmenting path, hence there are no path from s to t in Gf . Let • S={v∈V: there exists a path from s to v in Gf } • T=V-S Then the partition (S,T) is a cut