在二分图匹配讲座中，$E(S)$ 是什么意思？

适用条件

• S 是左侧顶点的子集。
• 邻接关系在给定的二分图中取值。

理解与推导

1. 识别左侧顶点的子集 S。
2. 找出所有通过边连接到 S 中至少一个顶点的右侧顶点。
3. 将这些右侧顶点收集到集合 $E(S)$ 中。

例子

幻灯片在右侧写上 $E(S)$，后来声明 $E(S)$ ::= 与 S 中至少一个女孩相邻的男孩。

容易误解的地方

• 将 $E(S)$ 与与 S 关联的边集混淆。
• 认为 $E(S)$ 包含 S 本身的顶点。

观看对应讲解

继续追问

• 在这段视频中，瓶颈是如何定义的？
• 为什么三女两男的例子证明不可能有匹配？