Thi đấu

Cặp Ghép Cực Đại Trên Đồ Thị Hai Phía và Thuật Toán Kuhn

Tìm tập cạnh độc lập lớn nhất trên đồ thị hai phía bằng thuật toán đường tăng Kuhn (DFS) hoặc mô hình hóa quy về bài toán luồng cực đại qua đỉnh nguồn và đích ảo.

Cặp Ghép Cực Đại Trên Đồ Thị Hai Phía và Thuật Toán Kuhn

Đồ thị hai phía (Bipartite Graph) là cấu trúc đồ thị đặc biệt mà tập đỉnh có thể phân hoạch thành hai tập rời nhau \(X\) và \(Y\) sao cho mọi cạnh chỉ nối một đỉnh thuộc \(X\) với một đỉnh thuộc \(Y\). Trong thực tế, mô hình này xuất hiện ở khắp mọi nơi: phân công công việc cho công nhân, ghép cặp sinh viên với đề tài nghiên cứu, phân bổ máy bay cho các đường bay, hay ghép cặp các đấu thủ thi đấu đối kháng.

Một Cặp ghép (Matching) trên đồ thị là một tập hợp các cạnh đôi một không chung đỉnh. Bài toán cốt lõi là tìm một cặp ghép có số lượng cạnh lớn nhất — gọi là Cặp ghép cực đại (Maximum Bipartite Matching). Mặc dù bài toán này có thể quy về bài toán luồng cực đại (Max-Flow), nhưng trong phòng thi, một thuật toán trực tiếp mang tên Thuật toán Kuhn (dựa trên tìm đường tăng luồng bằng DFS) được ưa chuộng hơn cả nhờ độ dài mã nguồn cực ngắn (chưa đầy 20 dòng lệnh), cài đặt nhanh như chớp và hiệu năng thực tế vô cùng ấn tượng.

Bài viết này sẽ giải mã nguyên lý đường tăng luồng Berge, phân tích chi tiết thuật toán Kuhn, liên hệ với Định lý Kőnig về tập phủ đỉnh cực tiểu, và cung cấp mã nguồn chuẩn cho các bài thi HSG Tin học.

1. Định lý Berge và Khái niệm Đường Tăng Luồng

Để hiểu thuật toán Kuhn, ta cần nắm vững các định nghĩa sau:

  • Đỉnh tự do (Exposed / Free Vertex): Đỉnh chưa bị ghép với bất kỳ cạnh nào trong cặp ghép hiện tại.
  • Đường xen kẽ (Alternating Path): Một đường đi trên đồ thị mà các cạnh trên đường luân phiên xen kẽ giữa cạnh không thuộc cặp ghép và cạnh thuộc cặp ghép.
  • Đường tăng (Augmenting Path): Một đường xen kẽ bắt đầu bằng một đỉnh tự do thuộc tập \(X\) và kết thúc bằng một đỉnh tự do thuộc tập \(Y\).
Cặp Ghép Cực Đại Trên Đồ Thị Hai Phía (Bipartite Matching) & Thuật Toán Kuhn Tìm tập cạnh đôi một không chung đỉnh lớn nhất bằng kỹ thuật đường tăng luồng (Augmenting Path) Thuật toán Kuhn (DFS Đường Tăng) • Với mỗi đỉnh u thuộc tập trái X (0..N-1): • Duyệt DFS tìm đường mở xen kẽ tới đỉnh phải v • Nếu v chưa ghép HOẶC dfs(match[v]) thành công: gán match[v] = u -> tăng kích thước cặp ghép! Định lý Konig: Cặp ghép cực đại = Tập phủ đỉnh cực tiểu Chạy tay: X = {0,1,2,3}, Y = {0,1,2,3} • u = 0: ghép với v = 1 -> match[1] = 0 • u = 1: ghép với v = 0 -> match[0] = 1 • u = 2: ghép với v = 3 -> match[3] = 2 • u = 3: ghép với v = 2 -> match[2] = 3 => Cặp ghép hoàn hảo: 4 cặp {(0, 1), (1, 0), (2, 3), (3, 2)}
Cặp Ghép Đồ Thị Hai Phía Thuật toán Kuhn và Đường tăng luồng Nguyên lý Kuhn: • Tìm đường xen kẽ giữa cạnh tự do và cạnh ghép • Đảo trạng thái các cạnh trên đường tăng Độ phức tạp O(|V| * |E|), code cực ngắn và nhanh Chạy tay ví dụ 4 đỉnh: (0 -> 1), (1 -> 0) (2 -> 3), (3 -> 2) => Cặp ghép cực đại = 4 Đạt cặp ghép hoàn hảo không chung đỉnh
Quá trình ghép cặp 4 đỉnh độc lập trên đồ thị hai phía bằng thuật toán Kuhn đạt cặp ghép hoàn hảo 4.

