不连通图中的最大二分匹配

Question

当您的图有多个组件时，如何找到最大二分匹配？每个组件可以用两种方法着色。如何决定集合X和Y，以便运行最大匹配例程？

- rohit89

---

最大匹配或最大二分匹配？（前者是不可解决的） - abeln

将例程分别在每个组件上运行，将你的答案合并？ - btilly

@abeln 它是最大二分匹配。 - rohit89

@btilly 问题在于，根据你着色的方式（特别是对于奇数顶点的图形），你可以以不同的方式进行组合。 - rohit89

@abeln- 在一般图中进行最大匹配可以使用多种算法在多项式时间内解决，其中最好的算法渐进复杂度非常好(O(m sqrt n)，我相信)。虽然算法具有高常数因子，但它肯定是可行的。 - templatetypedef

你在谈论什么最大匹配算法？X和Y是什么？图的分区？ - fuglede

Answer 1

如果您的图有几个不同的连通分量，您可以通过找到每个分量中的最大匹配并返回它们的联合来在图中找到最大匹配。

至于如何决定集合X和Y，存在许多算法用于检测特定图是否为二分图，并在此情况下为节点分配标签以恢复这两个组。您可以使用修改后的DFS或BFS轻松完成此操作。因此，您的问题的算法可能是

1. 对整个图运行DFS以将其分解为连通分量。
2. 对于这些组件中的每一个：
   1. 在这些组件上运行DFS以恢复哪些节点在组X和Y中。
   2. 使用最大二分匹配算法在该组件中找到最大匹配。
3. 将所有结果组合在一起以获得总体答案。

希望这可以帮助您！

- templatetypedef

Answer 2

不要从边缘的角度看待匹配，而是将其视为一组边缘。这种观点使得无论如何连接子结果，它在后面仍然是可以的。

1. 将图形分成连通组件

2. 对于每个图形组件，使用您选择的算法找到最大匹配。

3. 找到的匹配的并集是整个图形的最大匹配。

- hugomg

Answer 3

我不知道什么是非连通图，但如果你有一个像我这样的完全图，这可能对你很有趣：http://wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html。它使用了修改后的 Floyd-Warshall 算法来查找最大匹配。我不知道这与匈牙利算法之间的区别。

- Micromega