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

  • 本文讨论无权图

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

0. 一些前置

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

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

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

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

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

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

  因此，只要证明了从一侧的任一点出发都找不到增广路，那么整张二分图就没有增广路。我们不妨假设从左侧出发。

  我们归纳地证明一下（通过讨论匈牙利算法进行到左侧的第几个点）。我们要证明的是，匈牙利算法进行完某一个点之后，从这个点出发以及从之前的（左侧的）点出发都找不到增广路，即图中没有增广路。下文的提及的“前xx个点“都是数左侧的点。

  首先，当一开始算法进行完 \(0\) 个点的时候，前 \(0\) 个点中没有增广路。如果你不放心，那么我们考虑算法进行第一个点，要么有增广路被增广了 第一个点变成了匹配点 ，从前 \(1\) 个点出发没有增广路；要么就找不到增广路，同样从前 \(1\) 个点出发没有增广路。

  现在我们假设前 \(k\) 个点出发没有增广路，我们想证明，在进行完第 \(k + 1\) 个点的搜索、（可能存在的）增广之后，图中不存在增广路。

  如果从这个点出发找不到增广路，那么也肯定不会有任何操作，也就不会影响前面的点的结果，因此前 \(k + 1\) 个点中没有增广路。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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