二分图

naoliaok_lovely · 2023-08-14 14:18:03 · 算法·理论

定义

把原图分为两个点集 X,Y，那么所有的边 (x,y) 均满足 x\in X,y\in Y。

判定

充要条件：是否存在奇环。
方法：染色法。

二分图最大匹配

选取最多的边，使得这些边没有公共点。

方法：匈牙利算法（寻找增广路）。

bool dfs(int x)
{
    for(int i = h[x]; i; i = ne[i])
        if(!vis[e[i]])
        {
            int j = e[i];
            vis[j] = 1;
            if(!link[j] || dfs(link[j]))
            {
                link[j] = x;
                return 1;
            }
        }
    return 0;
}

其中，传入的 x 始终为左侧点，对应的 j 即为右侧点。vis 表示本次匹配中右侧点是否被遍历过，link 表示右侧点相连的左侧点。时间复杂度 O(nm)。（和网络流一样，这个时间复杂度基本上是跑不满的）

扩展：Hopcroft-Karp 算法——多路增广。（每次都寻找互不相交的增广路，可以将复杂度降到 O(m\sqrt n)）
另：对于二分图匹配问题，通常会用速度更快的网络流算法实现。

bfs 实现

由于上述的 HK 和网络流都太过麻烦，于是出现了匈牙利的 bfs 实现形式，可以砍掉一个很大的常数，这些优化基本上足够我们通过题目了。

bfs 的队列中与 dfs 中的 x 变量类似，即只包含二分图中同一集合的点。实现时每一个点存一个前驱 pre 用于回溯，当找到增广路时立即回溯即可。
代码来源

void aug(int v){
    int t;
    while(v){
        t=px[pre[v]];
        px[pre[v]]=v;
        py[v]=pre[v];
        v=t;
    }
}
bool bfs(int s){
    memset(pre,0,sizeof(pre));
    memset(vx,0,sizeof(vx));
    memset(vy,0,sizeof(vy));
    q[hh=tt=1]=s;
    int u;
    while(hh<=tt){
        u=q[hh++];
        vx[u]=1;
        for(int v:G[u]) if(!vy[v]){
            vy[v]=1;
            pre[v]=u;
            if(!py[v]) return aug(v),1;
            q[++tt]=py[v];
        }
    }
    return 0;
}

霍尔(Hall)定理

设二分图两端点集为 X 和 Y，且 |X|\le|Y|，则其最大匹配为 |X| 的充要条件是：|X| 中任意 k(1\le k\le|X|) 个点都与 Y 中至少 k 个点相连。
证明：归纳法。

推广：设二分图两端点集为 X 和 Y，且 |X|\le|Y|，则其最大匹配为 |X|-\max\limits_{A\subseteq X}\{|A|-|R(A)|\}，其中 R(A) 表示 |X| 中与 |Y| 相连点的并集。

相关模型

1.最小点覆盖

选取最少的点，使得每条边都至少有一个端点被选。

Konig定理

在二分图中，最大匹配等于最小点覆盖。
证明就不写了，可以参考这篇文章。值得注意的是，Konig定理给出了最小点覆盖的构造。

void konig(int x)
{
    for(int i = h[x]; i; i = ne[i])
        if(flag[e[i]])
        {
            int j = e[i];
            flag[j] = 0;
            if(link[j] && flag[link[j]])
                flag[link[j]] = 0, konig(link[j]);
        }
}

int main()
{
    for(int i = 1; i <= m; i++)
    {
        flag[i] = 1;
        if(link[i]) flag[link[i]] = 1;
    }
    for(int i = 1; i <= n; i++)
        if(!flag[i]) konig(i);
    for(int i = 1; i <= n; i++)
        if(flag[i]) printf("%d ", i);
    puts("");
    for(int i = 1; i <= m; i++)
        if(!flag[i]) printf("%d ", i);
}

2.最大独立集

选取最多的点，这些点两两之间无边相连。

Tips：\color{red}\text{最大独立集}\color{black}\text{与}\color{green}\text{最小点覆盖}\color{black}\text{互补！}

3.最大团

选取最多的点，这些点两两之间都有连边。（构成完全图）

Tips：\color{red}\text{最大团}\color{black}\text{等于补图的}\color{green}\text{最大独立集}\color{black}\text{！}

4.DAG 最小路径划分

在有向无环图（DAG）中，使用最少的不相交（无公共点）路径，覆盖每一个顶点。

步骤：

原图中每个点 u 拆成 2 个点 u 和 u'。
对原图中一条边 (u,v)，新图中连边 (u,v')。
原图最小路径划分 =n- 新图最大匹配。

即把原图的每个点都分为入和出。

5.DAG 最小路径覆盖

在有向无环图（DAG）中，使用最少的路径，覆盖每一个顶点。

先用 floyd 传递闭包，原问题即变为了最小路径划分。

6.有向图环覆盖

在有向图中，选择 n 条边，使得每个点都在一个有向环中。

与 DAG 最小路径划分同样的构图，新图中的完美匹配则对应一种方案。

7.狄尔沃斯(Dilworth)定理

任意偏序集（例如：DAG）最小路径划分等于最大反链。（反链：类似与无向图中的独立集，指任意两个元素之间无路径（有向）相连。）

upd20231013：加入了 bfs 写法。