二分图

文章发布时间:

最后更新时间:

一个图是二分图 <=> 染色法存在矛盾 <=> 图中不存在奇数环

（通过染色法可以想到棋盘，树，DAG）

匹配：“一夫一妻”

最大匹配：一个二分图中边数最多的一组匹配

增广路径：（对于一个匹配来说）始于非匹配点且终于非匹配点（除了起始的点）的由匹配边与非匹配边交错而成路径。增广路中边的数量是奇数，所以这两个匹配点一定是不同边。

最大匹配<=>此匹配不存在增广路径

匈牙利算法：

遍历每一个男的，看他喜欢的女生的男朋友能不能再找一个，好让他们两个在一起

用到了递归，就是看那个男朋友能不能再找一个的时候用到的算法是一样的（find）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
if (!vis[j])
        {
vis[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    
    return false;
}
int main() {
for (int i = 1; i <= M; ++i) // 遍历二分图的一边
    {
        memset(vis, 0, sizeof(vis)); //重置vis数组
if (find(i)) cnt++;
    }
    return 0;
}

*下面的遍历是指main函数中的，只有M次

其实本质上是每次遍历找一条增广路径

（遍历过的男的不一定是匹配点，但男的匹配点一定被遍历过，因为只有被遍历的时候男的会变成匹配点）

记得每次遍历的时候标记一下vis（因为这个点向外扩展的方式的唯一的）

  • 最小点覆盖：选出最少的点，使得每一条边的端点至少有一边被选
  • 二分图中 最小点覆盖 = 最大匹配数 ！
  • 最大独立集：选出最多的点，使得选出的任意两点之间没有边 => 去掉最少的点，把所有的边破坏掉 => 最小点覆盖
  • 最大团：选出最多的点，使得选出的任意两点之间都有边（即补图的最大独立集）
  • 最小路径点覆盖：用最少的互不相交的路径将所有点覆盖
    • 针对有向无环图
    • 不是边，是几条路径
    • 不一定能找到可行解
    • = 点数 - 拆点后的最大匹配数
    • 方法：拆点（拆成出点和入点 => 二分图） 不相交 =>（拆点后的）匹配
  • 最小路径重复点覆盖：
    • 传递闭包后图G‘做最小点覆盖
    • 原图G的每一个路径重复点覆盖 都对应 G'中的一个路径点覆盖，且路径数目相同；G'中的一个路径点覆盖 都对应 原图G的每一个路径重复点覆盖，且路径数目相同
  • 例：acwing379. 捉迷藏
    • 题目：一个有向无环图，问最多选多少个点，使得两两之间没有路径连接
    • 题解：即传递闭包只有的最大独立集