##### 霍尔婚配定理 - 霍尔婚配定理 - **霍尔婚配定理**主要描述了在一个[[二分图]]中, 如何判断是否存在[[二分图的匹配|完美匹配]], 即每个顶点都与另一个顶点相匹配, 涉及[[相异代表系]]. 设 $G=(X\sqcup Y,E)$ 是一个二分图, 其中 $|X|=|Y|$, 则 $G$ 存在一个完美匹配的充要条件是 $\forall S\subseteq X$, $|N(S)|\geq |S|$, 其中 $N(S)$ 表示 $S$ 在 $Y$ 中所有邻居组成的集合 - $\forall S\subseteq X$, $|N(S)|\geq |S|$ >[!example]- 霍尔婚配定理 > - 场景 > - 左侧 $U$, $3$ 位男生 $\{A,B,C\}$ > - 右侧 $V$, $3$ 位女生 $\{X,Y,Z\}$ > - 心仪关系 > - $A$ 喜欢 $X,Y$ > - $B$ 喜欢 $Y,Z$ > - $C$ 喜欢 $X,Z$ > - 验证霍尔条件, 对 $U$ 的每个子集 $S$, 检查其邻居数 $|N(S)|\geq|S|$ > - $S=\{A\}$, $N(S)={X,Y}$, $|N(S)|=2≥1$ > - $S=\{B\}$, $N(S)={Y,Z}$, $|N(S)|=2≥1$ > - $S=\{C\}$, $N(S)={X,Z}$, $|N(S)|=2≥1$ > - $S=\{A,B\}$, $N(S)={X,Y,Z}$, $|N(S)|=3≥2$ > - $S=\{A,C\}$, $N(S)={X,Y,Z}$, $|N(S)|=3≥2$ > - $S=\{B,C\}$, $N(S)={X,Y,Z}$, $|N(S)|=3≥2$ > - $S=\{A,B,C\}$, $N(S)={X,Y,Z}$, $|N(S)|=3≥3$ > - 所有子集均满足霍尔条件，存在完美匹配 > - $A\rightarrow X$, $B\rightarrow Y$, $C\rightarrow Z$ > - $A\rightarrow Y$, $B\rightarrow Z$, $C\rightarrow X$