二分图

定义

二分图，又称二部图，英文名叫 Bipartite graph。

二分图是什么？节点由两个集合组成，且两个集合内部没有边的图。

换言之，存在一种方案，将节点划分成满足以上性质的两个集合。

性质&判定

如果两个集合的各个节点分别表示不同的颜色，那么每条边都连接不同颜色的节点。

且没有奇环的无向图一定是二分图。

判定二分图可以遵循以上的过程对每条边的两个端点染不同的颜色，如果发现无法满足上述条件即不是二分图。

二分图最大匹配

• 匹配的定义：选出一些边，使这些边两两之间不具备相同的端点。

• 最大匹配：在上述限制下使选出的边的数量尽可能大。

增广路算法 Augmenting Path Algorithm

也叫匈牙利算法。

对于二分图左部未匹配到的点，如果存在一条增广路，那么匹配数量就增加 $1$，最后没有增广路了那么就是最大匹配。（增广路定理）

*增广路：以非匹配边开始，以非匹配边结束的一条路径，使得路径上的边是非匹配边，匹配边交错出现。

那么代码就很容易写出来了，注意此处可以在更新右部匹配的时候顺便更新左部匹配，这样的话更好处理以后的内容。

（以下是时间戳优化的版本）

1
2
3
4
5
6
7
8
9
10
11
12

bool dfs(ll x,ll r){
	for(ll i=0;i<op[x].size();i++){
		if(vis[op[x][i]]==r) continue;
		vis[op[x][i]] = r;
		if(!link[op[x][i]]||dfs(link[op[x][i]],r)){
			link[op[x][i]] = x;
			link2[x] = op[x][i];
			return 1;
		}
	}
	return 0;
}

同理，可以转化为 Dinic 求网络流，此处不展开讨论。

二分图最小点覆盖（König 定理）

• 最小点覆盖：选最少的点，满足每条边至少有一个端点被选。

二分图中，最小点覆盖 $=$ 最大匹配。

首先最小点覆盖一定 $\ge$ 最大匹配，因为最大匹配的每条边至少选一个端点。

考虑构造性算法：

假设我们求出了一组最大匹配，然后对于左部未被匹配到的点执行 dfs，但是规定从左部到右部的边只能经过非匹配边，从右部到左部的边只能经过匹配边。那么最后左部未被访问到的点和右部访问到的点构成一组最小点覆盖。

证明：

首先这个方法的大小肯定是等于最大匹配的，一个匹配边要么两个端点都没有访问到，要么都访问到了，并且最小点覆盖肯定不包含不在最大匹配上的点。

其次一定可以满足在上述 dfs 中所经过的所有边都有一个点是右部访问到的点（非增广路以非匹配边开始一定以匹配边结束），然后剩下的就是左部未访问到的点，恰好能够满足覆盖所有边。

二分图最大独立集

• 最大独立集：选最多的点，满足这些点两两无边连接。

引理：最小点覆盖 $+$ 最大独立集 $=$ 总点数。

证明很显然，把最小点覆盖中的点及其连接的边删去，图中就没有边了，剩下的点构成最大独立集。

因为，二分图最大独立集 $=$ 总点数 $-$ 最大匹配数。

有向无环图最小路径划分/覆盖

• 路径划分：选出若干条不相交的路径，使得每个点恰好被经过 $1$ 次。
• 路径覆盖：选出若干条路径，使得每个点被经过至少 $1$ 次。

划分

将每个点拆成入点和出点，那么对于每一条 $u \to v$ 的边，连接 $u_{out}\to v_{in}$，形成一个二分图，那么这个有向无环图最小路径划分就是 $n-$ 二分图最大匹配数。

证明：

我们可以将这个有向图最开始看做 $n$ 条路径，然后二分图最大匹配中的每一条边就可以看做将末尾是 $a$ 的路径和开头是 $b$ 的路径连接，总路径就会减少一条，并且因为每个 $u$ 结尾的路径最多连接一条以 $v$ 结尾的路径，每个 $v$ 开头的路径最多连接一条 $u$ 结尾的路径，故最大匹配是正确的。

覆盖

对原图跑一个传递闭包，然后对 $w_{i,j}=1$ 的 $i,j$ 连接一条 $i \to j$ 的边，容易发现，新图也是一个有向无环图在新图上再跑上面的最小路径划分就行了。

正确性证明：

其实就是将有相交的路径中的相交的地方保留了一处，其它路径直接越过这个地方，就转化为了最小路径划分。

注：如果是有向图就会出现环的情况会被判作 $0$ 条链（匹配数是 $n$，节点数是 $n$，剩下 $n-n=0$），但实际上需要至少 $1$ 条链。

有向图环覆盖

类似于上面的情况，还是对每个点拆成入点和出点，连边后跑二分图匹配判断是否有完美匹配即可。证明同上，只不过在最后一次合并的时候一定会合并成至少一个环，恰好满足要求。

以上三种有向图上的问题均可以输出方案，只需要存储经过了哪些边即可。（二分图匹配上的边）

有向无环图最大反链

根据 Dilworth 定理，有向无环图最大反链 $=$ 有向无环图最小路径划分。

此处主要讲述输出方案：

首先像最小路径划分一样求出二分图的最大独立集的方案（点集 $-$ 最小点覆盖）。
若 $x_{in}$ 和 $x_{out}$ 都在二分图的最大独立集里，那么 $x$ 就存在于当前二分图最大匹配所对应的有向无环图最大反链。

证明同最小点覆盖，用作复习。

如果要求出每个点是否可能存在于一种最大反链，那么可以把这个点以及与其含有偏序关系的点去掉，然后再跑出来最大反链，如果此时最大反链的大小只减少了 $1$，那么就可以存在于一种最大反链之中。

二分图博弈

两个人操控二分图上的一颗棋子，每个人移动这个棋子到另一个未被移动到过的点，若不能移动则失败。

定理：对于某个节点若先手必胜当且仅当这个节点一定存在于这个二分图的最大匹配中。

证明：

• 如果这个节点存在于二分图的最大匹配中，那么先手移动的一定是沿着匹配边走，后手一定移动到一个匹配点。如果走到了非匹配点，那么设当前的路径是 $s \to p_1 \to p_2 \to \dots \to p_k$，那么把当前的匹配边 $(S,p_1),(p_2,p_3),\dots,(p_{k-2},p_{k-1})$ 右移一位变为 $(p_1,p_2),(p_3,p_4),\dots,(p_{k-1},p_k)$，后面的点不变，那么与 $S$ 一定在最大匹配上矛盾。

• 反之，如果不在二分图的最大匹配上，那么先手一走，一定走到匹配点上，后手就必胜了。

后记

二分图有很多技巧：求一个点是否一定在最大匹配中，一条边是否一定在最大匹配中等等。

这些问题通常通过修改匈牙利算法的顺序或者重复执行查找增广路的过程得出。

并且还可以通过二分得到二分图最大匹配的前提下最大的边权最小是多少。

需要灵活运用匈牙利算法。