二分图

notes

  • 匈牙利算法

    【模板】二分图最大匹配

    1
    2
    3
    4
    5
    6
    7
    8
    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,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$ 开始标记能达到的右部点（反），那么被标记的点均为非必须点，其补集为必须点。

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

  • 二分图边染色

    颜色数为最大点的度数。

    1
    2
    3
    4
    5
    6
    7
    8
    inline int mex(int *a){ int res=1; for(;a[res];++res); return res; }
     
    a=rd,b=rd,m=rd;
    for(int i=1,x,y,c1,c2;i<=m;++i){
    	c1=mex(to[x=rd]),c2=mex(to[y=rd+a]),e[x][y]=e[y][x]=i;
    	to[x][c1]=y,to[y][c2]=x,mx=max({mx,c1,c2});
    	if(c1!=c2) for(int u=y,tmp=c2;u;u=to[u][tmp],tmp^=c1^c2) swap(to[u][c1],to[u][c2]);
    }

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