Bipartite grap 举例说明 a bipartite graph is a graph can be 赢二分图实例 ertices into two parts L and r, L and r are disjoined and all edges go between 清华大学就件学院末恒 请华大学轼件学院宋斌恒 Finding the maximum matching Convert the maximum-bipartite in a bipartite graph atching problem to a maximum flow problem s Application of the matching problem lf L is set of machines R is a set of tasks the means that the machine can do the task ing the maximum simultaneously erforming tasks 清华大学软件学院宋恒 請华大学轼件学院宋斌包 利用流求二分图的正确性 总结: 燕如何保证最后的最大流对应的边构成 燕流的定义和属性 个匹配 最大流与分割 Ford- Fulkerson算法如何保证流是整 残余流与增广路 血Ford- Fulkerson方法 端Ford- Fulkerson实现 燕 Edmonds-Karp算法及其复杂性分析 最大流在最大二分匹配问题中的应用 清华大学软件字院宋斌 请华大学狱件学院宋斌恒10 清华大学 软件学院 宋斌恒 55 Bipartite graph A bipartite graph is a graph can be partitioned its vertices into two parts L and R, L and R are disjoined and all edges go between L and R 左L 右R 清华大学 软件学院 宋斌恒 56 举例说明 二分图实例 清华大学 软件学院 宋斌恒 57 Finding the maximum matching in a bipartite graph Is the maximum-bipartite-matching problem. Application of the matching problem: If L is set of machines, R is a set of tasks, the edges means that the machine can do the task. Finding the maximum simultaneously performing tasks 清华大学 软件学院 宋斌恒 58 Convert the maximum-bipartite￾matching problem to a maximum flow problem 左L 右R s ？ t 清华大学 软件学院 宋斌恒 59 利用流求二分图的正确性 如何保证最后的最大流对应的边构成一 个匹配？ Ford－Fulkerson算法如何保证流是整 数？ 清华大学 软件学院 宋斌恒 60 总结： 流的定义和属性 最大流与分割 残余流与增广路 Ford－Fulkerson方法 Ford－Fulkerson实现 Edmonds－Karp算法及其复杂性分析 最大流在最大二分匹配问题中的应用