在片段末尾介绍的霍尔定理是什么？

适用条件

• 适用于二分图。
• 需要没有瓶颈的条件。

理解与推导

1. 检查图是否有任何瓶颈。
2. 如果没有瓶颈，则得出存在匹配的结论。

例子

幻灯片标题写着霍尔定理，陈述写着反之，如果没有瓶颈，那么就有匹配。不明显。接下来讨论。

容易误解的地方

• 假设瓶颈引理的逆命题同样容易证明。
• 认为霍尔定理提供了寻找匹配的算法。

观看对应讲解

继续追问

• 为什么三女两男的例子证明不可能有匹配？
• 霍尔定理的逆命题关于瓶颈和匹配说了什么？