二分图学习笔记

a_gold_TomAndJerry · 2025-11-23 12:41:28 · 个人记录

1.什么是二分图

如果图 G=(V,E) 的顶点集 V 可以分为两个互不相交的子集 X 和 Y，使得每条边 e\in E 的两个端点都分别属于 X 和 Y，就称图 G 是一个二分图。集合 X 和 Y 常称作它的两个部分，或者分别称为二分图的左部和右部。

这是 OI Wiki 上的解释，简单说就是当一个图的所有顶点可以分成两个集合，使得每个集合中不存在两个顶点之间有边，这个图就是二分图。

举个例子：

可以看到左边的三个顶点间是没有边的，右边也如此。所以这个图就是二分图。

不难看出，可以给这个二分图进行黑白染色，即左边全染成白色，右边全染成黑色。

由于这个性质，可以得出一个结论：在二分图中不存在奇数长度的环。因为无论从哪个颜色节点的顶点开始，它的邻居节点都是与他异色的。所以每走一步就会换一次颜色。若想要再次回到这个节点，就必须走偶数长度的环。

2.二分图染色

因为二分图能被黑白染色，所以可以通过黑白染色来判断一个图是否是二分图。

大体思路如下：

• 遍历所有顶点，若出现未被染色的顶点，就说明存在未被染色的连通分量。
• 任选一种颜色给这个顶点染色，并以它为起点做 DFS 或 BFS。
• 若走到了一个未被染色的顶点，将其染上与前一个顶点相反的颜色。
• 若走到了一个被染色的点，如果它的颜色与前一个顶点相反，则继续遍历；如果相同，则证明这个图不是二分图。

找个板子题来具体说明一下：封锁阳光大学。

将放或不放河蟹看做黑白两种颜色，并对图进行染色。再把黑看做放河蟹和把白看做放河蟹的两种情况进行比较，取最小值，这些最小值的和就是答案。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
vector<int> G[maxn];
int n,m,ans=0,c[maxn],sum=0; 
bool flag[maxn];
void DFS(int u,int k){  //染色
    if(c[u]==k) return;  //如果与前面顶点颜色不同
    if(c[u]!=-1){  //如果与前面顶点颜色相同
        cout<<"Impossible";
        exit(0);
    }
    c[u]=k;  //染色
    flag[u]=1;
    sum++;
    for(int i:G[u]) DFS(i,k^1);  //遍历并改变颜色
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    memset(flag,0,sizeof(flag));
    for(int i=1;i<=n;++i){
        if(flag[i]) continue;
        sum=0;
        memset(c,-1,sizeof(c));  //用时间戳更好，但用memset能刚好AC
        DFS(i,0);
        int p=0;
        for(int i=1;i<=n;++i) p+=c[i]==1;
        ans+=min(p,sum-p);  //白或者黑
    }
    cout<<ans;
    return 0;
}

3.最大匹配（匈牙利算法）

如果对于边的全集中有一个子集满足其中任意两条边没有公共顶点，则称这个子集为这个图的一组匹配。可以理解为当且仅当一个顶点与另一个顶点有边。在二分图中，可以把匹配理解为在一组匹配中，左边的顶点只有一个右边的顶点有边。

在所有匹配中，包含边数最大的一个匹配被称为最大匹配。显然，在二分图中最大匹配边数不大于二分之一的顶点数。

求最大匹配的核心思想其实就是 DFS。

大体思路如下：

• 遍历每一个左边的顶点。
• 遍历每个左边顶点与右边顶点连的所有边。
• 如果当前访问的右边顶点未被匹配，则暂时将它们匹配。
• 如果当前访问的右边顶点已被匹配，让原本与其已经匹配的左侧顶点重新匹配。若那个左侧顶点存在额外的匹配，则将其与新的右侧顶点暂时匹配，现在的左侧顶点与现在被访问的右侧顶点暂时匹配。若不存在新的匹配，则遍历下一条边，直到遍历结束为止。

可能说的不太清楚

如果没有看懂可以去看看这篇文章。

模板题：二分图最大匹配。

我们可以根据以上思路写出代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,e,r[505],ans=0;  //r[i]表示第i个右边顶点与哪个左边顶点匹配
bool G[505][505],used[505];  //used[i]表示这个左边顶点与第i个右边顶点是否匹配
bool find(int x){
    for(int i=1;i<=m;++i){
        if(G[x][i]&&!used[i]){  //遍历边
            used[i]=1;
            if(r[i]==0||find(r[i])){  //如果为匹配或者能被腾出
                r[i]=x;  //匹配
                return true;
            }
        }
    }
    return false;
}
int main(){
    scanf("%d%d%d",&n,&m,&e);
    for(int i=1;i<=e;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        G[x][y]=1;
    }
    for(int i=1;i<=n;++i){  //遍历顶点
        memset(used,0,sizeof(used));
        if(find(i)) ans++;  //如果能匹配，总长度增加
    }
    cout<<ans;
    return 0;
}

例题：座位安排。

这道题几乎是个板子，但是要注意，每排有两个座位，所以可以考虑将另一列座位安在第一列的尾部，然后就是愉快的打板子。

AC Code：

#include<bits/stdc++.h>
using namespace std;
vector<int> G[4010];
int n,r[4010],ans=0;
bool used[4010];
bool find(int x){
    for(int i:G[x]){
        if(used[i]) continue;
        used[i]=1;
        if(r[i]==0||find(r[i])){
            r[i]=x;
            return true;
        }
        if(used[i+n]) continue;
        used[i+n]=1;
        if(r[i+n]==0||find(r[i+n])){
            r[i+n]=x;
            return true;
        }
    }
    return false;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=2*n;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        G[i].push_back(x);
        G[i].push_back(y);
    }
    for(int i=1;i<=2*n;++i){
        memset(used,0,sizeof(used));
        if(find(i)) ans++;
    }
    cout<<ans;
    return 0;
}

有人说这个算法与网络流有关，可惜我不会。。。