二分图 学习笔记

发表于 | 分类于 | | + s

模板及讲解

二分图相关定义

二分图：对于某无向图 ，若它的顶点可以划分为两个互不相交的子集 ，且每条边的两端点分别属于两子集 ，则称该图为二分图
（二分图）匹配：选择一个 边集 ，使得任意边 不存在重复的顶点 ，称该边集为该（二分）图的一个 匹配 。
极大匹配：对于一个匹配，若无法在原图中找到任意边加入匹配，则称该匹配为一个极大匹配。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配 。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边 …形成的路径叫 交替路 。
增广路：对于一条路径，从一个未匹配点出发，走交替路，终止于另一个未匹配点 ，则这条交替路称为增广路

增广路的性质：
1、具有奇数条边
2、起点和终点均为未配对点
3、整条路径上奇数边均不在原匹配中，偶数边均在原匹配中

二分图的最大匹配

普通网络流做法$O(n \sqrt{m})$：
dinic虽是$O(n^2m)$的，但是做二分图被证明了复杂度为$O(n \sqrt{m})$，详情做法看最大流最小割 算法笔记

匈牙利算法做法$O(nm)$：
算法思路大致为(具体实现看相关代码)：先枚举每个左边点DFS找右边点匹配，如果当期右边点没有被匹配，就匹配；如果被匹配了，就继续DFS这个右边点匹配的左边点找另外的点匹配，如果找得到，就完成匹配；找不到，就不能够匹配了
比较”专业”的说法：
找到一未配对点$ u$，从 $u $为端点的边中任选一条尝试配对（令其另一端点为$ v$），若此时$ v$ 未配对，则配对成功，答案更新。若点$ v$ 已经被配对，就尝试从$ v $出发“扩展”该交替路，执行递归操作，尝试找到一条增广路，若成功，对该增广路取反，即回溯更新配对关系。若失败，则尝试换一条以 $u$ 为端点的边重复操作，直至$ u$ 配对成功或全部尝试过为止。
对所有剩下的未配对点进行操作，直至尝试完毕所有点，找不到增广路为止，此时找到原图最大匹配~

二分图的最小点覆盖
定义：假如选了一个点就相当于覆盖了以它为端点的所有边。最小顶点覆盖就是选择最少的点来覆盖所有的边。
解法：二分图最大匹配 $=$ 二分图最小点覆盖(König 定理)
因为如果该图还会有边没覆盖到，二分图的当前匹配就不是最大匹配。因为二分图匹配必须有一条边的两端都能让出位置才能匹配。
二分图的最大独立集
定义：选出一些顶点使得这些顶点两两不相邻，则这些点构成的集合称为独立集。找出一个包含顶点数最多的独立集称为最大独立集。
解法：最大独立集 $=$ 所有顶点数 $-$ 最小顶点覆盖(匈牙利算法：最大独立集 $=$ 所有顶点数 $-$最小顶点覆盖$/2$，因为匈牙利算法是针对有向边的而最大独立集的边是无向边)
这个比较显然， 最小顶点覆盖把所有边的一个顶点都算上了，其他点不会再有相邻的
二分图的最大团
定义：对于一般图来说，团是一个顶点集合，且由该顶点集合诱导的子图是一个完全图，简单说，就是选出一些顶点，这些顶点两两之间都有边。最大团就是使得选出的这个顶点集合最大。对于二分图来说，我们默认为左边的所有点之间都有边，右边的所有顶点之间都有边。那么，实际上，我们是要在左边找到一个顶点子集X，在右边找到一个顶点子集Y，使得X中每个顶点和Y中每个顶点之间都有边。
解法：二分图的最大团 $=$ 补图的最大独立集
补图的定义：对于二分图中左边一点$x$和右边一点$y$，若$x$和$y$之间有边，那么在补图中没有，否则有。
因为最大独立集是两两不相邻，所以最大独立集的补图两两相邻。
DAG的最小不相交路径覆盖
定义：在一个有向图中，找出最少的路径，使得这些路径经过了所有的点，且这些路径不可以相交。不相交即任何一个顶点有且只有一条路径与之关联。
解法：把一个点$A$拆成$A_1, A_2$，如果$A->B$，那么$A_1->B_2$。然后对新图进行二分图最大匹配，答案为 原图的节点数 $-$ 新图的二分图最大匹配
因为先假设图中的点都是独立的一条路径，而二分图最大匹配的过程就是把这些路径连起来。
DAG的最小可相交路径覆盖
定义：在一个有向图中，找出最少的路径，使得这些路径经过了所有的点，这些路径可以相交。
解法：算出图的连通性$G$，把一个点$A$拆成$A_1, A_2$，如果$G(A, B) = 1$，那么$A_1->B_2​$，转化为DAG的最小不相交路径覆盖
(以上部分内容转自此处或此处)

