二分图中的最大匹配总是完美匹配吗？

Question

Hopcroft-Karp 算法能否帮助确定二分图的完美匹配？

Answer 1

没有。只有当两个集合中的顶点数量相等时，才有可能实现完美匹配。

无法找到此图的完美匹配：

即使两个集合的顶点数相同，如果缺少边，最大匹配也不会完美:

Answer 2

你的假设是错误的。二部图中的最大匹配可能不是完美匹配。考虑以下示例：

  a1
 / \
b1  b2

这显然是一个二分图，集合A = {a1}和B = {b1, b2}。最大匹配将由该图的一条边组成。我们不能只用一条边覆盖所有三个顶点。所以，没有完美的匹配。