完全匹配

在 二分图 $⟨V_1,E,V_2⟩$ 的边集 $E$ 中能够找到一个包含所有 $V_1$ 的端点，且端点不重复的子集，形成的子图称为 完全匹配，即存在一个从 $V_1$ 到 $V_2$ 的的 单射

必要条件

$|V_1|\le |V_2|$

相异性条件（充要条件）

霍尔定理

二分图 $G=⟨V_1,E,V_2⟩$ 中存在从 $V_1$ 到 $V_2$ 的 完全匹配 的充分必要条件是 $V_1$ 中任意 $k$ 个结点至少与 $V_2$ 中的 $k$ 个结点相邻，$k=1,2,\dots ,|V_1|$

通常称为相异性条件

指向原始笔记的链接

t 条件（充分条件）

• $V_1$ 中每个结点至少关联 t 条边
• $V_2$ 中每个结点至多关联 t 条边

上面的条件满足 相异性条件 故能证明匹配存在

只要计算 $V_1$ 中的最小度 $\delta$ 和 $V_2$ 中的最大度 $\Delta$ 就可以了，只要满足 $\delta \le \Delta$ 就判断成功，如果不连通就按连通分支来考虑

选组长问题是一个完全匹配的运用：

组长放 $V_1$，所有组员放 $V_2$，可能选出来的情况连边, 要求不能兼职，那么就转化为完全匹配问题了