Dilworth 定理

参见Luogu 4934

模型

行列匹配法(连边代表点思想)
有很多箭，每根箭可以杀死一行或者一列的敌人，我们要杀死所有的敌人至要用到几根箭？
解：每个敌人的坐标$(x, y)$建图，由左边$x$连向右边$y$，然后求最小顶点覆盖即可。
因为这个图中的一条边$(x, y)$相当于原来的$(x, y)$处的敌人，所以覆盖所有边即可以全部杀死。
例题: Bzoj 1059, caioj 1126

黑白染色法(匹配思想)
给出一个网格图，棋盘有些格子是不能放东西的。现在要判断在所以可以放东西的格子上是否能用$1 \times 2$的小方块填满。
解：将图黑白染色，即相邻的格子颜色不同(黑白相间)。本题就是相当于将白格和黑格进行匹配，连边二分图，然后求出最大匹配即可。但是最大匹配后可能还会有$1 \times 1$的小方块不在匹配中，要验证答案。
例题: poj 2446

反建法(逆向思维)
也就是依据题目要求的答案反着建图。

拆点法
见最小路径覆盖。

一行变多行，一列变多列法
例题: Hdu 1045

常见题型

1、求二分图的最大匹配
Q: 给定一个二分图，求它的最大匹配
解: 见解析
例题:Bzoj 1191
2、求二分图最小点覆盖
Q: 给定一个二分图，求它的最小点覆盖
解: 见解析
例题:caioj 1125
3、求二分图的最大独立集
Q: 给定一个二分图，求它的最大独立集
解: 见解析
例题:
4、二分图的最大团
Q: 给定一个二分图，求它的最大团
解: 见解析
例题:
5、DAG的最小不相交路径覆盖(拆点)
Q: 给定一个DAG图，求它最小不相交路径覆盖
解: 见解析
例题:Bzoj 2150
6、DAG的最小可相交路径覆盖(拆点)
Q: 给定一个DAG图，求它最小可相交路径覆盖
解: 见解析
例题:
7、行列匹配法(模型, 以上题型为基础题型)
Q: 有很多箭，每根箭可以杀死一行或者一列的敌人，我们要杀死所有的敌人至要用到几根箭？
解: 见解析
例题: Bzoj 1059, caioj 1126
7、黑白染色法
Q: 见解析
解: 见解析
例题: poj 2446
8、反建法
Q: 见解析
解: 见解析
例题:
9、拆点法
Q: 见解析
解: 见解析
例题: Bzoj 2150
10、一行变多行，一列变多列法
Q: 见解析
解: 见解析
例题: Hdu 1045

二分图匈牙利算法(Bzoj 1191)：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000 + 5;
int cnt, n, m, lk[MAXN], vis[MAXN];
//lk[u]=i: 右边的u点被左边的i点匹配
//vis[u]=i: 第i轮左边的u点被尝试更改(不设为bool是因为这样免去每次重置数组)
vector<int> G[MAXN];
//记录左边点->右边点的边 
bool hungary(int u) {
    for (int i = 0; i < G[u].size(); i++) {//枚举每个右边的点匹配 
        int v = G[u][i];
        if (vis[v] != cnt) {//尝试修改过的节点就不需要遍历了
            vis[v] = cnt;
            if (!lk[v] || hungary(lk[v])) {
            //如果枚举的右边点没被匹配，就可以直接匹配。如果已经被匹配了，那么就让之前
            //匹配这个右边点的左边点去匹配另一个点，让这个点去匹配这个右边点。
            //这里运用了||的性质，||左边如果为true就不在执行||右边的表达式 
                lk[v] = u;
                return true;//成功匹配 
            }
        }
    }
    return false;
}
void clean() {
    for (int i=0;i<=max(n, m);i++) vis[i] = lk[i] = 0, G[i].clear();
}
void solve() {
    clean();
    for (int a, b, i = 1; i <= m; i++) {//可以把u, v压行qwq
        scanf("%d%d", &a, &b);
        G[i].push_back(a), G[i].push_back(b);
    }
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        if (hungary(cnt = i)) ans++; else break;//枚举每个左边的点匹配，如果一道题不能做出来就要break，因为不能进入下一关了，而正常二分图最大匹配这样写是不行的 
    }
    printf("%d\n", ans);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    scanf("%d%d", &n, &m), solve();
    return 0;
}
------ 本文结束 ------