⚠ 转载请注明出处：作者：ZobinHuang，更新日期：May.16 2022

本作品由 ZobinHuang 采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

如果 $M$ 是图 $G$ 的匹配，$G$ 中一条由 $M$ 中的边和非 $M$ 中的边交错形成的路，称为$G$ 中的一条 $M$ 交错路 (M Alternating Path)。特别地，若 $M$ 交错路的起点与终点是 $M$ 非饱和点，称这种 $M$ 交错路为 $M$ 增广路(M Augmenting Path) 或 $M$ 可扩路。

以上图为例，设 $M={v_7v_8,v_3v_4}$，则路 $v_6v_7v_8v_3v_4$ 和 $v_1v_7v_8v_2$ 都是 $M$ 交错路，其中后者是 $M$ 增广路。

Berge 定理

Berge 定理定义如下:

$G$ 的匹配 $M$ 是最大匹配，当且仅当 $G$ 不包含 $M$ 增广路。

首先采用反证法证明必要性: 在已知 $G$ 的最大匹配 $M$ 的条件下，若 $G$ 包含一条 $M$ 增广路 $P$，则可令该增广路为: $P=v_0v_1v_2...v_{2k}v_{2k+1}$。显然，$P$ 中 $M$ 中的边比非 $M$ 中的边少一条。于是作新的匹配 $M_1$，它当中的边由 $P$ 中非 $M$ 中边组成。$M_1$ 中边比 $M$ 中多一条，这与 $M$ 是 $G$ 的最大匹配矛盾。

然后使用反证法证明充分性: 在已知 $G$ 不包含 $M$ 增广路的条件下，假设 $M$ 不是 $G$ 的最大匹配。令 $M_1$ 是 $G$ 的最大匹配，则有 $|M_1|>|M|$，也即 $M_1$ 中的边数至少比 $M$ 多 $1$。下面考虑 $G[M_1\Delta M]$ (p.s. $\Delta$ 是图的对称差运算，见子图、图运算、路与连通性)，则:

$\Delta[G(M_1\triangle M)] \le 2$
$\delta[G(M_1\triangle M)] \ge 1$

可以断言，$G(M_1\triangle M)$ 是不交圈和路的并，则考虑 $G(M_1\triangle M)$ 导出分支的各种情况：

若导出分支是圈，则该圈一定是偶长圈，且来自 $M_1$ 和 $M$ 的边交替出现 (i.e. 因为如果是奇长圈，否则与匹配的定义相矛盾，具体如上图所示)。若 $G(M_1\triangle M)$ 只包含圈，则来自 $M_1$ 和 $M$ 的边数量相同。但是由于 $|M_1|>|M|$，因此一定存在至少一条路 $P$，其首尾都是 $M$ 非饱和点，则此时这条路 $P$ 即为 $M$ 增广路，与假设不符，因此充分性得证。

Berge 定理给我们提供了迭代扩大 $G$ 的匹配的思路 (算法)。

二部图的匹配与覆盖

考虑这样一个问题，有 $7$ 位求职者 $A,B,C,...,G$，它们求职的岗位有 $a,b,c,...,g$。它们投递的情况如下图所示，求解的是是否存在一种情况使得所有求职者都能找到工作。

事实上，上述问题是一个二部图求匹配的问题。我们从以下两方面开始对这个问题的探讨。

如何判定二部图的匹配是否存在?
如何求出二部图的匹配?

下面的小节解决前面一个问题，再下一小节解决第二个问题。

二部图的匹配的存在性

下面给出 Hall 定理：

设 $G=(X,Y)$ 是二部图，则 $G$ 存在饱和 $X$ 每个顶点的匹配的充要条件是：对 $\forall S \subseteq X$，有 $|N(S)| \ge |S|$，其中 $S$ 表示 $X$ 的一个点子集，$N(S)$ 表示 $S$ 的邻点的集合。

证明:

首先证明必要性。如果 $G$ 存在饱和 $X$ 每个顶点的匹配，则由匹配的定义，$X$ 的每个顶点在 $Y$ 中至少有一个邻点，所以对 $\forall S \subseteq X$，有 $|N(S)| \ge |S|$。

然后使用反证法证明充分性：假设不存在饱和 $X$ 每个顶点的匹配。不妨设 $M$ 是 $G$ 的最大匹配，但点 $u$ 未被 $M$ 饱和，$u \in X$。

