二分图相关

% \(\rm \color{red}{L}\color{black}{BY}\) 学长。

0.定义：

• 二分图:

二分图是一张图 \(G = (V, E)\)，其中点集 \(V\) 可以分成两个部分 \((V1, V2)\)，满足 \(V1 \cap V2 = \emptyset, V1 \cup V2 = V\)，且 \(V1, V2\) 中均没有边，即对于 \(\forall e \in E, e = (v_i, v_j)\)，均有 \(v_i \in V1, v_j \in V2\)。注意：接下来称 \(V1\) 为左部点，\(V2\) 为右部点。

• 匹配：

一张图的匹配定义为一个原图的一个子图，且满足任意两条边均没有公共端点。一个匹配的大小定义为其中边的个数，一个图的最大匹配定义为匹配的大小最大的一个匹配。特殊的，对于一个匹配且该匹配完全包含左部点或右部点时，我们称该匹配是完美匹配，完美匹配一定是原图中的最大匹配。

• 点覆盖：

一张图的覆盖定义为原图中点集的一个子集，满足原图中每条边均有一个端点在该点集中。一个覆盖的大小定义为点集的大小，最小点覆盖就是原图中最小的覆盖。

• 独立集：

一张图的独立集定义为原图中点集的一个子集，满足原图中每条边的端点至少有一个不在该点集中。一个覆盖的大小定义为点集的大小，最大独立集就是原图中最大的独立集。

1.二分图最大匹配：

二分图中的最大匹配求法较一般图是简单的，我们接下来探究对于二分图如何求最大匹配。

我们要引入匈牙利算法。依次考虑左部点并进行匹配，假设我们考虑到第 \(i\) 个点。我们找到与之相连的且没有标记过的右部点 \(v\)，并做标记，若 \(v\) 没有匹配，则给让 \(v\) 跟 \(i\) 匹配并返回 \(i\) 匹配成功。否则我们考虑更换与 \(v\) 匹配的左部点的匹配点，若更换成功，则将 \(v\) 与 \(i\) 匹配，否则考虑下一个点。当 \(i\) 一个点都没有匹配到时，返回没有找到即可。

注：其中我们称该过程中走的边为增广路或交替路，因为这条路径上的边是匹配边和非匹配边交替的。

匈牙利算法看起来相当暴力，实际上，它的时间复杂度为 \(O(n^3)\)。

bool dfs(int u){
	for(int i = 1; i <= n; i++){
		if(!vis[i] && G[u][i]){
			vis[i] = true;
			if(!match[i] || dfs(match[i])){
				match[i] = u;
				return true;
			}
		}
	}
	return false;
}

2.二分图最小点覆盖：

对于求解二分图中的最小点覆盖问题，我们可以考虑将其转化为最大匹配问题求解。

König定理：二分图中，最大匹配等于最小点覆盖。

• 证明：

首先我们可以知道最大匹配 \(\le\) 最小点覆盖。因为最小点覆盖至少要覆盖到匹配边，而匹配边端点互不相交，故每条匹配边都需要一个单独的点去覆盖。

接下来我们考虑构造出一种方案取到下界。具体方案是从未匹配的右部点出发，走交替路并且标记经过的点，最后选择左边标记的点和右边未标记的点。画图容易发现每个点恰好是一条匹配边的端点，原因大概是从左向右走的一定是匹配边，因此左边标记过的点如果是匹配点，一定会将所在匹配边的右部点标记而不会选进点集中。而右边未标记的点一定是匹配点，于是恰好覆盖了所有匹配边且恰好没有重复。

对于完全覆盖的证明，我们考虑使用反证法，假设有一条边没有被覆盖到，则它对应的左部点一定是未标记过，而右部点是标记过的。进一步的，该边不可能是未匹配边，但是若该边是匹配边，则右部点只可能是由左部点走过来，但是这样左部点就标记了，推出矛盾，从而定理得证。

3.二分图最大独立集：

与最小点覆盖问题类似，我们依旧考虑转化问题。

实际上，我们可以考虑将点覆盖与独立集建立映射关系。具体的，一个独立集的补集即为原图的一个点覆盖。这是因为独立集中的点两两之间没有任何边，于是剩下的点