Skip to content

二分图学习笔记

笔记856 字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

定义

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

性质

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

判定

定理

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

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

代码

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 是右部点个数。

代码实现

#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 日。