扩展路径算法-最大匹配

Question

我正在阅读扩充路径或Kuhn的算法，以便在未加权的二部图中找到最大匹配大小。

该算法试图找到一条交替的路径(由交替的未匹配和匹配的边组成)，在未匹配的顶点开始和结束。如果找到备用路径，则增加该路径，并将匹配计数加1。

我可以理解算法，但我在理解它通常实现的方式方面存在问题。这里有一个参考实现-- https://sites.google.com/site/indy256/algo/kuhn_matching2。

在每个阶段，我们应该尝试从左侧不匹配的顶点开始找到一条交替的路径。然而，在给定的实现中，在每次迭代中，我们不是尝试将所有不匹配的顶点作为可能的开始位置，而是仅从一个不匹配的顶点开始搜索，如以下代码所示：

for (int u = 0; u < n1; u++) {
      if (findPath(graph, u, matching, new boolean[n1]))
        ++matches;
    } 

这样，在迭代过程中不匹配的左侧顶点将永远不会再次尝试。我不明白为什么这是最优的？

Answer 1

这足以证明算法结束后不会留下任何扩充路径。因为没有增加路径意味着最大流量。假设Ai是左边的i个顶点，Bi是右边的i个顶点。

如果Ai已经匹配，那么它将在任何扩充路径中保持匹配。

所以，我们唯一关心的是，当我们考虑了Ai，没有发现匹配，但在for循环中进行了一些迭代后，Ai突然有了新的增强路径。我们将证明这永远不会发生。

让我们考虑Ai之前没有增广路径，假设S是dfs(i)可以访问的顶点集。只有两种方法可以让新顶点(以前不在S中)在之后包含在S中。

1. 对于S中的某些Ax，边Ax - By从匹配更改为不匹配(之后将包含在S中)

矛盾。因为我们应该通过- Ax - ... - Sink找到扩充路径，但是Sink不在S中，所以我们不能这样做。

• 对于S中的某些By，边By - Ax从不匹配更改为匹配(之后Ax将包含在S中)

又是矛盾。这一次，我们应该找到扩展路径Ax - By - ... - Sink，但同样，我们无法到达Sink from By。

由于上述原因，不可能意外地向左增加意味着最大流量的路径。

Answer 2

根据我的理解，该算法试图为每个左侧顶点u(从0到n1-1)找到一条增广路径。如果存在这样的路径，则可以将u添加到匹配中，使之前添加的所有顶点都保持在匹配中。如果不存在这样的路径，则不可能将u添加到匹配中。这源于扩充路径的特殊属性。

当我们为每个u检查这一点时，我们找到了可能添加到匹配中的最大顶点数，从而导致了最优性保证。