流的值 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