##### 二分图的匹配 - 二分图的匹配 - **二分图的匹配**指对[[二分图]]中元素的[[图匹配|匹配]]问题进行建模, 如任务分配, 婚姻匹配, 网络流等问题. 具有[[霍尔婚配定理]], 判断二分图是否存在完全匹配. 给定一个二分图 $G = (V_1 \cup V_2, E)$, 其中 $V_1$​ 和 $V_2$ 是两个互不相交的顶点集, 对于任意 $S \subseteq V_1$, 满足 $|N(S)| \geq |S|$ 则存在完美匹配, $N(S)$ 表示 $S$ 在图中的邻域, 即与 $S$ 中顶点相邻的所有 $V_2$ 顶点