二分图的定义
二分图是指将图中所有点分为两个集合，任意一条边对应的两个点都不在同一个集合中。
二分图的判定
判定一个图是否为二分图，是考虑这个图中是否有奇数环，如果不存在奇数环，则图为二分图。
具体的判定方法可以使用染色法。
vector<int> g[N];
const int N = 100010;
int color[N];
bool dfs(int u, int c) {
color[u] = c;
for (int v: g[u])
if (color[v] == 0) {
if (!dfs(v, 3 - u)) return false;
} else if (color[v] != color[u]) {
return false;
}
return true;
}
bool ans = true;
for (int i = 1; i <= n; ++i)
if (color[i] == 0) {
if (!dfs(i, 1)) {
ans = false;
break;
}
}
if (ans) puts("This graph is biparite graph.");
else puts("This graph is not biparite graph.");
二分图判定模板题：860. 染色法判定二分图
二分图判定的练习题：257. 关押罪犯
二分图的最大边匹配
对于一个二分图，分为集合
S
S
S 和 集合
T
T
T。
选择最多的边，使得这些边对应的点各不相同。
那么解决这个问题的就是匈牙利算法，这也是接下来解决问题的重点算法。
int match[N];
int st[N];
int g[N][N];
bool hungarian(int i) {
for (int j = 1; j <= n; ++j) {
if (g[i][j] && !st[j]) {
st[j] = true;
if (match[j] == 0 || hungarian(match[j])) {
match[j] = i;
return true;
}
}
}
return false;
}
int res = 0;
for (int i = 1; i <= n; ++i)
if (hungarian(i)) res += 1;
printf("二分图的最大边匹配为：%d\n", res);
解释一下上面的几个数组：
-
g[i][j] 是邻接矩阵存储的图
-
match[j] 表示 T 中的点 j 匹配边的
S
S
S 中的点。
-
st[j] = true 表示第 j 个点已经被其他人考虑了，暂时不能考虑。
一个例子：如果有边 1-4，1-5，2-4。对应的集合 S = {1, 2}，集合 T = {4, 5}。
首先 S1 与 T4 匹配，接着来考虑 S2 要匹配的点，S2 只能与 T4 匹配，所以考虑 T4 目前匹配的点 S1 是否可以匹配其他边。幸运的是 S1 可以匹配 T5 ，从而把 T4 让出来。
但是我们需要考虑在算法的枚举过程中，如果 st[4] == false ，则在使得 T4 目前匹配的点 S1 考虑其他边时，从小到大，其总会先看到 T4 ，如此陷入一个死循环。
二分图最大边匹配的识别：372. 棋盘覆盖
二分图的最小点覆盖
对于一个二分图，分为集合
S
S
S 和 集合
T
T
T。
选择最少的点，使得其可以覆盖所有的边。（覆盖一条边是指，一条边对应两个点，其中至少有一个点被选择）
一个结论：二分图的最大边匹配 = 二分图的最小点覆盖数，懒得证明了。
二分图最小点覆盖的识别：376. 机器任务
二分图的最大独立集与最大团
对于一个图，分为集合
S
S
S 和 集合
T
T
T，选择最多的点，但是这些点中任意两个点都不存在一条边，这个点集就是最大独立集。
对于一个图，分为集合
S
S
S 和 集合
T
T
T，选择最多的点，使得任意两点之间都存在边，这些点和他们之间的边构成了一个完全图，这个完全图叫作团，选择最多的点满足这个条件，这些点和他们之间的边构成了一个最大团。
在二分图中有一些结论：二分图的最大独立集 = 点数 - 二分图的最小点覆盖。
简单证明下：二分图的最大独立集是指选择最多的点，两两点之间内部不存在边。等价于 “去掉最少的点，将所有边都破坏掉”，即选择最少的点，覆盖所有的边，对应的就是二分图的最小点覆盖。
二分图的最大独立集识别：378. 骑士放置
二分图的最小路径点覆盖和最小路径重复点覆盖
对于一个有向无环图（DAG） ，二分图的最小路径点覆盖是指找到最少的路径，选择的路径之间不存在交点，使得覆盖所有点。
一个结论：二分图的最小路径点覆盖 = 点数 - 二分图的最大边匹配
简单证明：
假设现在有 5 个点，我们建立如下的图，如果从 1 点有一条向 2 点的边，那么我们在下面这个图中从 1 点向 2’ 点连一条边。
对于一个路径来说，其只有一个终点，这个终点没有出边，即对于所有的出点来说，找到所有没有向入点连边的出点，这就是路径数。
故我们需要找到最少的出点，等价于我们需要找到尽可能多的出点都有匹配边，即找到最大边匹配，减去这些有匹配边的出点，剩余的没有匹配边的出点就是路径的终点。
1 1'
2 2'
3 3'
4 4'
5 5'
出点 入点
二分图的最小路径重复点覆盖，可以通过传递闭包，转换为二分图的最小路径点覆盖。
我们现在有路径 x->y->z，但是 x->y 和 y>z 都已经被走过，那么对于这条路径，剩余价值为 x->z 没走过，将这条边加入到图中。
而传递闭包就是指：x->y & y->z ==> x->z 即 x->y 以及 y->z 可以推导出 x->z
二分图的最小路径重复点覆盖、二分图的最小路径点覆盖识别
总结
- 二分图等价于：图中不存在奇数环，等价于染色法不会有矛盾
- 匈牙利算法求解二分图最大边匹配
- 二分图的最大边匹配 = 二分图的最小点覆盖 = 二分图总点数 - 二分图的最大独立集 = 点数 - 二分图的最小路径点覆盖
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
