Wiki › Thuật toán › Luồng mạng (Network Flow) › Ghép cặp tổng quát (Blossom của Edmonds)

Ghép cặp tổng quát (Blossom của Edmonds)

Tìm cặp ghép lớn nhất trên đồ thị vô hướng bất kỳ (không cần hai phía) bằng thuật toán Edmonds: tìm đường tăng bằng BFS và co các chu trình lẻ (bông hoa) thành một đỉnh, O(V^3).

huunguyen huunguyen Updated Tháng 11. 16, 2026 Đọc 14 phút 3 lượt xem

Cặp ghép (matching) của đồ thị vô hướng là tập cạnh không có hai cạnh chung đỉnh. Trên đồ thị hai phía, cặp ghép lớn nhất tìm được bằng Kuhn hay Hopcroft-Karp. Nhưng nhiều bài cho đồ thị tổng quát: ghép đôi người chơi, ghép các ô kề nhau trên lưới có đường chéo, ghép các thành phần liên thông, chọn nhiều cặp (j,j+1) rời nhau nhất. Khi đồ thị có chu trình lẻ, thuật toán hai phía cho đáp án sai. Thuật toán Edmonds (1965, còn gọi là thuật toán bông hoa, blossom) giải đúng bài toán này trong O(V3), đủ nhanh cho V≤500 đến vài nghìn tuỳ mật độ.

Ý tưởng / Trực giác

Định lý Berge. Một cặp ghép M là lớn nhất khi và chỉ khi không tồn tại đường tăng: đường đi đơn giữa hai đỉnh tự do (chưa ghép) mà các cạnh luân phiên ngoài M, trong M, ngoài M, ... Nếu có đường tăng P, lật trạng thái mọi cạnh trên P (lấy hiệu đối xứng M⊕P) cho cặp ghép lớn hơn đúng 1. Ngược lại, nếu M′ lớn hơn M thì M⊕M′ là hợp các đường đi và chu trình xen kẽ, trong đó có một đường có nhiều cạnh của M′ hơn: đó là một đường tăng. Vì vậy thuật toán chỉ cần lặp: tìm đường tăng, lật, cho tới khi hết.

Tìm đường tăng bằng cây xen kẽ. Từ một đỉnh tự do r, BFS dựng cây mà các đỉnh xen kẽ hai nhãn: chẵn (cách r một số chẵn cạnh, gồm r) và lẻ. Từ đỉnh chẵn v xét cạnh v-w không thuộc M:

  • w chưa thăm và tự do: tìm được đường tăng r⤳v−w.
  • w chưa thăm và đã ghép với w′: gán w lẻ, w′ chẵn, đưa w′ vào hàng đợi.
  • w đã là đỉnh lẻ: bỏ qua.
  • w đã là đỉnh chẵn: đây là điểm khác biệt với đồ thị hai phía.

Bông hoa. Nếu cạnh v-w nối hai đỉnh chẵn, đường từ v và từ w lên tổ tiên chung gần nhất b cộng với cạnh v-w tạo thành một chu trình lẻ có 2k+1 cạnh, trong đó k cạnh thuộc M. Chu trình này gọi là bông hoa, b là gốc (base) của nó. Trên đồ thị hai phía tình huống này không xảy ra (mọi chu trình đều chẵn), nên thuật toán Kuhn không cần xử lý.

Vấn đề: trong bông hoa, mọi đỉnh đều có thể là "chẵn" (đi vòng theo chiều này hoặc chiều kia), nhưng BFS thường chỉ gán cho mỗi đỉnh một nhãn, và nhãn lẻ có thể chặn mất đường tăng thật. Định lý co bông hoa (Edmonds): co cả bông hoa B thành một đỉnh duy nhất b thì

G có đường tăng với M⟺G/B có đường tăng với M/B.

Chiều ⇐ là phần dùng trong thuật toán: một đường tăng đi qua đỉnh co b được "nở" ra thành đường trong G bằng cách đi vòng quanh bông hoa theo chiều có số cạnh chẵn từ điểm vào tới gốc. Vì vậy sau khi co, mọi đỉnh của bông hoa trở thành chẵn và được đưa vào hàng đợi.

Cài đặt không co thật. Thay vì dựng đồ thị mới, ta giữ mảng base[v] (gốc bông hoa chứa v). Khi gặp bông hoa qua cạnh v-w: tìm b= lca(v, w), đi từ v và từ w lên b, đặt lại p[] (cha trên cây) theo hướng ngược để sau này lần được đường đi vòng qua bông hoa, gán base[] = b cho mọi đỉnh trong bông hoa và đẩy các đỉnh mới thành chẵn vào hàng đợi. Khi tìm được đỉnh tự do, lần theo p[] và match[] để lật đường tăng.

Ví dụ chạy tay

