二分图

2024-01-01 13:10:52

二分图:

定义:

二分图的定义就是:所有节点由两个集合组成,而且两个集合内部没有边的图.

换言之,就是存在一种方案让节点划分成满足以上性质的两个集合.

二分图判定:

因为希望两个集合内部没有边,所以试着用黑白两种颜色标记图中的节点,相邻节点标记不同颜色,判断是否会有冲突即可.

二分图最大匹配

定义:

任意两条边没有公共顶点的边 的集合叫做图的一组匹配,在二分图中, 包含边数 最多的一组匹配叫做二分图的最大匹配.

解决:

我们希望匹配数量最多,所以尽量使更多的点能够与二分图另一半相连.

考虑这样一种情况: \(AB,CD\) 形成一个二分图,其中 \(A\) 连接 \(C,D\), \(B\) 连接 \(C\)

一开始,因为遍历的顺序,肯定先 \(A\) 连接 \(C\), 那么 \(B\) 怎么办? 这就需要使用一些算法:

经常使用的是 匈牙利算法.

匈牙利算法:

过程参考了 <<算法竞赛进阶指南>>.

过程为:

设 \(S=\emptyset\), 一开始所有边都是非匹配边.

寻找增广路,把路径上所有边的匹配状态取反得到一个更大的匹配,重复这个操作,直到找到增广路.

寻找增广路:尝试给每一个左部节点 \(x\) 找到一个匹配的右部节点 \(y\). 过程为:

\(y\) 本身为非匹配点,直接匹配即可.

\(y\) 本身为 \(x'\) 匹配,但从 \(x'\) 出发能找到另一个 \(y'\) 与之匹配,此时路径的 \(x\rightarrow y\) , \(x'\rightarrow y'\) 就是一条增广路.

增广路过程:找 \(y\) 对应连接的 \(x'\) ,看是否能和其他点相匹配就行.

代码:

//P3386 【模板】二分图最大匹配
#include<bits/stdc++.h>

using namespace std;
const int N=1e5+5;
int n,m,e;
vector<int> g[N];
int match[N],vis[N],ans;
bool dfs(int x){
    for(auto y:g[x]){
        if(vis[y]) continue;
        vis[y]=1;
        if(!match[y]||dfs(match[y])){//向下探索对应连接点是否能有增广路
            match[y]=x; return true; 
        }
    }
    return false;
}
int main(){
    cin>>n>>m>>e;
    for(int i=1,x,y;i<=e;i++)scanf("%d%d",&x,&y),g[x].push_back(y);
    for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis)); if(dfs(i)) ans++;}
    cout<<ans<<endl;
    system("pause");
    return 0;
}

例题:[SHOI2002]舞会

题意:

给定 \(n\) 人,有 \(m\) 个限制条件要求 \(A,B\) 不能同时出现,求最多出现人的个数.

分析:

观察数据范围,显然暴力的连接不连通的边肯定过不去。因此，有一个定理：

二分图最大独立集 \(=\) (\(n-\) 最小点覆盖) \(=\) (\(n-\) 二分图最大匹配数)

我们首先把左右两边的限制条件建立无向边，然后进行二分图的染色。

这样染色后，我们得到了颜色为 \(1\) 和颜色为 \(2\) 的点。二分图最大匹配要求 \(1\) 和 \(2\) 颜色的点相互连接的最大个数。

利用匈牙利定理。将颜色为 \(1\) 的点跑匈牙利算法即可。得到最大匹配数量为 \(ans\),,答案即为 \(n-ans\).

代码：

#include<bits/stdc++.h>

using namespace std;
const int N=4e4+5;
int n,m;
vector<int> g[1005],a;
int col[N],match[N],vis[N],ans;

void getcol(int x,int c){
    col[x]=c;  
    if(c==1) a.push_back(x);
    for(auto y:g[x]){
       if(!col[y]) getcol(y,3-c);
    }
}
bool dfs(int x){
    for(auto y:g[x]){
        if(vis[y]) continue; vis[y]=1;
        if(!match[y]||dfs(match[y])){
            match[y]=x; return true;
        }
    }
    return false;
}
int main(){
    cin>>n>>m;
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y); x++,y++;
        g[x].push_back(y); g[y].push_back(x);
    }
    for(int i=1;i<=n;i++) if(!col[i]) getcol(i,1);
    for(int i=0;i<a.size();i++){
        memset(vis,0,sizeof(vis)); if(dfs(a[i])) ans++;
    }
    cout<<n-ans<<endl;

    system("pause");
    return 0;
}

