组合数学课程笔记（？）：图的匹配

二分图匹配和霍尔定理

相异代表系

我们用一个相异代表系描述二分图匹配问题。我们有若干个集合 \(\{S_1,S_2,S_3,\cdots,S_m\}\)，现在要给每个集合选定一个代表 \(x_i\in S_i\)，并且每个 \(x_i\) 是相异的。

容易发现这个问题和二分图匹配问题是等价的。

霍尔定理

• 对于 \(m\) 个集合，如果它们存在一个相异代表系，等价于对于任何的 \(I\subseteq \{S_1,S_2,\cdots,S_m\}\)，都有 \(|\bigcup_{i\in I}S_i|\ge |I|\)。

首先，必要性是明显的，如果存在一个 \(I\) 不满足，那么显然对于这个子问题无解。然后就是要证明充分性，也就是只要有 \(\forall I,|\bigcup_{i\in I}S_i|\ge |I|\)，都存在一个相异代表系。

数学归纳法

假设条件对任意 \(n\lt m\) 成立，考虑规模为 \(n\) 的子问题。我们定义 \(|\bigcup_{i\in I}S_i|=|I|\) 的集合 \(I\) 是特殊的。那么，我们按照当前集合是否存在特殊的子集分类。如果不存在，我们可以随便选择一个集合和它内部的任何的点。因为任何的 \(|\bigcup_{i\in I}S_i|>|I|\)，所以在两边都至多减去 \(1\) 个之后依旧有 \(|\bigcup_{i\in I}S_i|\ge|I|\)。这就是规模 \(n-1\) 的子问题，得证。

我们需要处理的是存在特殊集合的子问题。首先，因为 \(|\bigcup_{i\in I}S_i|=|I|\)，所以这一块很明显变成了独立的子问题。\(\bigcup_{i\in I}S_i\) 外面的不可能和里面匹配（否则里面的就不够用了），里面又不能和外面匹配。那么我们的问题就被划分成 \(I\) 和 \(X/I\) 两部分。而 \(I\) 里面的子集都是原来的子集，\(I\) 是显然满足条件的。我们只需要验证 \(X/I\) 满足霍尔条件。

我们发现，对 \(X/I\) 里的任何子集 \(J\)，考虑它和我们取走的特殊子集 \(I\)，有 \(|\bigcup_{i\in I}S_i\cup\bigcup_{i\in J}S_i|\ge |I\cup J|\)。因为 \(I\) 和 \(J\) 很明显不交，所以 \(|I\cup J|=|I|+|J|\)。所以 \(|\bigcup_{i\in I}S_i|+|\bigcup_{i\in J}S_i|\ge |\bigcup_{i\in I}S_i\cup\bigcup_{i\in J}S_i|\ge |I\cup J|=|I|+|J|\)。因为 \(|\bigcup_{i\in I}S_i|=|I|\)，所以 \(|\bigcup_{i\in J}S_i|\ge |J|\)。也就是 \(X/I\) 同样满足霍尔条件，得证。

原始对偶现象

二分图最大匹配=二分图最小点覆盖

矩阵形式

我们把二分图的邻接矩阵写出来。则二分图最大匹配等价于找到最多的 \(1\) 使得它们的行和列互不相同。二分图最小点覆盖等价于选择一些行和一些列覆盖所有的 \(1\)，是选中的行和列总和最少。

证明

证明最小点覆盖不小于最大匹配是简单的。\(a\) 个独立的 \(1\) 至少需要 \(a\) 行或列覆盖。那么我们需要证明最小点覆盖不大于最大匹配，就能证明两者相等。我们考虑把最小点覆盖选定的行和列置换到前面，则我们的矩阵变成只有前 \(a\) 行和前 \(b\) 列有值（二者满足其一即可）。然后我们把前 \(a\) 行右边的部分扒出来，证明在这个子矩阵中一定存在 \(a\) 个独立的 \(1\)。如果存在，对偶的对最下角也成立，所以就存在 \(a+b\) 个独立的 \(1\)。得证。如果不存在，那么首先，如果有某一行没有，除掉这一行也不会有影响。如果有的列少于 \(a\)，那么全部用列覆盖显然更优，都和当前是最小点覆盖的假设矛盾。所以每一行每一列都有 \(a\)，根据霍尔定理，也就一定存在 \(a\) 个独立的 \(1\)。

得证二分图最大匹配等于二分图最小点覆盖。

平面图

平面图最大匹配可以用带花树算法在多项式时间内解决，平面图最小点覆盖则是 \(NP-hard\) 的。不过，我们可以证明最小点覆盖在最大匹配和二倍最大匹配之间，这是显然的。

偏序集最大反链=偏序集最小链覆盖

偏序集图就是如果 \(a\rightarrow b\) 有边 \(b\rightarrow c\) 有边则 \(a\rightarrow c\) 有边的图。

偏序集图上的一条链就是所有的元素相继有边的点集。偏序集图上的一个反链是任何元素都没有边的点集。

考虑画二分图，每个点在左右都对应画一个边。如果 \(u\rightarrow v\) 有边，就在二分图上连一个 \(v_{left}\leftarrow u_{right}\)。根据二分图最大匹配等于二分图最小点覆盖，这张图同样满足性质。

然后我们研究反链，我们发现其实就是点覆盖中选了的点一定是反链中没有的。所以最大反链是点总数减去最小点覆盖。

之后研究链。我们把每个相对的 \(u_{left}\) 和 \(u_{right}\) 连一条虚边，然后从第一个点开始往下走路径。我们发现，当前不能往下走当且仅当当前点没有匹配。所以链的个数就是在最大匹配中没有匹配到的点的个数，是点总数减去最大匹配。

得证二者相等。

霍尔定理

我们再用这个定理推回霍尔定理。我们发现我们可以把相异代表系理解成一个二层的偏序图，每个元素向集合连边当且仅当集合包含它。

我们发现，当前元素的相异代表系是一个链覆盖，并且是最小链覆盖。所以我们只需要证明满足霍尔条件时，这个偏序图的最大反链是 \(n\) 即可。

假设最大反链中，选择的所有的集合一共 \(k\) 个，因为霍尔条件，它们至少连到 \(k\) 个元素，这些都不能选。所以反链的大小不超过 \(n-k+k=n\)。同时还存在所有元素集合作为一个大小为 \(n\) 的反链，所以得到最大反链是 \(n\)，最大匹配是 \(n\)，充分性证明，霍尔定理得证。

鸽笼原理

我们之前证明过 \(mn+1\) 的序列要么存在 \(m+1\) 的不降序列，要么存在 \(n+1\) 的降序列。现在用这个定理可以方便的证明。我们在 \(a_i\le a_j(i<j)\) 的 \(i,j\) 之间连边，否则不连。那么不降序列就是一个链，降序列就是一个反链。而最小的不降序列覆盖和反链大小相等。而如果反链大小 \(\gt n\)，直接成立。否则，我们要用 \(\le n\) 个序列覆盖 \(nm+1\)，根据鸽笼原理一定会有一个序列超过 \(m\)。也就得证。