Đồ thị 6 đỉnh: chu trình lẻ 0−1−2−3−4−0 và cạnh treo 1−5. Cặp ghép hiện tại M={1-2, 3-4} (cạnh đôi), hai đỉnh tự do là 0 và 5:

graph
0 1
0 4
1 5
1 2
4 3
2 3
highlight blue 1-2 4-3

Đường tăng duy nhất là 0−4=3−2=1−5: nó phải đi vòng qua chu trình lẻ để tới 1 từ phía "chẵn".

Tìm kiếm kiểu hai phía thất bại. DFS xen kẽ từ 0 thử 0−1 trước: 1 đã ghép với 2, đi tiếp 2−3, 3 ghép với 4, từ 4 chỉ còn về 0 (đã thăm), bế tắc. Quay lại 0, thử 0−4 nhưng 4 đã bị đánh dấu thăm. Kết luận sai: "không có đường tăng". Lỗi nằm ở chỗ 1 bị gán nhãn lẻ (đến qua cạnh ngoài M), nên không bao giờ đi tiếp từ 1 sang 5 được.

Blossom từ gốc r=0:

bước xử lý kết quả
1 đỉnh chẵn 0, cạnh 0−1 1 lẻ (cha 0), bạn ghép 2 thành chẵn
2 đỉnh chẵn 0, cạnh 0−4 4 lẻ (cha 0), bạn ghép 3 thành chẵn
3 đỉnh chẵn 2, cạnh 2−3 3 cũng chẵn: bông hoa {0,1,2,3,4}, gốc lca(2, 3) = 0; đặt lại cha để 1 đi vòng được qua 2−3−4; 1 và 4 thành chẵn, vào hàng đợi
4 đỉnh 3, 4: mọi láng giềng đã cùng bông hoa bỏ qua
5 đỉnh chẵn 1, cạnh 1−5 5 tự do: tìm được đường tăng

Lần ngược từ 5: 5←1, bạn ghép của 1 là 2, cha (đã đặt lại) của 2 là 3, bạn ghép của 3 là 4, cha của 4 là 0 (gốc tự do). Đường tăng 5−1=2−3=4−0. Lật các cạnh: cặp ghép mới là {0-4, 2-3, 1-5}, kích thước 3, là cặp ghép hoàn hảo. Chương trình bên dưới với đồ thị này in đúng 3 và ba cặp 0 4, 1 5, 2 3 (kiểm tra bằng quy hoạch động bitmask cũng cho 3).

Cài đặt

Chương trình đọc n, m và m cạnh u v (đỉnh từ 0, không có khuyên; cạnh lặp không sao), in kích thước cặp ghép lớn nhất và các cặp.

C++
#include <bits/stdc++.h>
using namespace std;

// Thuật toán Edmonds (blossom) tìm cặp ghép lớn nhất trên đồ thị vô hướng tổng quát, O(V^3).
struct Blossom {
    int n;
    vector<vector<int>> g;
    vector<int> match, p, base, q;     // p: cha trên cây BFS, base: đỉnh gốc của bông hoa
    vector<bool> used, blossom;
    Blossom(int n) : n(n), g(n), match(n, -1), p(n), base(n), used(n), blossom(n) {}
    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // Tổ tiên chung gần nhất của a và b trên cây xen kẽ (đi theo match rồi p)
    int lca(int a, int b) {
        vector<bool> seen(n, false);
        while (true) {
            a = base[a];
            seen[a] = true;
            if (match[a] == -1) break;      // tới gốc cây
            a = p[match[a]];
        }
        while (true) {
            b = base[b];
            if (seen[b]) return b;
            b = p[match[b]];
        }
    }
    // Đánh dấu các đỉnh trên đường từ v lên tới gốc bông hoa b; đặt cha để đi vòng qua bông hoa
    void mark_path(int v, int b, int child) {
        while (base[v] != b) {
            blossom[base[v]] = blossom[base[match[v]]] = true;
            p[v] = child;
            child = match[v];
            v = p[match[v]];
        }
    }
    // BFS tìm đường tăng từ đỉnh tự do root; trả về đỉnh cuối đường tăng hoặc -1
    int find_path(int root) {
        fill(used.begin(), used.end(), false);
        fill(p.begin(), p.end(), -1);
        for (int i = 0; i < n; i++) base[i] = i;
        used[root] = true;
        q.assign(1, root);
        for (size_t qh = 0; qh < q.size(); qh++) {
            int v = q[qh];
            for (int to : g[v]) {
                if (base[v] == base[to] || match[v] == to) continue;
                if (to == root || (match[to] != -1 && p[match[to]] != -1)) {
                    // to là đỉnh "chẵn": cạnh v-to khép một chu trình lẻ, co bông hoa
                    int cur = lca(v, to);
                    fill(blossom.begin(), blossom.end(), false);
                    mark_path(v, cur, to);
                    mark_path(to, cur, v);
                    for (int i = 0; i < n; i++)
                        if (blossom[base[i]]) {
                            base[i] = cur;
                            if (!used[i]) {
                                used[i] = true;
                                q.push_back(i);
                            }
                        }
                } else if (p[to] == -1) {
                    // to là đỉnh "lẻ" mới
                    p[to] = v;
                    if (match[to] == -1) return to;   // to tự do: tìm được đường tăng
                    used[match[to]] = true;
                    q.push_back(match[to]);
                }
            }
        }
        return -1;
    }
    int solve() {
        int res = 0;
        for (int i = 0; i < n; i++)
            if (match[i] == -1) {
                int v = find_path(i);
                if (v != -1) res++;
                while (v != -1) {                 // lật đường tăng
                    int pv = p[v], ppv = match[pv];
                    match[v] = pv;
                    match[pv] = v;
                    v = ppv;
                }
            }
        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    Blossom B(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;                         // đỉnh đánh số từ 0, u != v
        B.add_edge(u, v);
    }
    cout << B.solve() << '\n';
    for (int i = 0; i < n; i++)
        if (B.match[i] > i) cout << i << ' ' << B.match[i] << '\n';
}
Python
import sys


# Thuật toán Edmonds (blossom) tìm cặp ghép lớn nhất trên đồ thị vô hướng tổng quát, O(V^3).
def max_matching(n, g):
    match = [-1] * n

