瓶颈引理说了什么？

适用条件

• 存在左侧顶点的子集 S。
• |S| > |$E(S)$|。

理解与推导

1. 识别图中是否存在瓶颈 S。
2. 如果存在这样一个子集 S 使得 |S| > |$E(S)$|，则得出不可能有匹配的结论。

例子

幻灯片标题写着瓶颈引理，陈述写着如果有瓶颈，那么不可能有匹配，这很明显。

容易误解的地方

• 认为该引理提供了一种寻找匹配的方法。
• 假设没有瓶颈就自动意味着存在匹配，而无需进一步证明。

观看对应讲解

继续追问

• 在片段末尾介绍的霍尔定理是什么？
• 为什么三女两男的例子证明不可能有匹配？