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

• 本文讨论无权图

• 思维上没什么难度，但是文字量却比自己想的要多……

0. 一些前置

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

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

• 增广路、交错路是什么？

  “增广路、交错路概念” 这里引用 OI-wiki 的内容介绍。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.题外话：非二分图上的无权图的匹配

  思路：在图上进行 BFS 或者 DFS 进行染色，转化为二分图。那么有：如果存在奇环，那么不能直接转化成二分图，否则是可以的。涉及到奇环的问题需要锁点等技巧，就另见“带花树算法”了。

  首先，二分图只可能有偶环，没有奇环。我们假设二分图形成了环状结构，那么存在一条路径以某一点为起点和终点。根据二分图性质，因为起点和终点同一个点，所以一定处于同一侧，那么路径长度就一定为偶数，因此只能有偶环，不能有奇环。

  其次，我们考虑对一个无向图进行 dfs 染色，黑白相间。我们考虑搜索树上的情况，因为无向图 dfs 树只有 T 边和 B 边，T边上显然不冲突。考虑 B 边构成环的情况。可以看出，如果颜色染色不冲突，那么根据奇偶性质，一定是偶环，偶环不冲突。奇环一定冲突，所以不可能是奇环。

  于是，有点充要的，二分图和不含奇环的无向图可以相互转化。至于唯一性，那需要考虑连通性的问题了。

热门相关：倾心之恋：总裁的妻子   拒嫁豪门，前妻太抢手   后福   后福   本法官萌萌哒