    def lca(a, b, base, p):  # tổ tiên chung gần nhất trên cây xen kẽ
        seen = [False] * n
        while True:
            a = base[a]
            seen[a] = True
            if match[a] == -1:
                break  # tới gốc cây
            a = p[match[a]]
        while True:
            b = base[b]
            if seen[b]:
                return b
            b = p[match[b]]

    def mark_path(v, b, child, base, p, blossom):
        # đánh dấu đường từ v lên gốc bông hoa b, đặt cha để đi vòng qua bông hoa
        while base[v] != b:
            blossom[base[v]] = blossom[base[match[v]]] = True
            p[v] = child
            child = match[v]
            v = p[match[v]]

    def find_path(root):  # BFS tìm đường tăng từ đỉnh tự do root
        used = [False] * n
        p = [-1] * n
        base = list(range(n))
        used[root] = True
        q = [root]
        qh = 0
        while qh < len(q):
            v = q[qh]
            qh += 1
            for to in g[v]:
                if base[v] == base[to] or match[v] == to:
                    continue
                if to == root or (match[to] != -1 and p[match[to]] != -1):
                    # to là đỉnh "chẵn": cạnh v-to khép một chu trình lẻ, co bông hoa
                    cur = lca(v, to, base, p)
                    blossom = [False] * n
                    mark_path(v, cur, to, base, p, blossom)
                    mark_path(to, cur, v, base, p, blossom)
                    for i in range(n):
                        if blossom[base[i]]:
                            base[i] = cur
                            if not used[i]:
                                used[i] = True
                                q.append(i)
                elif p[to] == -1:
                    p[to] = v  # to là đỉnh "lẻ" mới
                    if match[to] == -1:
                        return to, p  # to tự do: tìm được đường tăng
                    used[match[to]] = True
                    q.append(match[to])
        return -1, p

    res = 0
    for i in range(n):
        if match[i] == -1:
            v, p = find_path(i)
            if v != -1:
                res += 1
            while v != -1:  # lật đường tăng
                pv = p[v]
                ppv = match[pv]
                match[v] = pv
                match[pv] = v
                v = ppv
    return res, match


def main():
    data = sys.stdin.read().split()
    n, m = int(data[0]), int(data[1])
    g = [[] for _ in range(n)]
    for i in range(m):
        u, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])  # đỉnh từ 0, u != v
        g[u].append(v)
        g[v].append(u)
    res, match = max_matching(n, g)
    out = [str(res)]
    for i in range(n):
        if match[i] > i:
            out.append("%d %d" % (i, match[i]))
    print("\n".join(out))


main()

Mẹo tăng tốc: trước khi chạy blossom, ghép tham lam (duyệt các cạnh, ghép nếu cả hai đầu còn tự do). Kết quả không đổi vì thuật toán chỉ cần một cặp ghép ban đầu bất kỳ, nhưng số lần BFS giảm đáng kể.

Độ phức tạp

Thao tác Thời gian Bộ nhớ
Một lần tìm đường tăng (BFS kèm co bông hoa) O(V2): mỗi lần co bông hoa duyệt O(V) đỉnh, tối đa O(V) lần co O(V+E)
Toàn bộ thuật toán O(V) lần tìm, tổng O(V3) O(V+E)
Micali-Vazirani (tham khảo) O(EV) O(V+E)

