二分图

匈牙利算法

【模板】二分图最大匹配

int dfs(int u){
	for(int i=head[u];i;i=ne[i]){
		if(vis[v[i]]) continue; vis[v[i]]=1;
		if(!mat[v[i]]||dfs(mat[v[i]]))
			return mat[v[i]]=u,vis[v[i]]=0,1;
	}
	return 0;
}

时间复杂度 $O(nm)$。

性质

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

就是 menger 定理的点形式。

求出最大匹配，遍历每一个未匹配的左部点，将增广路标记。

取未标记的左部点和标记的右部点作为点覆盖。

证明

二分图最大独立集 $=n-$ 二分图最大匹配。

最小点覆盖的补集。

补图的最大独立集为原图的最大团。

hall 定理

对于点数分别为 $x,y(x \le y)$ 的二分图，若其最大匹配为 $x$ 那么称其有完备匹配。

二分图存在完备匹配当且仅当 $\forall |S| \le |N(S)|$。

归纳法，每次删掉一对。

二分图最大匹配为 $x - \max\{|S|-|N(S)|\}$。

归纳法，每次删掉一对。

[CERC2016] 二分毯 Bipartite Blanket

存在匹配同时覆盖 $X,Y$，当且仅当存在匹配覆盖左部点集 $X$，且存在匹配覆盖右部点集 $Y$。

证明考虑将两个匹配拼起来，对于偶环/奇链，间隔选择即可。对于偶链，假设左部点多于右部点，一定存在一个左部点 $\notin X$，删去即可。

二分图博弈

在二分图上两个人轮流移动一个棋子，不能经过重复节点，不能动者输。

那么先手必胜当且仅当初始位置为必须点。

必经可行点边

跑二分图最大匹配，在残量网络上跑强连通分量（包括 $s,t$）。

• 若一条边为匹配边且两个端点不属于同一个强连通分量，那么它为必须边。

• 若一条边为匹配边或两个端点属于同一个强连通分量，那么它为可行边。

• 从 $s$ 开始标记能达到的左部点，从 $t$ 开始标记能达到的右部点，那么被标记的点均为非必须点，其补集为必须点。

• 若一个点存在一条相邻的可行边，那么它是可行点。

染色

Edge coloring of bipartite graph