[NOI2009] 变换序列

题解

模型：

二分图匹配有两个要素：

节点能分成独立的两个集合，每个集合内部没有边
每个节点只能与一条匹配边连接。

我们需要寻找题目中这种性质，就能利用二分图匹配解决问题。

二分图的最小点覆盖——\(konig\) 定理

~~找不到那个 \(o\) 上带两个点的先用 \(o\) 吧...~~

问题：

给定一张二分图，求出一个最小的点集 \(S\) ，使得图中任意一条边都有至少一个端点属于 \(S\) 。这个问题被称为二分图的最小点覆盖。

定理：

二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数

最大匹配是原来二分图边集的一个子集，并且所有边都不相交，所以至少需要从每条匹配边中选出一个端点。

因此，最小点覆盖包含的点数不可能小于最大匹配包含的边数。

如果能对二分图构造出一组点覆盖，其包含的点数等于最大匹配包含的边数，那么就能证明这个定理。

构造方法：

求出来二分图最大匹配
从左部每个非匹配点出发，再执行一次 \(dfs\) 寻找增广路的过程（一定会失败），标记访问过的节点。
取 左部没有被标记的点和右部被标记的点，就得到了二分图最小点覆盖。

例题：

UVA1194 Machine Schedule

题意：

有两台机器分别有 \(n,m\) 种模式，现在有 \(k\) 个任务，对于每个任务 \(i\) ，给定两个整数 \(a_i,b_i\) ，如果任务在 \(A\) 执行，模式设置为 \(a_i\), \(B\) 为 \(b_i\).

需要求出来 \(a,b\) 转换次数最小值。

分析：

二分图最小覆盖的模型特点则是：每条边有两个端点，两者至少选择一个端点。

在这道题中，每个任务要么在 \(A\) 上使用 \(a_i\), 要么在 \(B\) 上使用 \(b_i\)

我们可以把机器 \(A\) 的 \(m\) 种模式作为 \(m\) 个左部点，\(B\) 作为右部点。

每个任务作为无向边，连接左部的 \(a[i]\) 个节点和右部的第 \(b[i]\) 个节点。

用尽量少的模式，处理出来所有的任务，就是 二分图的最小覆盖。

题意：

//UVA1194 Machine Schedule
#include<bits/stdc++.h>

using namespace std;
const int N=1e5+5;
int n,m,k;
vector<int> g[N];
int a[N],b[N],ans,vis[N],match[N];

bool dfs(int x){
    for(auto y:g[x]){
        if(vis[y]) continue;
        vis[y]=1;
        if(!match[y]||dfs(match[y])){
            match[y]=x; return true;
        }
    }
    return false;
}
void init(){
    for(int i=0;i<=1005;i++) g[i]=g[N-1];
    for(int i=0;i<=1005;i++) vis[i]=match[i]=0; ans=0;
}

int main(){
    while(1){
        cin>>n;if(n==0) break; cin>>m>>k;
        for(int i=1,t,x,y;i<=k;i++){
            scanf("%d%d%d",&t,&x,&y); if(x==0||y==0) continue;
            g[x].push_back(y+n); g[y+n].push_back(x);
        }
        for(int i=0;i<n;i++){
            memset(vis,0,sizeof(vis)); if(dfs(i)) ans++;
        }
        printf("%d\n",ans);
        init(); 
    }
    // system("pause");
    return 0;
}

二分图最大独立集：

定义：

给定一张无向图 \(G=(V,E)\)，满足以下条件的点集 \(S\) 叫做图的独立集。

\(S\in V\)
\((x,y)\notin E\)

定理：

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

这个其实很好证明，直接用就行了。

有向无环图的最小点覆盖

定义：

给定一个有向无环图，要求用尽量少的不相交的简单路径，覆盖无向图的所有顶点，这个问题被称为无向图的 最小路径覆盖

定理：

首先需要把这个有向无环图转化一下：把第 \(i\) 个点拆成 \(i\) 和 \(i+n\)，对于每个连边 \((x,y)\) ，连接 \((x,y+n)\)，最终得到的图叫做 拆点二分图

最小点覆盖包含的路径条数，等于 \(n\) 减去拆点二分图的最大匹配数。

码农公寓