Vì sao O(V3)? Mỗi đỉnh tự do là gốc của tối đa một lần BFS thành công hay thất bại; nếu thất bại thì về sau gốc này cũng không bao giờ ghép được (một đỉnh không có đường tăng ở thời điểm nào thì mãi mãi không có, theo định lý cấu trúc), nên chỉ có V lần BFS. Trong một lần BFS, mỗi lần co bông hoa giảm số "đỉnh gốc" khác nhau ít nhất 2, nên tối đa V/2 lần co, mỗi lần O(V) để tìm LCA và cập nhật base. Các cạnh được duyệt O(E) mỗi lần BFS.

⚠️ Lỗi thường gặp

  • Dùng thuật toán hai phía cho đồ thị có chu trình lẻ: Kuhn hay Hopcroft-Karp chạy trên đồ thị tổng quát vẫn trả về một số, nhưng có thể nhỏ hơn đáp án thật (như ví dụ trên). Trước khi dùng, kiểm tra đồ thị có thật sự hai phía không.
  • Ghép tham lam thay cho blossom: ghép từ trái sang phải theo một thứ tự "hợp lý" thường đúng trên test nhỏ nhưng sai khi có chu trình lẻ. Nếu bài quy về cặp ghép trên đồ thị tổng quát, phải chạy blossom (hoặc chứng minh cấu trúc đặc biệt như đường đi, cây thì tham lam/DP được).
  • Quên đặt lại p theo hướng ngược khi co: mark_path phải đặt p[v] = child cho các đỉnh trên đường từ cả hai phía của cạnh khép bông hoa. Thiếu một phía thì lúc lật đường tăng sẽ đi sai, cặp ghép không hợp lệ (hai cạnh chung đỉnh).
  • Không đẩy đỉnh lẻ cũ của bông hoa vào hàng đợi: sau khi co, các đỉnh trước đó mang nhãn lẻ (như đỉnh 1, 4 ở ví dụ) trở thành chẵn và phải được duyệt tiếp. Bỏ qua bước này chính là lỗi của tìm kiếm kiểu hai phía.
  • Khuyên và cạnh lặp: khuyên u-u không bao giờ thuộc cặp ghép, nên bỏ đi khi đọc. Cạnh lặp vô hại với cài đặt trên nhưng làm chậm; có thể khử trùng bằng ma trận kề khi V nhỏ.
  • Nhầm sang bài có trọng số: blossom ở đây tìm cặp ghép có số cạnh lớn nhất. Cặp ghép trọng số lớn nhất trên đồ thị tổng quát cần thuật toán blossom có trọng số (đối ngẫu LP, O(V3) nhưng dài hơn nhiều), không phải chỉ đổi BFS thành Dijkstra.

Biến thể / Mở rộng

  • Đồ thị hai phía: khi chắc chắn không có chu trình lẻ, dùng thuật toán đơn giản và nhanh hơn: Bipartite Matching (Ghép cặp hai phía) và Hopcroft-Karp. Ghép cặp hai phía cũng là một bài luồng, xem Max Flow (Dinic).
  • Ma trận Tutte (ngẫu nhiên): kích thước cặp ghép lớn nhất bằng một nửa hạng của ma trận Tutte Tuv=xuv, Tvu=−xuv với xuv ngẫu nhiên modulo một số nguyên tố lớn. Khử Gauss O(V3) cho kích thước (không cho cặp cụ thể) với xác suất sai rất nhỏ, cài đặt ngắn hơn blossom.
  • Phủ cạnh nhỏ nhất: trên đồ thị không có đỉnh cô lập, số cạnh ít nhất phủ mọi đỉnh là V−ν(G) (định lý Gallai), với ν(G) là kích thước cặp ghép lớn nhất.
  • Phân tích Gallai-Edmonds: sau khi chạy blossom, các đỉnh chia thành D (không phải lúc nào cũng được ghép), A (láng giềng của D) và C (phần còn lại). Phân tích này trả lời các câu hỏi "đỉnh nào luôn được ghép trong mọi cặp ghép lớn nhất".
  • Ghép có trọng số: với đồ thị hai phía dùng Min Cost Flow hoặc thuật toán Hungary; với đồ thị tổng quát nhỏ (V≤20) có thể quy hoạch động bitmask.

Bài tập luyện

  • In tài liệu (icpc24mbh): (Expert) Tìm số tờ giấy ít nhất cần in thêm để ghép được tài liệu N trang từ các tờ đã in. Sau khi gom các trang bằng DSU, mỗi thành phần cây để hở một trang, và việc gộp hai trang hở liên tiếp vào một tờ là bài cặp ghép lớn nhất trên đồ thị các thành phần, có chu trình lẻ nên cần blossom.
Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0