最大流算法及其应用备课讲稿.ppt

最大流模型 一个典型的最大流模型就是二分图的最大二分匹配 二分图G=(X,Y,E)其中X和Y是两个不相交的点集并且对于每对(u,v)EuX且vY二分图的最大二分匹配问题就是从E中选择一些边使得每个点最多在选择的边里出现一次问最多能选多少条边 图2 一个二分图的例子及其最大匹配实线表示选中的边虚线表示未选中的边 分析 实际上我们可以将二分图的最大匹配问题转换为最大流问题增加源和汇将源连到每个左边的