续 续 s We claim(u, v)not in Et 6s,V)>8(,V) >m If it is, then a Gr, So that(u,v)in Er andh froms to v et p=s-->u>v be a shortest 8(s, v)8(s, u)+1(triangle inequality) 6-(S,u)=6(SV1【三角不定式】and ≤6(s,u)+l( see above,递增假设成 61(s,u)≥8(s,u),【假设,】 ≤8(V) 清华大学就件学院末恒 请华大学轼件学院宋斌恒 续 续 How can we have(u, v) not in E but in Er? sIt is impossible! If it is true, then the ≤64(S,u}1【假设】 augmentation must increased the flow from ≤64(SV2【三角不等式】 v to u. By the Edmonds-Karp algorithm ≤8(SV) always augment flow along the shortest Contradicts to paths, and the shortest path from s to u in Ge 8(s,V)<8s,v) has(v, u)as its last edge. Therefore Conclusion: The assumption is incorrect. 清华大学软件学院宋恒 請华大学轼件学院宋斌包 Proof of step2: (Theorem 26.9) Maximum Bipartite Matching The critical time for an edge cannot exceed 匹配的概念: Ny2-1 Given an undirected graph G=(V,E), a matching If(u, v) al at flow f and is not critical until to the flow f. then we have is a subset m of edges in e such that for all vertices v in v. at most one edge of m is 8(su)=8(sV)+1【临界假设】 ≥8(sV+1【递增性质】 incident on v. If one edge is incident onv, we 6s,u)+2【临界假设】 say v is matched by matching M, otherwise we Because the distance must be less than /VIl,we say v is unmatched have the critical time should be less than v2-1 kimm matching is a ma such that it the maximum cardinali 南华大学软件学院宋就恒 请华大学狱件学院宋斌恒9 清华大学 软件学院 宋斌恒 49 续 即 δf (s,v)＞ δf’(s,v) Let p=s--->uÆv be a shortest path from s to v in Gf’ , so that (u,v) in Ef’ and δf’(s,u)＝δf’(s,v)-1 【三角不定式】and δf’(s,u)≥ δf (s,u), 【假设，】 清华大学 软件学院 宋斌恒 50 We claim (u,v) not in Ef . If it is, then δf (s,v)≤ δf (s,u)+1 (triangle inequality) ≤ δf’(s,u)+1 (see above，递增假设成立) ≤ δf’(s,v) A contradiction! 续 清华大学 软件学院 宋斌恒 51 续 How can we have (u,v) not in Ef but in Ef’? It is impossible! If it is true, then the augmentation must increased the flow from v to u. By the Edmonds-Karp algorithm always augment flow along the shortest paths, and the shortest path from s to u in Gf has (v,u) as its last edge. Therefore, 清华大学 软件学院 宋斌恒 52 δf (s,v)= δf (s,u)-1 ≤ δf’(s,u)-1 【假设】 ≤ δf’(s,v)-2 【三角不等式】 ≤ δf’(s,v) Contradicts to δf’(s,v) < δf (s,v) Conclusion: The assumption is incorrect. 续 清华大学 软件学院 宋斌恒 53 Proof of step2: (Theorem 26.9) The critical time for an edge cannot exceed |V|/2-1. If (u,v) is critical at flow f and is not critical until to the flow f’, then we have δf’(s,u) = δf’(s,v)+1【临界假设】 ≥ δf (s,v)+1【递增性质】 = δf (s,u)+2【临界假设】 Because the distance must be less than |V|-1, we have the critical time should be less than |V|/2-1. 清华大学 软件学院 宋斌恒 54 Maximum Bipartite Matching 匹配的概念: Given an undirected graph G=(V,E), a matching is a subset M of edges in E such that for all vertices v in V, at most one edge of M is incident on v. If one edge is incident on v, we say v is matched by matching M, otherwise we say v is unmatched. A maximum matching is a matching such that it takes the maximum cardinality