Bipartite Matching (Ghép cặp hai phía)

Wiki › Thuật toán › Luồng mạng (Network Flow)

Bipartite Matching (Ghép cặp hai phía)

huunguyen · Last updated 8, Tháng 4, 2026, 15:32

Bài toán ghép cặp hai phía: cho đồ thị hai phía $G = (L \cup R, E)$ , tìm tập cạnh không chia sẻ đỉnh lớn nhất (maximum matching).

Thuật toán Hungarian (Augmenting Path) — $O (V E)$

const int MAXN = 505;
vector<int> adj[MAXN];   // adj[u]: danh sách đỉnh bên R kề với u ở bên L
int match_l[MAXN], match_r[MAXN];   // match_l[u]: u ghép với ai bên R
bool visited[MAXN];
int n_left, n_right;

bool dfs(int u) {
    for (int v : adj[u]) {
        if (visited[v]) continue;
        visited[v] = true;
        if (match_r[v] == -1 || dfs(match_r[v])) {
            match_l[u] = v;
            match_r[v] = u;
            return true;
        }
    }
    return false;
}

int max_matching() {
    fill(match_l, match_l+n_left+1, -1);
    fill(match_r, match_r+n_right+1, -1);
    int res = 0;
    for (int u = 1; u <= n_left; u++) {
        fill(visited, visited+n_right+1, false);
        if (dfs(u)) res++;
    }
    return res;
}

Dùng Max Flow

Ghép cặp hai phía là trường hợp đặc biệt của max flow:

Thêm nguồn $s$ nối với mọi $u \in L$ (capacity 1).
Thêm đích $t$ nhận từ mọi $v \in R$ (capacity 1).
Capacity của cạnh $L \to R$ là 1.

// Dùng MaxFlow từ trang max-flow
MaxFlow mf(n_left + n_right + 2);
int s = 0, t = n_left + n_right + 1;

for (int u = 1; u <= n_left; u++) mf.add_edge(s, u, 1);
for (int v = 1; v <= n_right; v++) mf.add_edge(n_left+v, t, 1);
for (int u = 1; u <= n_left; u++)
    for (int v : adj[u])
        mf.add_edge(u, n_left+v, 1);

int matching = mf.max_flow(s, t);

Định lý König

Trong đồ thị hai phía:

Maximum Matching = Minimum Vertex Cover

Tìm minimum vertex cover từ maximum matching:

Chạy max matching.
Trong residual graph, BFS từ $s$ để tìm tập đỉnh đạt được $Z$ .
Vertex cover = $(L ⧵ Z_{L}) \cup (R \cap Z_{R})$ .

// Sau khi chạy max matching
vector<bool> reachable(n_left + n_right + 2, false);
queue<int> q;
reachable[s] = true; q.push(s);
while (!q.empty()) {
    int v = q.front(); q.pop();
    for (auto& e : mf.graph[v])
        if (e.cap > 0 && !reachable[e.to]) {
            reachable[e.to] = true; q.push(e.to);
        }
}
// u ∈ L thuộc vertex cover khi !reachable[u]
// v ∈ R thuộc vertex cover khi reachable[n_left+v]

Độ phức tạp

Thuật toán	Độ phức tạp
Hungarian (DFS)	$O (V E)$
Hopcroft-Karp	$O (E \sqrt{V})$
Max Flow (Dinic)	$O (E \sqrt{V})$ cho unit capacity

Khi nào dùng?

Bài toán phân công: $n$ task, $m$ worker, mỗi worker làm được một số task.
Bài toán tô màu đồ thị hai phía.
Tìm Independent Set tối đa: $| V | - max matching$ (định lý Gallai).

Bình luận

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

Bipartite Matching (Ghép cặp hai phía)

Thuật toán Hungarian (Augmenting Path) — O(VE)

Dùng Max Flow

Định lý König

Độ phức tạp

Khi nào dùng?

Bình luận

Thuật toán Hungarian (Augmenting Path) — $O (V E)$