【二分图】二分图上匹配问题和匈牙利算法正确性说明

本文讨论无权图
思维上没什么难度，但是文字量却比自己想的要多……

0. 一些前置

什么是二分图上的匹配？什么是匈牙利算法？

“二分图最大匹配概念、匈牙利算法” 这里引用 Pecco 的介绍。这篇文章写的非常通俗易懂，而且揭示了匈牙利算法（或者说增广路）的本质是“朴素的匹配调整”。

增广路、交错路是什么？

1.匈牙利算法跑完之后，二分图中不存在增广路

我们先强调一下，在二分图上增广路的一些性质。因为增广路一定有偶数个点、奇数条边，因此二分图上增广路的两个端点一定分别在两侧。那么显然，如果从一侧出发找不到增广路，那么从另一侧出发肯定也找不到。以及增广路中除了两端点外所有的点都是匹配点，以及增广路中最左右两条边是未匹配的，剩下的边交替着匹配和未匹配。

然后我们归纳地来证一下。

因为匈牙利算法是从一侧的点出发，所以我们按照一侧（不妨是左侧）的点的规模来进行归纳，过程中间右侧的所有点都保持存在。显然，当左侧没有点的时候，不存在增广路。

之后我们考虑每加入一个点，会引入这个点，以及这个点和右侧点相连的若干条边。归纳假设是，新加入这个点之前，（跑完匈牙利算法）是没有增广路的。我们来考虑匈牙利算法在这个新加入的点上的表现情况。

因为之前的图里面没有增广路，所以新的增广路只能由这个新加入的点影响产生。第一种情况是，匈牙利算法从这个新加入的点出发，没有找到增广路。那么从之前的点出发也找不到增广路，于是整个图里面没有增广路，成立。

如果从新加入的这个点出发找到了增广路，那么这条路就要被增广，增广之后就不是增广路了。我们现在唯一要考虑的就是，这条路增广的过程中，会不会影响先前的点，使得先前的点中间出现增广路？

这里我们使用反证法。假设是增广之前，整张图里面没有增广路。新点加入之后，左侧点中，新加的这个点出发有增广路，从其他之前的点出发是没有增广路的。因为加入新点之后，如果形成增广路，那么终点一定在另一侧。小证明：分左侧点是起点、终点、中间点讨论。

一条增广路中间的点都是匹配点，所以左侧的之前的点不可能作为增广路的中间点。显然左侧未匹配点不能是从左侧出发的增广路的终点。我们考虑左侧的之前的点作为起点，新增加的边一定和新增加的点相连，而新增加的点没有匹配，因此不可能出现在增广路上，因此新加入的边是无法影响之前的增广路情况的。那么左侧之前的点，在新加入点前，就没有找到增广路，因此加入新点后，出发也找不到增广路。

增广完成后，增广的路径上都变成了匹配点。

我们考虑增广完成后的情况。假设，增广完成后，在之前的点中间（只能在之前的点中间出现在增广路，因为新点已经被匹配了），出现了增广路。

（本图中内容涵盖上文和下文，请结合对应部分内容阅读）

加入新的增广路和这次被增广的增广路没有交点，那就矛盾了，因为这次增广过程根本不会影响到这条路径，那么这条所谓的“新的”增广路在之前就是增广路，不符合我们的假设。

两条路径相交的时候，一条是我们发现的新的增广路，一条是本轮中经过增广后，整个路径上全部被匹配的路径。那么显然相交点不可能存在于增广路的两端，因为另一条路上的点全匹配了，增广路上没匹配。

（接下来的说明中，涉及到奇偶性的证明和匹配、未匹配冲突的说明，见上图）

我们考虑相交在增广路中间的时候，如果只是点相交但没有边的重合，那么显然是矛盾的，因为这样会产生匹配冲突。

如果有边的重合，那么我们还原到本轮增广之前的情况，肯定可以选取“新增广路”的端点和之前的端点形成增广路，与之前不存在增广路矛盾（画一下就可以知道）。

因此可以证明，本轮增广不会使得之前的点中形成新的增广路，整个图中没有增广路。这种情况也成立。

因此归纳成立。匈牙利算法进行完成后，二分图中不存在增广路。

2. 二分图中不存在增广路等价于达到最大匹配

我们把原命题逆否一下（逆否之后肯等等价），二分图没达到最大匹配等价于二分图中存在增广路

后推前是明显成立的。因为二分图中如果有增广路，那肯定可以增广一下，匹配数量+1。

前推后在这里引用一个证明：“匈牙利算法匹配即最大匹配的证明” 这里面的证明基于“匈牙利算法跑完后、二分图中不存在增广路”，也就是之前的证明。

3.最大匹配数等于最小点覆盖数

“二分图最大匹配的König定理及其证明” 在这里我引用了 Matrix67 的证明。下文关于König定理的证明是参考的这篇文章。

简而言之，最小点覆盖数的“瓶颈”是有多少条不相交的边（因为都得盖上）。所以最小覆盖数 \(\ge\) 最大匹配数（就是最多的不相交的边）。而当达成最大匹配之后，二分图中的匹配边可以分“方向”（和未匹配点的连接方式有关），按照方向在匹配边两个端点中的一个选择覆盖。最终证明可以覆盖所有边。那么最小点覆盖数 \(=\) 最大匹配数。