在这段视频中，瓶颈是如何定义的？

适用条件

• S 是左侧顶点的子集。
• $E(S)$ 是 S 在右侧集合中的邻域。

理解与推导

1. 取左侧顶点的任意子集 S。
2. 计算 S 的大小，记为 |S|。
3. 计算其邻域 $E(S)$ 的大小，记为 |$E(S)$|。
4. 比较这两个大小：如果 |S| > |$E(S)$|，则 S 是一个瓶颈。

例子

幻灯片显示 |S| = 3 和 2 = |$E(S)$|，后来声明 |S| > |$E(S)$|。演讲者说：“瓶颈的定义是，如果你有一个集合，其中 S 的大小大于 S 的像的大小，那么这就称为瓶颈。”

容易误解的地方

• 认为瓶颈意味着整个图的右侧顶点太少。
• 假设 |S| >= |$E(S)$| 就足以成为瓶颈。

观看对应讲解

继续追问

• 瓶颈引理说了什么？
• 为什么三女两男的例子证明不可能有匹配？