为什么三女两男的例子证明不可能有匹配？

适用条件

• 具有左侧集合 G 和右侧集合 B 的二分图。
• 三个女孩的突出子集 S。
• 它们的集体邻域 $E(S)$ 只包含两个男孩。

理解与推导

1. 识别三个女孩的子集 S。
2. 确定这三个女孩的邻域 $E(S)$。
3. 比较大小：|S| = 3 且 |$E(S)$| = 2。
4. 应用瓶颈引理：因为 |S| > |$E(S)$|，所以不可能有匹配。

例子

图表显示那三个女孩只连接到右侧的两个男孩。演讲者解释说，两个男孩必须在三个女孩之间共享，所以没有足够的兼容男孩让所有三个女孩都能被独特地匹配。

容易误解的地方

• 认为只有当整个右侧太小时匹配才会失败。
• 假设左侧的其他两个女孩能以某种方式弥补这个特定子集缺乏男孩的问题。

观看对应讲解

继续追问

• 在这段视频中，瓶颈是如何定义的？
• 瓶颈引理说了什么？