图论——二分图 学习笔记

定义

二分图，又称二部图，英文名叫 Bipartite graph。

定义为，一个图，可以将节点划分为两个集合，而集合内部没有相连的边。如图：

性质

1. 如果对二分图黑白染色，那么每条边两边对应的一定是一个黑点、一个白点；
2. 不存在长度为奇数的环，因为只有偶数条边，才能从一个集合回到这个集合。

判定

有两种方法。

第一种是根据性质 \(2\)，我们可以 DFS 或 BFS 遍历这张图，如果发现奇环，说明不是二分图。

另一种方法是染色法，即，我们设每个节点有三种状态 \(0/1/2\)，分别表示「未被染色」「被染成黑色」「被染成白色」，显然当我们把一个节点染成颜色 \(x\)，那么与它相邻的节点只能被染成 \(3-x\) 颜色，如果在染色过程中发现不匹配，则说明不是二分图。

代码：

struct {
    bool check(graph_t &e) {
        int n = e.n; vector<int> col(n + 1);
        function<bool(int, int)> dfs = [&] (int u, int c) {
            col[u] = c; for (int v : e.g[u]) {
                if (col[v] == c) return false;
                else if (col[v]) continue;
                if (!dfs(v, 3 - c)) return false;
            } return true;
        }; rep(i, n) if (!col[i + 1] && !dfs(i + 1, 1)) return false;
        return true;
    }
} bi_graph;

二分图最大匹配

不大会。

练习题

见：https://www.luogu.com.cn/training/419020

Reference

[1] https://oi-wiki.org/graph/bi-graph/
[2] https://www.luogu.com.cn/blog/ilibilib/solution-at-abc327-d