algorithm - 为什么图论中的最大流算法对于最大二分匹配是正确的

Question

我读过很多文章，指出可以使用最大流算法找到二分图的最大匹配。但是有可能我们从最大流中得到的匹配不是最大的，或者匹配没有最大边。

来自 Anti Laaksonen 的竞争性编程手册的示例：

但是，如果我以不同的方式呈现图表，那么现在的图表是：

然后随着最大流量算法的进行，匹配将是 1----5, 2----7

因为 1 只是擦除了到 sink 的路径，但如果它会去边缘 1----6 那么匹配可能是

1----6, 3----5, 4----7

标签： algorithmgraphbipartitemax-flow

Answer 1

我一直和你在一起，直到这一点：

然后随着最大流量算法的进行，匹配将是 1----5, 2----7

您在这里描述的实际上并不是图中的最大流量。我们可以通过发送一个流量单位从 1 到 6、一个流量单位从 2 到 7 以及一个流量单位从 3 到 5 来推动更多流量。

阅读你的问题，我认为你最终得到（非最大）流量而不是最大流量的原因是因为这个陈述：

因为 1 只是删除了到水槽的路径

根据您在此处的描述，我假设您正在使用类似 Ford-Fulkerson 算法的算法来计算最大流量：找到从源到汇的增广路径并推动流量穿过它。但是 Ford-Fulkerson 在这里还有第二步：在推动流越过边缘之后，我们在推动的流的相反方向上引入剩余边缘。如果我们找到更好的路径，这提供了“撤销”我们做出的决定的机会。

结果，在我们从 1 到 5 推动一个单位流之后，我们将一个剩余边从 5 添加回 1，具有单个容量单位。这意味着图表现在看起来像这样：

在这里，蓝绿色的边缘从 s 流向 t，而紫色的边缘从 t 流向 s。

请注意，我们可以“撤销”我们将 1 分配到 5 的决定，如下所示。在路径上推动一个流量单位

s → 3 → 5 → 1 → 6 → t

给这个流网络：

现在，在路径上再推一个单位的流量

s → 2 → 7 → t

给出整体匹配 1 -- 6, 2 -- 7, 3 -- 5，这是最大匹配。