Skip to content

二分图学习笔记

笔记859 字
# 图论 # 二分图
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#定义

一张图 GG 是二分图当且仅当 GG 的点集 VV 可以分为两个点集 V0,V1V_0, V_1，满足 V0∪V1=VV_0 \cup V_1 = V，V0∩V1=∅V_0 \cap V_1 = \emptyset，且对于 GG 的每条边 ee，其两个端点分别属于不同的点集。

#性质

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

#判定

#定理

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

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

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}

#匹配

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

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

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

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

#算法流程

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

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

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

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

#代码实现

C++
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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;
}

#参考资料

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