Konig-Egervary定理

概述

Konig-Egervary定理（Konig-Egervary Theorem）：在二部图中，最大匹配的基数等于最小顶点覆盖的基数。这是图论中最优美的对偶定理之一，建立了匹配理论与覆盖理论之间的精确等价关系。

定理陈述

形式化陈述

设 $G=(V,E)$ 是一个二部图，顶点集划分为 $V=L\cup R$（$L$ 和 $R$ 分别为左部和右部）。

• 匹配（Matching）：边集 $M\subseteq E$，其中任意两条边不共享端点。$|M|$ 称为匹配的基数
• 顶点覆盖（Vertex Cover）：顶点子集 $C\subseteq V$，使得 $E$ 中每条边至少有一个端点在 $C$ 中。$|C|$ 称为覆盖的基数

Konig-Egervary定理： ${\max }_{M\text{ 是匹配}}|M|={\min }_{C\text{ 是顶点覆盖}}|C|$

即二部图中最大匹配的大小等于最小顶点覆盖的大小。

前置概念

关键定义

• 二部图 $G=(L\cup R,E)$：顶点可划分为两个不相交集合 $L$ 和 $R$，每条边的端点分别属于 $L$ 和 $R$
• 最大匹配：基数最大的匹配，记其大小为 ${\alpha }^{\prime }(G)$
• 最小顶点覆盖：基数最小的顶点覆盖，记其大小为 $\beta (G)$
• 交替路径：从未匹配顶点出发，边交替属于匹配和不在匹配中的路径
• 增广路径：两端都是未匹配顶点的交替路径

证明概要

证明思路（通过最大流最小割定理）

证明将二部图匹配问题转化为流网络问题，利用最大流最小割定理完成证明。

步骤1：构造流网络

给定二部图 $G=(L\cup R,E)$，构造有向流网络 $G^{\prime }=(V^{\prime },E^{\prime })$：

• 添加源点 $s$ 和汇点 $t$
• 从 $s$ 向每个 $u\in L$ 添加容量为 $1$ 的有向边 $(s,u)$
• 将 $G$ 中每条无向边 $\{u,v\}$（$u\in L,v\in R$）替换为容量为 $1$ 的有向边 $(u,v)$
• 从每个 $v\in R$ 向 $t$ 添加容量为 $1$ 的有向边 $(v,t)$

步骤2：建立匹配与流的对应

• 匹配 $\to$ 整数流：匹配 $M$ 中的每条边 $\{u,v\}$ 对应流网络中 $s\to u\to v\to t$ 的单位流。$|f|=|M|$
• 整数流 $\to$ 匹配：由流的整数性定理，最大流可以取为整数流。每条从 $L$ 到 $R$ 的流边对应匹配中的一条边
• 因此：最大匹配的基数 = 最大流的值

步骤3：建立顶点覆盖与割的对应

• 流网络中的 $(s,t)$-割 $(S,T)$（$s\in S,t\in T$）的容量为： $c(S,T)=|S\cap L|+|T\cap R|+\text{（跨割的 }L\to R\text{ 边数）}$
• 最小割 $\to$ 顶点覆盖：设 $(S,T)$ 是最小割，令 $C=(S\cap L)\cup (T\cap R)$。可验证 $C$ 是 $G$ 的顶点覆盖，且 $|C|\le c(S,T)$
• 顶点覆盖 $\to$ 割：设 $C$ 是顶点覆盖，令 $S=\{s\}\cup (C\cap L)\cup (R\setminus C)$，则 $(S,V^{\prime }\setminus S)$ 是割，容量 $c(S,T)\le |C|$
• 因此：最小顶点覆盖的基数 = 最小割的容量

步骤4：应用最大流最小割定理

由最大流最小割定理： $\text{最大流值}=\text{最小割容量}$

结合步骤2和步骤3的对应关系： $\max |M|=\text{最大流值}=\text{最小割容量}=\min |C|$

即 ${\alpha }^{\prime }(G)=\beta (G)$。

参考资源：

• Cornell CS4820 Konig定理讲义：https://www.cs.cornell.edu/courses/cs4820/2025sp/notes/16-Konig.pdf
• 南京大学组合数学Wiki：https://tcs.nju.edu.cn/wiki/index.php/组合数学_(Spring_2014)/Flow_and_matching

关键推论

• 一般图不成立：Konig定理仅在二部图中成立。在一般图中，${\alpha }^{\prime }(G)\le \beta (G)$，但等号不一定成立（例如三角形 $K_3$：最大匹配为1，最小顶点覆盖为2）
• Hall婚姻定理：二部图存在完美匹配当且仅当对每个 $S\subseteq L$，$|N(S)|\ge |S|$（Hall条件）。这可以由Konig定理推出
• 算法意义：Konig定理保证了可以通过最大流算法（如Ford-Fulkerson）在多项式时间内同时求出最大匹配和最小顶点覆盖
• 独立集与顶点覆盖的互补性：在任意图中，最大独立集 $+$ 最小顶点覆盖 $=|V|$。因此二部图中最大独立集 $=|V|-$ 最大匹配

应用场景

在算法导论（CLRS）Ch25/Ch29中的具体应用：

1. 二分匹配：Konig定理是二分匹配理论的核心结果，为最大匹配算法提供了理论基础
2. 二部图：在二部图中，许多优化问题（如任务分配、排班问题）可以归约为最大匹配问题
3. 最大流：通过流网络归约，最大流算法成为求解二部图匹配的标准工具
4. 分配问题：将工人分配到任务、将学生分配到项目等场景中，最大匹配给出最优分配方案
5. 顶点覆盖的精确求解：虽然一般图的顶点覆盖是NP-hard的，但二部图中的最小顶点覆盖可以在多项式时间内精确求解

参见

• 二部图
• 二分匹配
• 最大流
• 图论
• 连通图
• 贪心算法