二分图匹配学习笔记
二分图 定义 如果一个图 $G=(V,E)$ 中的结点可以被分为两个部分，且两个部分之内的点互相没有连边，则称这种图为二分图。如果每个结点的度数相等且都为 $k$，则称这种二分图为 $k$ - 正则二分图。 判断 对图的结点进行黑白染色，相连的结点染不同的颜色，若最后满足每条边的两个端点颜色不相同，则这个图是二分图。树也是二分图。 染色 这里的染色不同于判断的染色，它指的是对边进行染色。若染 $k$ 种颜色，则称其为二分图的 $k$ 染色。 对于一个 $k$ - 正则二分图来说，它一定可以被 $k$ 染色，而对于一般的二分图，若其最大度数为 $k$，则它也可以被 $k$ 染色。 匹配 在二分图的边集中选出一个非空子集，且这个非空子集内没有两条边连接了一个相同的端点，则这个非空子集被称为二分图的一个匹配，同样对于一般图也有类似的概念。 若一个匹配的所含的边数最大，则称这个匹配为最大匹配。 若二分图两边的结点个数相同，且存在一个匹配满足其中的边连接了所有的点，则这个匹配被称为这个二分图的完美匹配或者完备匹配。 若每条边有边权，且一个匹配的所含的边的权值和最大，则这个匹配被称为这个二分图的最大权匹配。 匈牙利算法 交替路 假设在二分图最大匹配的过程中，已经找到了一些边作为一个匹配，则一条交替路就是一个匹配边和非匹配边交替连接组成的简单路径。 根据二分图的定义，假设一条交替路的起点在左边，且第一条边是匹配边，则这条交替路中的匹配边一定都是从左边到右边，而非匹配边一定是从右边到左边。 交替路上的结点最多连接一条匹配边和一条非匹配边，所以如果把交替路上的匹配边变为非匹配边，非匹配边变为匹配边，则仍然满足条件，也就是交替路边集的匹配边集的补集也可以是匹配。 增广路 匈牙利算法的核心就是找增广路，这条增广路是一条交替路。每次增广从左边开始，第一条边是非匹配边，最后一条边也是非匹配边，根据上文的描述，这样的路径的边数为奇数，非匹配边个数比匹配边个数多 $1$，若把匹配边与非匹配边反转，则反转后的边集仍然是一个合法的匹配，且比原来的匹配的边数多了 $1$。如果能找到一条这样的增广路，则此次增广成功。 具体来说，比如一个左边的结点 $x$ 找到了一个右边的结点 $y$，它没有与其他左边的结点匹配过，则 $e(x,y)$ 可以作为一个匹配边，反转边集前，有 $1$ 条匹配边，$0$ 条非匹配边，增广成功。 如果右边的结点 $y$ 已经有匹配了，那么就可以让原来 $y$ 的匹配 $x'$ 新找一个点 $y'$，如果能够找到这个 $y'$，那么 $e(x',y')$ 成为一个匹配边，$y$ 就无需和 $x'$ 匹配了，也就是说 $y$ 已经变为了一个没有匹配的点，$x$ 就可以与 $y$ 匹配了。如果 $x'$ 找不到 $y'$，那么 $x'$ 就要保持原样，和 $y$ 匹配，那么 $x$ 就不可以和 $y$ 匹配，只能继续寻找下一个可能的结点。...