极大流问题 续 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)