跳转至

二分图最大匹配 (Bipartite Matching)

如果一个图的所有顶点可被划分为两个互不相交的集合 \(U\) 和 \(V\)，使得每条边的两端点分别属于不同的集合，则称该图为二分图 (Bipartite Graph)。

  • 匹配 (Matching)：图中的一个边集，其中任意两条边都没有公共顶点。
  • 最大匹配 (Maximum Matching)：包含边数最多的匹配。

1. 二分图判定 (染色法)

无向图为二分图的充要条件是：图中不存在奇数长度的环 (奇环)。可用黑白双色进行 DFS 染色判定（时间复杂度 \(\mathcal{O}(V + E)\)）。

#include <vector>

bool is_bipartite(int n, const std::vector<std::vector<int>> &adj) {
    std::vector<int> color(n, 0); // 0: 未染色, 1: 黑色, 2: 白色

    for (int i = 0; i < n; ++i) {
        if (color[i] != 0) continue;
        std::vector<int> q = {i};
        color[i] = 1;

        for (int head = 0; head < (int)q.size(); ++head) {
            int u = q[head];
            for (int v : adj[u]) {
                if (color[v] == 0) {
                    color[v] = 3 - color[u]; // 1 -> 2, 2 -> 1
                    q.push_back(v);
                } else if (color[v] == color[u]) {
                    return false; // 出现同色相邻点，存在奇环
                }
            }
        }
    }
    return true;
}

2. 匈牙利算法 (增广路法)

基于 Berge 增广路定理：一个匹配是最大匹配，当且仅当图中不存在关于该匹配的增广路径。

匈牙利算法依次为左半部分的每个节点寻找增广路。若某右侧节点已被占用，则递归尝试为原配偶寻找新的替代匹配。

时间复杂度：\(\mathcal{O}(V \cdot E)\)，代码极短，小规模数据（\(V \le 1000\)）首选。

#include <vector>

struct Hungarian {
    int n_left, n_right;
    std::vector<std::vector<int>> adj; // adj[u] 存储左侧点 u 连接的右侧点 v
    std::vector<int> match_right;      // match_right[v] 存储右侧点 v 匹配的左侧点
    std::vector<bool> vis;

    Hungarian(int n_left, int n_right) 
        : n_left(n_left), n_right(n_right), adj(n_left), match_right(n_right, -1) {}

    void add_edge(int u, int v) {
        adj[u].push_back(v);
    }

    bool dfs(int u) {
        for (int v : adj[u]) {
            if (vis[v]) continue;
            vis[v] = true;

            // 若右侧点未被匹配，或其当前配偶可以找到新的增广路
            if (match_right[v] == -1 || dfs(match_right[v])) {
                match_right[v] = u;
                return true;
            }
        }
        return false;
    }

    int max_matching() {
        int matches = 0;
        for (int u = 0; u < n_left; ++u) {
            vis.assign(n_right, false);
            if (dfs(u)) {
                matches++;
            }
        }
        return matches;
    }
};

3. 大规模数据：转化为网络流求解 (\(\mathcal{O}(E \sqrt{V})\))

对于顶点数较多（如 \(V \ge 5000, E \ge 10^5\)）的二分图，匈牙利算法容易超时。此时可建立网络流模型，使用 Dinic 算法：

  1. 建立虚拟源点 \(S\) 与汇点 \(T\)；
  2. 从 \(S\) 向每个左部点连一条容量为 \(1\) 的边；
  3. 原二分图中的每条边由左向右连一条容量为 \(1\) 的边；
  4. 从每个右部点向 \(T\) 连一条容量为 \(1\) 的边。

网络的最大流值即为二分图的最大匹配数。在单位网络上，Dinic 的运行时间为 \(\mathcal{O}(E \sqrt{V})\)。

经典定理与衍生结论 (柯尼希定理)

在任意二分图中：

  1. 最大匹配数 = 最小点覆盖数 (Minimum Vertex Cover)
  2. 选出最少的点，使得图中每条边都至少有一个端点被选中。
  3. 最大独立集 (Maximum Independent Set) = 总顶点数 - 最大匹配数
  4. 选出最多的点，使得选出的点两两之间没有边。
  5. 最小路径覆盖 (DAG 最小不相交路径覆盖) = 顶点数 - 拆点后二分图最大匹配数