二部图

定义

二部图（Bipartite Graph）：设无向图 $G = ⟨ V, E ⟩$ ，若能将 $V$ 划分成两个不相交的非空子集 $V_{1}$ 和 $V_{2}$ ，使得 $G$ 中的任何一条边的两个端点分别属于 $V_{1}$ 和 $V_{2}$ ，则称 $G$ 为二部图（或称偶图）。 $V_{1}$ 和 $V_{2}$ 称为互补顶点子集。

完全二部图（Complete Bipartite Graph）：若 $V_{1}$ 中每个顶点与 $V_{2}$ 中每个顶点之间都有且仅有一条边相连，则称 $G$ 为完全二部图，记作 $K_{r, s}$ ，其中 $r = ∣ V_{1} ∣$ , $s = ∣ V_{2} ∣$ 。

判定定理

定理：一个无向图 G 是二部图当且仅当 G 中不含奇圈（长度为奇数的圈）。

这是二部图的重要特征性质。该定理可通过染色法来理解：对图的顶点进行二染色，若存在奇圈，则无法用两种颜色使得相邻顶点不同色。反之，若图中不含奇圈，则可通过 BFS 对图进行二染色，从而得到二部划分。

二部图的匹配

匹配是二部图的核心研究内容之一。二部图中的匹配（Matching）是指边集的一个子集，其中任意两条边没有公共顶点。

最大匹配：边数最多的匹配。
完美匹配：覆盖了所有顶点的匹配。

Hall 定理（婚姻定理）

定理：设 $G = ⟨ V_{1}, V_{2}, E ⟩$ 是二部图， $G$ 中存在从 $V_{1}$ 到 $V_{2}$ 的匹配覆盖 $V_{1}$ 中所有顶点当且仅当对任意 $S \subseteq V_{1}$ ，都有 $∣ N (S) ∣ \geq ∣ S ∣$ ，其中 $N (S)$ 表示 $S$ 的邻域。