二分图

Author Avatar
Axell 8月 15, 2019
  • 在其它设备中阅读本文章

二分图

前置知识

定义: 一个无向图,可以分成两个互不相交的点集
判定: 至少有两个节点,没有奇环
二分图最大匹配: 选出尽可能多的边,使得每个点仅被不超过一条边覆盖
二分图最小点覆盖: 选出尽可能少的点,使得每条边被覆盖
二分图最大独立集: 选出尽可能多个点,使得每个点之间没有边相连
二分图最大团: 选出尽可能多个点,构成一张完全图(二分图的补图上的最大独立集就是原图的最大团)

相关计算方法

二分图最大匹配

匈牙利算法

一些定义
匹配边: 在二分图中在两个点集之间连接的边,匹配边两端都是匹配点。
未匹配边: 在二分图中在两个点集之间连接的边,未匹配边一端是未匹配点一端是匹配点。
增广路: 在二分图中从未匹配点开始,按照未匹配边,匹配边交替的模式找到一个未匹配点结束。

在执行匈牙利算法时,就是从每个点出发,尝试寻找一条增广路,把路径上的所有原匹配点的匹配方向取反,即可得到匹配边数+1的方案
代码如下

bool dfs(int x){
    for (int i=head[x];i;i=Pth[i].Next){
        int y=Pth[i].y;
        if (!vis[y]){
            vis[y]=1;
            if (!match[y] || dfs(match[y])){
                match[y]=x;
                return 1;
            }
        }
    }
    return 0;
}
//main
int ans=0;
for (int i=1;i<=n;++i){
    memset(vis,0,sizeof vis);
    if (dfs(i)) ans++;
}

二分图最小点覆盖

定理: 二分图最小点覆盖等于二分图最大匹配
理解
1. 首先可以发现,最小点覆盖一定>=最大匹配(因为最大匹配的所有边都是没有共同点的,至少每条边选出一个顶点)
2. 此时不可能存在有一条边两端都没有被选中,否则存在一条长为1的增广路,与最大匹配的定义矛盾
3. 因此二分图最小点覆盖等于二分图最大匹配

二分图最大独立集

定理: 二分图最大独立集等于二分图两侧点数-二分图最大匹配
理解: 想要所有的点全部不相连,就得删除某些点,可以发现,删除最小点覆盖的那些点时,正好满足条件,且不可能有更好的方案

DAG最小路径覆盖

概念
DAG最小不相交路径点覆盖: 选出尽量少的若干路径,使得DAG所有点被路径经过,且每个点仅被覆盖一次
DAG最小可相交路径点覆盖: 选出尽量少的若干路径,使得DAG所有点被路径经过,每个点可被覆盖多次
有向图的拆点二分图: 把有向图的每个点$V$拆成$V_x$,$V_y$(x为左部节点,y为右部节点),对于一条边$(a,b)$,在二分图中连接$(a_x,b_y)$

可以发现, DAG最小不相交路径点覆盖 = DAG的点数-拆点二分图的最大匹配数
理解: 可以发现,每找到一组匹配边,就相当于把两条路径连接成一条路径,因此不难看出
DAG最小可相交路径点覆盖由于路径可以相交,因此先对原图做传递闭包,可以转化为不相交路径覆盖来做

一些例题

机器任务安排二分图最小点覆盖
泥泞的区域(muddy)分成行泥泞块和列泥泞块,对于每个点,连接它所在的行泥泞块和列泥泞块,二分图最小点覆盖
骑士放置(horse)对格子进行黑白染色,可以发现是个二分图,把可以互相攻击的骑士连边,二分图最大独立集
vani和cl2捉迷藏(travel) 先进行传递闭包,然后发现任意可见的两点只能选出一个点,二分图最大独立集

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。

本文链接:https://axell.wind-flower.cn/archives/二分图/