修改二分图，使其具有完美匹配

Question

给定一个边 X 和 Y 大小相等的二分图，我们如何有效地找到我们必须添加的最小边数以使该图具有完美匹配？有没有比迭代所有 2^(|X|) 子集并添加边直到满足霍尔定理更好的解决方案？

谢谢。

Answer 1

如果我理解正确的话，应该可以生成一个cardinality-maximal matching of the initial graph efficiently, by either using the so-called Hungarian method或者模型化为一个网络流问题。一旦找到 cardinality-maximal 匹配，每个分区中必须有相等数量的不匹配节点，可以随意使用额外的边进行匹配。

换句话说，如果M是原始图中cardinality-maximal匹配的基数并且|X|=|Y|成立，那么至少M-|X|条边必须添加以便在图中包含完美匹配。