Định lý then chốt của Claude Berge (1957)

Một cặp ghép \(M\) là cực đại khi và chỉ khi trên đồ thị không còn tồn tại bất kỳ đường tăng luồng nào đối với \(M\).

Hơn thế nữa, nếu ta tìm được một đường tăng luồng \(P\), thì số lượng cạnh không thuộc \(M\) trên đường đi này nhiều hơn số cạnh thuộc \(M\) đúng 1 cạnh. Bằng cách đảo ngược trạng thái của tất cả các cạnh trên đường \(P\) (cạnh nào đang trong \(M\) thì bỏ ra, cạnh nào chưa trong \(M\) thì đưa vào), ta sẽ thu được một cặp ghép mới có kích thước tăng thêm đúng 1 đơn vị (\(|M'| = |M| + 1\))!

2. Nguyên lý hoạt động của Thuật Toán Kuhn

Thuật toán Kuhn duyệt qua từng đỉnh \(u\) thuộc tập trái \(X\) (\(u = 0, \dots, N-1\)). Với mỗi đỉnh \(u\), ta tìm cách tăng kích thước cặp ghép thêm 1 bằng một lượt duyệt DFS:

  1. Duyệt qua mọi đỉnh kề \(v \in Y\) của \(u\).
  2. Nếu đỉnh \(v\) chưa được ghép (match_r[v] == -1): Ta ghép ngay \(u\) với \(v\) (match_r[v] = u) và kết thúc lượt tăng luồng!
  3. Nếu đỉnh \(v\) đã được ghép với một đỉnh \(u' = \text{match\_r}[v]\) trước đó: Ta tạm thời yêu cầu đỉnh \(u'\) thử tìm một "bến đỗ mới" thông qua lời gọi đệ quy dfs(u'). Nếu \(u'\) tìm được người ghép mới, thì đỉnh \(v\) được giải phóng để ghép với \(u\)!
  4. Nếu thử hết các đỉnh kề mà không thành công, ta kết luận không có đường tăng luồng xuất phát từ \(u\).

Phân tích độ phức tạp

  • Số đỉnh tập trái là \(|X| = N\), số đỉnh tập phải là \(|Y| = M\), số cạnh là \(|E|\).
  • Ta duyệt qua \(N\) đỉnh của tập trái. Mỗi lượt duyệt gọi DFS duyệt qua tối đa \(O(E)\) cạnh.
  • Tổng độ phức tạp thời gian trong trường hợp xấu nhất là \(O(|X| \cdot |E|)\).
  • Trong thực tế, các đồ thị ngẫu nhiên hoặc thưa thường chỉ tốn vài mili-giây, nhanh ngang ngửa thuật toán Hopcroft-Karp.
Học cùng giảng viên

Chủ đề này nằm trong Buổi 15 - Max Flow / Bipartite Matching của Tài năng lập trình. Xem đề cương

3. Cài đặt C++17 và Python 3 chuẩn thi đấu

Dưới đây là mã nguồn thuật toán Kuhn tối ưu, ngắn gọn và trong sáng:

Cài đặt C++17

#include <iostream>
#include <vector>

using namespace std;

// Thuat toan Kuhn tim cap ghep cuc dai tren do thi hai phia
struct BipartiteMatching {
    int n, m; // Tap trai n dinh (0..n-1), tap phai m dinh (0..m-1)
    vector<vector<int>> adj;
    vector<int> match_r; // match_r[v] luu dinh ben trai ghep voi v (ben phai)
    vector<bool> vis;    // vis[v] danh dau dinh ben phai v da xet trong luot DFS (m phan tu)

    BipartiteMatching(int n, int m) : n(n), m(m), adj(n), match_r(m, -1), vis(m) {}

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

    // DFS tim duong tang luong xuat phat tu u
    bool dfs(int u) {
        for (int v : adj[u]) {
            if (vis[v]) continue;
            vis[v] = true;
            // Neu v chua ghep hoac ban ghep cua v co the doi sang dinh khac
            if (match_r[v] < 0 || dfs(match_r[v])) {
                match_r[v] = u;
                return true;
            }
        }
        return false;
    }

    int max_matching() {
        int res = 0;
        for (int u = 0; u < n; ++u) {
            fill(vis.begin(), vis.end(), false);
            if (dfs(u)) res++;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // Do thi hai phia 4 dinh trai, 4 dinh phai
    BipartiteMatching bm(4, 4);
    bm.add_edge(0, 1);
    bm.add_edge(0, 2);
    bm.add_edge(1, 0);
    bm.add_edge(2, 0);
    bm.add_edge(2, 3);
    bm.add_edge(3, 2);
    
    // Ket qua: 4 cap ghep cuc dai
    cout << bm.max_matching() << '\n';
    return 0;
}

Cài đặt Python 3

import sys

class BipartiteMatching:
    def __init__(self, n: int, m: int):
        self.n = n
        self.m = m
        self.adj = [[] for _ in range(n)]
        self.match_r = [-1] * m
        self.vis = [False] * m

    def add_edge(self, u: int, v: int):
        self.adj[u].append(v)

    def dfs(self, u: int) -> bool:
        for v in self.adj[u]:
            if self.vis[v]:
                continue
            self.vis[v] = True
            if self.match_r[v] < 0 or self.dfs(self.match_r[v]):
                self.match_r[v] = u
                return True
        return False

    def max_matching(self) -> int:
        res = 0
        for u in range(self.n):
            self.vis = [False] * self.m
            if self.dfs(u):
                res += 1
        return res

def main():
    bm = BipartiteMatching(4, 4)
    bm.add_edge(0, 1)
    bm.add_edge(0, 2)
    bm.add_edge(1, 0)
    bm.add_edge(2, 0)
    bm.add_edge(2, 3)
    bm.add_edge(3, 2)
    print(bm.max_matching())

if __name__ == '__main__':
    main()

4. Định lý Kőnig và các bài toán tương đương

Định lý Kőnig (Kőnig's Theorem, 1931) là một trong những viên ngọc quý của lý thuyết đồ thị:

Trong mọi đồ thị hai phía, kích thước của Cặp ghép cực đại luôn bằng kích thước của Tập phủ đỉnh cực tiểu (Minimum Vertex Cover). \[\text{Max Matching} = \text{Min Vertex Cover}\]

Hơn thế nữa, dựa vào bổ đề về tập độc lập, ta có: \[\text{Tập độc lập cực đại (Max Independent Set)} = |V| - \text{Tập phủ đỉnh cực tiểu} = |V| - \text{Max Matching}\]

Nhờ định lý này, một loạt bài toán hóc búa tưởng như thuộc lớp NP-khó (như đặt nhiều quân xe nhất sao cho không con nào ăn được con nào trên bàn cờ có ô cản, hoặc chọn nhiều ô nhất không kề nhau) đều được giải quyết gọn gàng trong thời gian đa thức bằng thuật toán Kuhn!

Bảng chạy tay chi tiết thuật toán Kuhn tìm cặp ghép

Xét đồ thị hai phía với tập trái \(U = \{1, 2, 3\}\) và tập phải \(V = \{4, 5, 6\}\). Danh sách các cạnh: \((1, 4), (1, 5), (2, 5), (3, 5)\). Ban đầu, tất cả các đỉnh đều chưa ghép: match[v] = 0.

Lượt duyệt đỉnh trái \(u\) Đỉnh phải \(v\) xét Đỉnh \(v\) đã ghép chưa? Hành động của thuật toán Cặp ghép hiện tại
\(u = 1\) \(v = 4\) Chưa ghép (match[4] = 0) Ghép ngay: match[4] = 1 \((1, 4)\)
\(u = 2\) \(v = 5\) Chưa ghép (match[5] = 0) Ghép ngay: match[5] = 2 \((1, 4), (2, 5)\)
\(u = 3\) \(v = 5\) Đã ghép với 2 (match[5] = 2) Gọi đệ quy tìm đường tăng cho đỉnh 2 Đang tìm kiếm...
Đệ quy: \(u = 2\) Không còn cạnh nào khác Thất bại Đỉnh 2 không thể nhường đỉnh 5 Giữ nguyên \((1, 4), (2, 5)\)
Kết quả lượt 3 - - Đỉnh 3 không thể ghép Kích thước cặp ghép: 2

Qua bảng chạy tay trên, ta thấy rõ thuật toán Kuhn thử tìm đường tăng bằng cách yêu cầu đỉnh ghép cũ nhường chỗ. Nếu không tìm được đường tăng thay thế, cặp ghép hiện tại được bảo toàn nguyên vẹn.

Mối liên hệ bộ ba kinh điển: Cặp ghép, Phủ đỉnh và Tập độc lập

Trong đồ thị hai phía, Định lý Kőnig thiết lập mối liên hệ sâu sắc giữa các bài toán tối ưu tổ hợp:

  1. Cặp ghép cực đại bằng Tập phủ đỉnh cực tiểu (Min Vertex Cover): Số lượng đỉnh ít nhất để phủ toàn bộ các cạnh trên đồ thị hai phía đúng bằng kích thước của cặp ghép cực đại: \[\text{Min Vertex Cover} = \text{Max Matching}\]

  2. Tập độc lập cực đại (Max Independent Set): Tập độc lập là tập hợp các đỉnh không có cạnh nào nối trực tiếp giữa chúng. Kích thước tập độc lập cực đại luôn bằng tổng số đỉnh trừ đi tập phủ đỉnh cực tiểu: \[\text{Max Independent Set} = |V| - \text{Max Matching}\]

  3. Tập phủ cạnh cực tiểu (Min Edge Cover): Nếu đồ thị không có đỉnh cô lập, số lượng cạnh ít nhất để phủ mọi đỉnh là: \[\text{Min Edge Cover} = |V| - \text{Max Matching}\]

Nhờ các hệ quả toán học này, một bài toán tưởng chừng rất phức tạp như tìm tập độc lập lớn nhất trên đồ thị hai phía có thể được giải quyết trọn vẹn chỉ bằng một hàm tìm cặp ghép cực đại!

Bốn lỗi cài đặt thường gặp trong các kỳ thi

  1. Quên làm sạch mảng đánh dấu visited trước mỗi lượt duyệt: Trong thuật toán Kuhn, trước khi gọi dfs(u), bắt buộc phải xóa sạch mảng đánh dấu các đỉnh bên phải: vis.assign(m, false) (mảng này có kích thước bằng số đỉnh phải \(m\), không phải số đỉnh trái \(n\)). Nếu quên bước này, các đỉnh phải đã thăm trong lượt trước sẽ bị bỏ qua ở lượt sau, làm giảm nghiêm trọng kích thước cặp ghép tìm được.

  2. Nhầm lẫn không gian chỉ số giữa hai tập đỉnh: Nếu cả tập trái và tập phải đều đánh số từ \(1\) đến \(N\), mảng match sẽ bị xung đột chỉ số. Quy ước an toàn là đánh số tập trái từ \(1\) đến \(N_1\) và tập phải từ \(1\) đến \(N_2\) với hai mảng riêng biệt, hoặc cộng thêm độ dời \(N_1\) cho tập phải.

  3. Áp dụng Kuhn cho đồ thị không phải hai phía: Thuật toán Kuhn chỉ đúng trên đồ thị hai phía. Nếu đồ thị có chu trình lẻ, việc tìm đường tăng đòi hỏi kỹ thuật co cánh hoa (Blossom Algorithm của Edmonds) phức tạp hơn rất nhiều. Hãy kiểm tra tính chất hai phía bằng BFS tô 2 màu trước khi áp dụng.

  4. Đồ thị quá lớn gây TLE: Khi đồ thị có \(V \approx 5 \times 10^4\) và \(E \approx 10^5\), thuật toán Kuhn \(O(V \cdot E)\) sẽ chạy quá 1 giây. Lúc này bạn cần chuyển sang thuật toán Hopcroft-Karp hoặc thuật toán Dinic với độ phức tạp \(O(E \sqrt{V})\).

Luyện ngay trên Big-O Coding

Hãy thực hành ngay các bài toán ghép cặp đồ thị hai phía kinh điển trên Big-O Coding:

Làm thế nào để nhận biết một đồ thị là đồ thị hai phía?

Một đồ thị là đồ thị hai phía khi và chỉ khi nó không chứa bất kỳ chu trình độ dài lẻ nào. Ta có thể kiểm tra tính chất này trong thời gian \(O(V + E)\) bằng thuật toán tô 2 màu (2-Coloring) sử dụng BFS hoặc DFS. Nếu trong quá trình duyệt phát hiện hai đỉnh kề nhau có cùng màu, đồ thị không phải là đồ thị hai phía.

Thuật toán Hopcroft-Karp có ưu thế gì so với thuật toán Kuhn?

Thuật toán Hopcroft-Karp kết hợp BFS phân tầng để tìm nhiều đường tăng luồng ngắn nhất cùng lúc trong một pha, tương tự như tư duy của thuật toán Dinic. Độ phức tạp của Hopcroft-Karp là \(O(E \sqrt{V})\), nhanh hơn Kuhn khi đồ thị rất dày và số lượng đỉnh lớn (\(V \ge 10^5\)). Tuy nhiên, với các bài thi \(V \le 2000\), thuật toán Kuhn ngắn gọn hơn rất nhiều và ít nguy cơ bug trong phòng thi.

Nguồn tham khảo

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483