清华大学就件学院末恒 请华大学轼件学院宋斌恒 Edmonds-Karp algorithm Proof of x-O(EV) in Edmonds- Karp algorithm s If we use the bfs as the method to find an a Stepl: for all vertices v in V-is, t), the augmenting path, then such an shortest-path distance 8(s, v)in th implementing of Ford-Fulkerson Method residual network Gr increases call Edmonds-Karp algorithm monotonically with each flow sThe kernel of Edmonds-Karp algorithm is augmentation.【残网距离递增】 that it can prove that 清华大学软件学院宋恒 請华大学轼件学院宋斌包 续 Proof of stepl( Lemma 26.8) s Suppose that there exists a flow f, a next <Step2: Every edge can become critical at augmented flow f and a vertex v'in V-is, t) I times: here above critical edge not satisfies the property mentioned in stepl means it is in an augmenting path and its that is 8(s, v)<8(s, v)does not hold value equals the capacity of the path.【边为 s then we choose y be one of such elements 关键边个数有限】 which takes the minimum distance from s in s By step2, in Edmonds-Karp algorithm, it G,【f的残网】 will complete in(vp2-1)*E steps of 【蓝字什么意思?为什么能这样假设?】 augmentation 华大学软件字院宋 请华大学狱件学院宋斌恒 88 清华大学 软件学院 宋斌恒 43 u v s t 清华大学 软件学院 宋斌恒 44 u v s t 清华大学 软件学院 宋斌恒 45 Edmonds-Karp algorithm If we use the BFS as the method to find an augmenting path, then such an implementing of Ford-Fulkerson Method call Edmonds-Karp algorithm. The kernel of Edmonds-Karp algorithm is that it can prove that x=O(EV) 清华大学 软件学院 宋斌恒 46 Proof of x=O(EV) in Edmonds￾Karp algorithm Step1: for all vertices v in V-{s,t}, the shortest-path distance δf (s,v) in the residual network Gf increases monotonically with each flow augmentation.【残网距离递增】 清华大学 软件学院 宋斌恒 47 续 Step2: Every edge can become critical at most |V|/2-1 times; here above critical edge means it is in an augmenting path and its value equals the capacity of the path.【边为 关键边个数有限】 By step2, in Edmonds-Karp algorithm, it will complete in (|V|/2-1)*E steps of augmentations. 清华大学 软件学院 宋斌恒 48 Proof of step1(Lemma 26.8) Suppose that there exists a flow f, a next augmented flow f’ and a vertex v’ in V-{s,t} not satisfies the property mentioned in step1, that is δf (s,v’)≤ δf’(s,v’) does not hold, then we choose v be one of such elements which takes the minimum distance from s in Gf’ 【f’的残网】 【蓝字什么意思？为什么能这样假设？】