L005 匹配

匹配和最大匹配

对于图 \(G=\left\langle V,E\right\rangle\) 和边子集 \(M\subseteq E\)，若 \(M\) 中的边两两不相邻，则 \(M\) 称作 \(G\) 的一个「匹配」（matching），\(M\) 中边的端点称作被 \(M\)「饱和」（saturated），又称「已匹配」（matched）。

对于匹配 \(M\)，若 \(M\) 不是 \(G\) 任何匹配的真子集，那么称 \(M\) 是 \(G\) 的「极大匹配」（maximal matching），边数最多的匹配称为 \(G\) 的最大匹配（maximum matching）。

对于图 \(G=\left\langle V,E\right\rangle\) 和匹配 \(M\subseteq E\)，若路 \(P\) 交替经过集合 \(M\) 和 \(E\setminus M\) 中的边，则称 \(P\) 为 \(M\)「交错路」（alternating path），起点和终点均未被 \(M\) 饱和的非平凡 \(M\) 交错路称作 \(M\)「增广路」（augmenting path）。

Th.5.1（Berge 定理）：对于图 \(G=\left\langle V,E\right\rangle\) 和匹配 \(M\subseteq E\)，\(M\) 是最大匹配当且仅当 \(G\) 不含 \(M\) 增广路i。

「匈牙利算法」（Hungarian algorithm）

【Algo.5.1、Algo.5.2】

Th.5.2

「霍普克罗夫特-卡普算法」（Hopcroft-Karp algorithm）

【Algo.5.3、Algo.5.4、Algo.5.5】

Th.5.3 Th.5.4

「花算法」（blossom algorithm）、「花」（blossom）、「花梗」（stem）、「花托」（base）。

完美匹配

对于图 \(G=\left\langle V,E\right\rangle\) 和匹配 \(M\subseteq E\)，若 \(M\) 饱和顶点集 \(V\) 中所有顶点，则 \(M\) 称作 \(G\) 的「完美匹配」（perfect matching）。

Th.5.5（Hall 定理）：对于二分图 \(G=\left\langle X\cup Y, E\right\rangle\)，\(G\) 有饱和顶点子集 \(X\) 中所有顶点的匹配当且仅当 \(\forall S\subseteq X,|N(S)|\ge |S|\)，其中 \(N(S)\) 表示 \(S\) 中点的邻点构成的集合。

\(G\) 中所有奇数阶连通分支的数量记作 \(o(G)\).

Th.5.6（Tutte 定理）：对于图 \(G=\left\langle V,E\right\rangle\)，\(G\) 有完美匹配当且仅当 \(\forall S\subseteq V,o(G-S)\le |S|\).