浅谈二分图

shyr · 2023-04-17 15:45:21 · 个人记录

对于一个图 G=(V,E)，若能将 G 分为两个子图 G_1=(V_1,E_1),G_2=(V_2,E_2)，且满足 E_1=E_2=\emptyset,V_1\cap V_2=\emptyset,V_1 \cup V_2=V，那么这个图就是一个二分图，V_1 被称为二分图的左部点，V_2 被称为二分图的右部点。

判定定理 一个图 G 是二分图，当且仅当 G 不存在奇环，即经过奇数个点的简单环。

证明 考虑由 V_1 回到 V_1 的路径的环所在集合必然是 V_1 \rightarrow V_2 \rightarrow V_1 \rightarrow V_2 \rightarrow \dots \rightarrow V_1，显然因为第一个点等于最后一个点，所经过的点数必然是偶数个。

因此，可以通过染色算法来判定二分图，即将每个点和与该点相邻的点染成异色，若有冲突，则该图不是二分图。

代码：

void color(int now,int co){
    vis[now]=co;
    for(int i=0;i<g[now].size();++i){
        int y=g[now][i];
        if(!vis[y])color(y,3-co);
        else if(vis[y]==vis[now])ok=1;
    }
}

二分图的最大匹配问题 给定一个二分图 G，求选出一些边，使得这些边没有公共顶点，且边的数量最大。

匈牙利算法 对于每个点 x，枚举其邻点 y。

对于 y：

1. 若 y 已被访问，即 y 已经增广完毕，跳过。

2. 若 y 没有匹配，则将 y 的匹配记为 x，增广 y。

3. 若 y 有匹配 z，但是 z 仍能够继续增广，则同 2。

时间复杂度 \mathrm{O}(nm)。

代码：

bool mc(int x){
    for(int i=0;i<d[x].size();++i){
        int y=d[x][i];
        if(!vis[y]){
            vis[y]=1;
            if(!p[y]||mc(p[y])){
                p[y] = x;
                return true;
            }
        }
    }
    return false;
}

网络流模型求解 考虑新建立超级源点 s,t，对于 \forall x\in V_1,f(s,x)=1，对于 \forall x\in V_2,f(x,t)=1，对于 (u,v)\in E (默认 u\in V_1,v\in V_2)，f(u,v)=1。

在原图跑最大流，增广完毕后剩余容量为 0 的，形如 f(u,v) 的边即是匹配边。

时间复杂度 \mathrm{O}(m\sqrt n)。

代码有点长，就不放了，反正板子网上一大堆。

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

König 定理 二分图的最小点覆盖 = 二分图的最大匹配。

证明略，见 OI-wiki。

二分图的最大独立集 选最多的点，满足两两之间没有边相连。

定理 二分图的最大独立集 = 点数 - 最小点覆盖。

证明 对于最小点覆盖，每个边至少被选了一个点，对于其补集，每个边最多被选了一个点，满足两两之间无边相连，同时这种情况一定为最优的。

二分图最大权匹配 二分图中边权和最大的匹配。

KM 算法 待更新。

费用流模型求解 在模型中跑最大费用最大流即可。

P1525 显然若二分图 G=(V,E)，那么其子图 G'=(V,E'),E'\subseteq E 也为二分图，按边权排序，二分答案，判定前 k 条边是否组成二分图。

P6185 令 c_i=a_i-b_i，则操作转化为如何使 \forall c_i=0。