Berge定理

概述

Berge定理（Berge’s Theorem）：图 $G$ 中的匹配 $M$ 是最大匹配，当且仅当 $G$ 中==不存在 $M$-增广路径==。该定理由 Claude Berge 于 1957 年提出，是匹配理论中最基本的结构性定理，为所有匹配算法（包括匈牙利算法、Hopcroft-Karp 算法）提供了理论基础。

定理陈述

形式化陈述

定理（Berge, 1957）：设 $G=(V,E)$ 是一个无向图，$M\subseteq E$ 是 $G$ 中的一个匹配。则：

$M\text{ 是最大匹配}⟺G\text{ 中不存在关于 }M\text{ 的增广路径}$

其中，$M$-增广路径是一条长度为奇数的路径 $v_0,v_1,\dots ,v_{2k+1}$，满足：

• $v_0$ 和 $v_{2k+1}$ 都是未匹配顶点（不与 $M$ 中的任何边关联）
• 路径上的边交替属于 $M$ 和 $E\setminus M$：$(v_0,v_1)\notin M$，$(v_1,v_2)\in M$，$\dots$，$(v_{2k},v_{2k+1})\notin M$

直觉理解：增广路径就像是一条”可以改进”的路径——沿着它翻转匹配状态，就能让匹配多覆盖两个顶点（起点和终点）。如果不存在这样的改进路径，说明当前匹配已经无法改进了。

证明概要

证明思路

证明分为两个方向：必要性（$\Rightarrow$）和充分性（$\Leftarrow$）。

步骤 1：必要性（$\Rightarrow$）——若存在增广路径则 $M$ 不是最大匹配

设 $P=v_0,v_1,\dots ,v_{2k+1}$ 是一条 $M$-增广路径。构造新匹配： $M^{\prime }=(M\setminus \{(v_1,v_2),(v_3,v_4),\dots ,(v_{2k-1},v_{2k})\})\cup \{(v_0,v_1),(v_2,v_3),\dots ,(v_{2k},v_{2k+1})\}$

即将 $P$ 上所有匹配边替换为非匹配边（“翻转”操作）。由于 $P$ 上有 $k$ 条匹配边和 $k+1$ 条非匹配边，翻转后 $|M^{\prime }|=|M|-k+(k+1)=|M|+1$。因此 $M$ 不是最大匹配。

步骤 2：充分性（$\Leftarrow$）——若不存在增广路径则 $M$ 是最大匹配

反证法。假设 $M$ 不是最大匹配，但 $G$ 中不存在 $M$-增广路径。设 $N$ 是 $G$ 中的一个最大匹配，且在所有最大匹配中，$|M\Delta N|$（对称差）最小。

考虑由 $M\Delta N$ 导出的子图 $H$。由于 $M$ 和 $N$ 都是匹配，$H$ 中每个顶点的度数至多为 2（每个顶点最多关联 $M$ 中一条边和 $N$ 中一条边）。因此 $H$ 的每个连通分量是以下之一：

• 一条偶数长度的路径（两端都是匹配边或都是非匹配边）
• 一条奇数长度的路径（一端是 $M$ 的匹配边，另一端是 $N$ 的匹配边）
• 一个偶数长度的环

由于 $|N|>|M|$，$N$ 比 $M$ 多至少一条边。在 $H$ 中，$N$ 的边比 $M$ 的边多，因此 $H$ 中必存在一个连通分量，其中 $N$ 的边比 $M$ 的边多。这个分量只能是一条以 $N$ 的非匹配边开头和结尾的奇数路径——但这正是一条 $M$-增广路径，与假设矛盾。

因此 $M$ 是最大匹配。

学术参考：MIT 18.455/18.433 课程讲义给出了清晰的完整证明：https://math.mit.edu/~goemans/18455S20/lecs-matching.pdf

关键推论

• 匹配算法的设计原则：寻找最大匹配等价于寻找增广路径，因此所有匹配算法的核心操作都是”找增广路径并增广”
• 二部图匹配的特殊性：在二部图中，增广路径可以通过 BFS/DFS 高效搜索（Hopcroft-Karp 算法利用这一点达到 $O(\sqrt{V}\cdot E)$ 的时间复杂度）
• König 定理的推导：Berge 定理结合二部图的结构性质可以推导出 König 定理（最大匹配 = 最小顶点覆盖）
• 最大匹配的唯一性：若图中不存在增广路径，则当前匹配是唯一的最大匹配当且仅当不存在交替环（即所有环上的匹配边与非匹配边数量相等）

应用场景

• 算法导论 Ch25：Berge 定理是匈牙利算法和 Hopcroft-Karp 算法的理论基础
• 任务分配：通过反复寻找增广路径来增大匹配，直到找到最大匹配
• 稳定婚姻问题：Gale-Shapley 算法的正确性分析中也用到增广路径的概念
• 一般图匹配：Edmonds 的”开花”（blossom）算法将 Berge 定理推广到一般图，通过收缩奇数环来处理增广路径搜索中的困难情况
• 匹配多面体：Berge 定理是匹配多面体（matching polytope）刻画的基础，Edmonds 利用增广路径的概念给出了匹配多面体的完整线性描述

参见

• 二分匹配 — 二分匹配的定义、增广路径、König 定理
• 二部图 — 二部图的定义与判定
• 最大流 — 通过最大流求解二分匹配
• 图论 — 图论基础概念