令 $Z$ 是所有的以 $u$ 为起点的 $M$ 交错路的集合。记 $S=Z \cap X$，$T=Z \cap Y$。断言 $S$ 中所有点的邻居都在 $T$ 中，$T$ 中的所有点都是 $S$ 中点的邻居，也即 $N(S) = T$。证明：显然有 $T \subseteq N(S)$，然后证明等号成立。假设 $\exists v\in N(S)$ \ $T$，也即属于 $S$ 中点的邻居但不在 $T$ 中的一个点，此时可得到一条 $uv$ 增广路，根据 1，这与 $M$ 是 $G$ 的最大匹配矛盾，因此有 $N(S) = T$ 成立。而事实上，$|S|=|T|+1$ (i.e. $S$ 比 $T$ 多了一个点 $u$)，故有 $|S| = |N(S)| + 1$，也即 $|N(S)|<|S|$，这与假设矛盾，故充分性得证。

上述定理存在如下推论：

若 $G$ 是 $k$ 正则二部图 $(k>0)$，则 $G$ 存在完美匹配 (i.e. 存在最大匹配饱和图中所有的点)。

证明:

一方面，由于 $G$ 是 $k$ 正则二部图，于是有 $k \cdot |X| = k \cdot |Y|$，故有 $|X|=|Y|$。

另一方面，对于 $X$ 的任一非空子集 $S$，设 $E_1$ 和 $E_2$ 分别是与 $S$ 和 $N(S)$ 相关联的边集，显然有 $E_1 \subset E_2$，也即 $k \cdot |S| \le k \cdot |N(S)|$，也即 $S \le |N(S)|$，由 2 可得，该二部图存在饱和 $X$ 中每个顶点的匹配。又因为 $|X|=|Y|$，所以一个匹配饱和了 $X$ 中的所有顶点相当于饱和了 $Y$ 中的所有顶点，因此图 $G$ 存在完美匹配。

点覆盖与 König 定理

首先我们给出关于点覆盖的定理，用以求解二部图的匹配问题。

$G$ 的一个顶点子集 $K$ 称为 $G$ 的一个点覆盖 (Vertex Cover)，如果 $G$ 的每条边都至少有一个端点在 $K$ 中。

$G$ 的一个包含点数最少的点覆盖称为 $G$ 的最小点覆盖，其包含的点数称为 $G$ 的覆盖数，记为 $\beta(G)$。

下面给出一个定理：

设 $M$ 是 $G$ 的匹配，$K$ 是 $G$ 的点覆盖，始终有 $|K|\ge|M|$。若 $|M|=|K|$，则 $M$ 是最大匹配，而 $K$ 是最小点覆盖。

证明：

首先证明始终有 $|K|\ge|M|$。由点覆盖和匹配的概念可知，$K$ 至少包含 $M$ 中每一条边的一个顶点，否则的话 $K$ 将不能覆盖图中所有的边。

然后证明后面一个结论。假设 $M^{\star}$ 是 $G$ 的最大匹配，$K^{\star}$ 是 $G$ 的最小点覆盖，则有 $|M| \le |M^{\star}| \le |K^{\star}| \le |K|$，现在有 $|M|=|K|$，故不等式上的等号全成立。

下面的 König 定理给出了二部图的点覆盖与二部图匹配间的关系，证明过程略:

在二部图中，最大匹配的边数等于最小点覆盖的顶点数。

Tutte 定理

上面看完了二部图的匹配，下面来看任意图的匹配问题。我们给出 Tutte 定理:

图 $G$ 有完美匹配当且仅当对 $V(G)$ 的任意子集 $S$，有 $o(G-S) \le |S|$

在上述定理中，$o(G−S)$ 表示奇分支数目 (奇分支是阶数为奇的连通分支)，且 $S$ 是 $V(G)$ 的任意子集 (可以是空集)。

下面有推论：

3 正则无桥图 (无割边) 存在完美匹配

证明:

设 $S$ 是 $V$ 的任意一个非空真子集，$G_1,G_2,...,G_k$ 是 $G-S$ 的所有奇分支。设 $m_i$ $(1 \le i \le k)$ 表示端点分属于 $S$ 和 $G_i$ 的边数。

下面我们对 $m_i$ 展开分析。

首先在 $G_i$ 中，所有顶点度和为 $2E(G_i)$。在 $G_i$ 中，每个顶点在 $G$ 中的总度数为 $3|V(G_i)|$。所以我们可以得到:

$m_i=3|V(G_i)|-2|E(G_i)|$

由于 $G_i$ 都是奇分支，因此 $V(G_i)$ 为奇数，因此 $m_i$ 必然也为奇数。由于 $G$ 没有割边，所以 $m_i \ge 3$。因此我们可以得到： $$o(G-S) = k \le \frac{1}{3} \sum_{i=1}^km_i \le \frac{1}{3} \sum_{v \in S} d(v) = \frac{1}{3} \cdot 3|S| = |S|$$

Zobin

二部图的匹配问题

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：May.16 2022

目录

图的匹配与 Berge 定理

图的匹配的概念

图的匹配的种类

图的 M 交错路和增广路

Berge 定理

二部图的匹配与覆盖

二部图的匹配的存在性

点覆盖与 König 定理

Tutte 定理