算法札记：匈牙利算法正确性证明

匈牙利算法Hungarian Algorithm通常指用于求解‌二分图最大匹配‌的算法。其正确性证明主要基于图论中的两个核心定理‌增广路定理‌和‌König定理‌。以下是严谨的逻辑推导过程1. 核心概念定义‌匹配 (Matching)‌图中一组没有公共端点的边。‌最大匹配 (Maximum Matching)‌包含边数最多的匹配。‌增广路 (Augmenting Path)‌设 M 为当前匹配若路径 P 满足以下条件则称 P 为关于 M 的增广路起点和终点都是未匹配点非饱和点。路径上的边交替属于“非匹配边”和“匹配边”。由于起点和终点未匹配且边交替出现增广路的长度必为奇数且非匹配边比匹配边多一条。‌对称差 (Symmetric Difference)‌对于两个匹配 M 和 M′其对称差 M⊕M′ 是由那些只属于 MM 或只属于 M′M′ 的边组成的集合。2. 证明逻辑框架证明分为两个主要部分‌充分性‌如果当前匹配 M 中不存在增广路则 M 是最大匹配。‌必要性‌如果 M 不是最大匹配则一定存在增广路。这等价于上述命题的逆否命题也是算法终止条件的依据。第一部分无增广路 ⇒ 最大匹配‌定理 (Berges Lemma)‌一个匹配 M 是最大匹配当且仅当图中不存在关于 M 的增广路。‌证明‌假设 M 是当前匹配且图中不存在关于 M 的增广路。我们要证明 M 是最大匹配。设 M∗ 是图中的任意一个最大匹配。考虑集合 SM⊕M∗即 M 和 M∗ 的对称差。在子图 G′(V,S) 中每个顶点的度数最多为 2因为每个顶点在 M 中最多关联一条边在 M∗ 中也最多关联一条边。因此G′ 由若干条‌不相交的路径‌和‌环‌组成。分析这些连通分量的结构‌环‌由于边在 M 和 M∗ 之间交替环的长度必为偶数。环中来自 M 的边数和来自 M∗ 的边数相等。‌路径‌路径上的边也交替属于 M 和 M∗。如果路径以 M 中的边开始并以 M 中的边结束或者以 M∗ 开始以 M∗ 结束则两种边的数量相等。如果路径以 M∗ 中的边开始并以 M 中的边结束或反之则其中一种匹配的边比另一种多一条。‌关键推论‌如果存在一条路径其来自 M∗ 的边比来自 M 的边多一条那么这条路径的起点和终点必然都是 M 的未匹配点因为它们在 M∗ 中被匹配但在 M 中未被匹配且路径两端不属于 M。这就构成了一条关于 M 的‌增广路‌。‌矛盾导出‌根据前提假设图中‌不存在‌关于 M 的增广路。因此在 SM⊕M∗ 的所有路径分量中不可能出现“M∗ 的边比 M 的边多”的情况。同理也不可能出现“M 的边比 M∗ 的边多”的情况吗不我们需要比较 ∣M∣ 和 ∣M∗∣。实际上由于 M∗ 是最大匹配∣M∗∣≥∣M∣。如果在任何路径中 M∗M∗ 的边都不多于 MM 的边且在环中两者相等那么总边数 ∣M∗∣ 不可能大于 ∣M∣。既然 ∣M∗∣≥∣M∣ 且 ∣M∗∣≤∣M∣由无增广路推导出的结构限制即无法通过异或操作增加 M 的边数而不产生增广路则必有 ∣M∣∣M∗∣。‌结论‌M 的边数等于最大匹配 M∗ 的边数故 M 是最大匹配。第二部分算法如何保证找到无增广路的匹配匈牙利算法的核心操作是‌寻找增广路并增广‌。‌初始状态‌空匹配 M∅显然无增广路或者说任何单边都是增广路算法会立即增广。‌迭代过程‌算法尝试为左部集的每个点寻找增广路。如果找到增广路 P则执行 M←M⊕P。新匹配 M′ 的边数比 M 多 1。如果找不到增广路则该点无法加入当前匹配算法继续处理下一个点。‌终止条件‌当遍历完所有左部点且对于每个点都找不到增广路时算法终止。‌正确性维持‌每次增广后匹配大小增加 1。关键在于‌之前的点是否可能因为后续的增广而重新获得增广路‌根据 Berge 定理的证明逻辑一旦算法确定某个点 u 在当前匹配下没有增广路并且算法继续处理其他点即使其他点的匹配状态改变也不会为 u 创造出新的增广路。这是因为如果存在从 u 出发的增广路它必然涉及之前已经处理过的点的匹配调整而这种调整在之前的搜索中已经被穷举或排除具体实现中通过vis数组标记避免重复搜索理论上由增广路的性质保证单调性。更直观的解释是匈牙利算法本质上是在构建交错树。如果从 u 出发的交错树无法到达右部未匹配点说明在该连通分量内已匹配点数与可访问的右部点数满足 Hall 定理的限制无法进一步扩展。3. 补充König 定理视角虽然 Berge 定理直接证明了最大匹配与增广路的关系但匈牙利算法的正确性也常通过 ‌König 定理‌ 来辅助理解其在最小点覆盖中的应用间接验证其完备性。‌König 定理‌在二分图中‌最大匹配数‌ ‌最小点覆盖数‌。匈牙利算法找到的最大匹配 M可以通过构造最小点覆盖来验证其最优性。如果算法停止意味着无法再增加匹配边此时构建的点覆盖大小等于匹配数根据 König 定理这确实是全局最小的点覆盖从而反证了匹配的极大性。总结匈牙利算法的正确性依赖于以下逻辑链‌增广路存在性‌匹配非最大 ⟺ 存在增广路。‌增广操作有效性‌沿增广路取反匹配数严格 1。‌终止性‌有限步内必能找出所有增广路因为每步匹配数增加且有上限。‌最终状态‌算法终止时图中不存在增广路 ⇒ 当前匹配为最大匹配。#includeiostream #includecstdio #includecstring #define _for(i,a,b) for (int i(a);i(b);i) using namespace std; const int N1e35,M1e55; int n1,n2,m; int e[M],ne[M],h[N],idx; int match[N]; bool vis[N]; inline void c_plus(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); } inline void init(){ memset(h,-1,sizeof(h)); idx0; } inline void add(int a,int b){ e[idx]b; ne[idx]h[a]; h[a]idx; } bool get(int x){ for (int ih[x];~i;ine[i]){ int je[i]; if (vis[j]) continue; vis[j]true; if (!match[j] || get(match[j])){ match[j]x; return true; } } return false; } int main(){ init(); c_plus(); int ans0; cinn1n2m; _for(i,1,m){ int u,v; cinuv; add(u,v); } _for(i,1,n1){ memset(vis,0,sizeof(vis)); if (get(i)){ ans; } } coutansendl; return 0; }