二分图学习笔记 - Baoshuo's OI Blog

#定义

一张图 $G$ 是二分图当且仅当 $G$ 的点集 $V$ 可以分为两个点集 $V_0, V_1$ ，满足 $V_0 \cup V_1 = V$ ， $V_0 \cap V_1 = \emptyset$ ，且对于 $G$ 的每条边 $e$ ，其两个端点分别属于不同的点集。

#性质

如果将二分图的两个点集中的点分别染成黑色和白色，那么二分图中的每一条边都一定将一个黑色点和一个白色点相连。
二分图内不存在长度为奇数的环。

#判定

#定理

一个无向图是二分图，当且仅当图中不存在长度为奇数的环。

根据二分图的定义，图中的每一条边都从一个集合通往了另外一个集合，显然只有经过偶数条边才能回到同一个集合，故该定理成立。

#代码

C++

bool dfs(int u, int c) {
    color[u] = c;

    for (int v : g[u]) {
        if (color[v]) {
            if (color[v] == c) return false;
        } else if (!dfs(v, 3 - c)) {
            return false;
        }
    }

    return true;
}

bool check() {
    for (int i = 1; i <= n; i++) {
        if (!color[i]) {
            if (!dfs(i, 1)) return false;
        }
    }

    return true;
}

#匹配

图 $G$ 的一个匹配是 $G$ 的一个边集 $E_0$ ，满足 $E_0$ 中的所有边都没有公共端点。

简单来说，一张图的一个匹配就是一些没有公共端点的边。

#二分图最大匹配 —— 匈牙利算法

常用的二分图匹配算法是匈牙利算法，其正确性基于 Hall 定理，本质是不断寻找增广路来扩大匹配数。

#算法流程

将二分图的两个点集划分为「左点集」和「右点集」，并称其中的点为「左部点」和「右部点」。

枚举每一个左部点 $u$ ，然后枚举该左部点连出的边，对于一个出点 $v$ ，如果它没有被先前的左部点匹配，那么直接将 $u$ 匹配 $v$ ，否则尝试让 $v$ 的「原配」左部点去匹配其他右部点，如果「原配」匹配到了其他点，那么将 $u$ 匹配 $v$ ，否则 $u$ 失配。

尝试让「原配」寻找其他匹配的过程可以递归进行。需要注意的是，在每一轮递归中，每个右部点只能被访问一次。

算法的时间复杂度为 $O(n \times e + m)$ ，其中 $n$ 是左部点个数， $e$ 是图的边数， $m$ 是右部点个数。

#代码实现

C++

#include <iostream>
#include <array>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 505;

int n, m, e, tag[N], match[N], ans;
std::array<std::vector<int>, N> g;

bool dfs(int u, int t) {
    if (tag[u] == t) return false;

    tag[u] = t;

    for (int v : g[u]) {
        if (!match[v] || dfs(match[v], t)) {
            match[v] = u;
            return true;
        }
    }

    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> e;

    for (int i = 1, u, v; i <= e; i++) {
        cin >> u >> v;

        g[u].emplace_back(v);
    }

    for (int i = 1; i <= n; i++) {
        if (dfs(i, i)) ans++;
    }

    cout << ans << endl;

    return 0;
}

#参考资料

0x68 二分图的匹配，《算法竞赛进阶指南》（ISBN 978-7-83009-313-6，河南电子音像出版社），李煜东，2019 年 5 月第 5 次修订版。
【2018 五一清北培训】2. 二分图以及匈牙利算法，一扶苏一，2018 年 5 月 1 日。