Wiki › Thuật toán › Luồng mạng (Network Flow) › Định lý Hall, Kőnig và Dilworth

Định lý Hall, Kőnig và Dilworth

Định lý Hall (điều kiện có cặp ghép đầy đủ, bản thiếu hụt, kiểm tra nhanh trên đoạn), Kőnig (cặp ghép cực đại bằng phủ đỉnh nhỏ nhất, tập độc lập lớn nhất), Dilworth và Mirsky (phủ xích, phản xích) cùng phủ đường đi trên DAG bằng ghép cặp hai phía.

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

Ba định lý Hall, Kőnig và Dilworth là phần "lý thuyết" đứng sau thuật toán ghép cặp hai phía. Chúng trả lời những câu hỏi mà chạy thuật toán ghép cặp thôi chưa đủ: khi nào tồn tại cặp ghép đầy đủ (Hall), cặp ghép cực đại bằng đại lượng nào khác (Kőnig: phủ đỉnh nhỏ nhất, từ đó suy ra tập độc lập lớn nhất), và số xích ít nhất phủ một tập sắp thứ tự bộ phận bằng phản xích lớn nhất (Dilworth). Giá trị thực tế nằm ở hai chỗ:

  • Biến một bài "phủ ít nhất / chọn nhiều nhất" (phủ đường đi trên DAG, chọn nhiều đoạn không giao, xoá hàng/cột) về một lần ghép cặp O(EV) thay vì duyệt tập con O(2n).
  • Biến điều kiện Hall thành một bất đẳng thức đơn giản (theo tiền tố, theo đoạn) có thể kiểm tra trong O(nlogn) bằng cây phân đoạn, khi đồ thị quá lớn để ghép cặp trực tiếp.

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

Định lý Hall (định lý hôn nhân)

Cho đồ thị hai phía G=(L∪R,E). Với tập S⊆L, gọi N(S) là tập các đỉnh phải kề với ít nhất một đỉnh của S.

Có cặp ghép phủ hết L⟺|N(S)|≥|S|với mọi S⊆L.

Chiều "⇒" hiển nhiên: nếu ghép được hết thì |S| đỉnh của S ghép với |S| đỉnh phải khác nhau, tất cả nằm trong N(S). Chiều ngược lại mới là nội dung: không có vật cản nào khác ngoài một tập S "quá đông so với hàng xóm".

Bản thiếu hụt (deficiency). Tổng quát hơn, cặp ghép cực đại có kích thước

ν(G)=|L|−maxS⊆L(|S|−|N(S)|),

trong đó max lấy cả S=∅ nên luôn ≥0. Hall là trường hợp đại lượng thiếu hụt bằng 0.

Chứng minh bằng lát cắt nhỏ nhất. Dựng mạng: nguồn s→u sức chứa 1 với mọi u∈L, cạnh u→v sức chứa ∞ với mỗi cạnh của G, v→t sức chứa 1 với mọi v∈R. Luồng cực đại bằng cặp ghép cực đại (xem luồng cực đại). Xét một lát cắt hữu hạn (A,A¯) với s∈A, đặt S=L∩A:

  • Nếu có u∈S kề v∉A thì cạnh ∞ bị cắt, lát cắt vô hạn. Vậy N(S)⊆A.
  • Các cạnh bị cắt: s→u với u∈L⧵S (đóng góp |L|−|S|) và v→t với v∈R∩A⊇N(S) (đóng góp ≥|N(S)|). Chọn R∩A=N(S) là tốt nhất.

Vậy lát cắt nhỏ nhất =minS(|L|−|S|+|N(S)|), đúng công thức thiếu hụt. Theo định lý luồng cực đại bằng lát cắt nhỏ nhất, xong cả Hall lẫn bản thiếu hụt.

Góc nhìn đường tăng. Nếu cặp ghép cực đại M còn đỉnh u∈L tự do, gọi Z là tập đỉnh đi tới được từ u bằng đường luân phiên. Mọi đỉnh phải trong Z đều đã ghép (nếu không sẽ có đường tăng), và đối tác của nó cũng trong Z. Đặt S=Z∩L thì N(S)=Z∩R và |S|=|N(S)|+1: chính S là vật cản vi phạm Hall. Đây cũng là cách tìm ra tập vi phạm khi đề yêu cầu in chứng cứ.

Dùng Hall để kiểm tra nhanh

Hall có 2|L| tập S, nhưng khi đồ thị có cấu trúc thì chỉ vài tập "quan trọng":

  • Đỉnh trái là đoạn, đỉnh phải là điểm (người i nhận một điểm trong [ai,bi], mỗi điểm cho một người). Với S bất kỳ, N(S) là hợp các đoạn; tách theo từng thành phần liên thông [l,r] của N(S) thì nếu S vi phạm, một thành phần cũng vi phạm, và thêm vào đó mọi đoạn nằm trong [l,r] chỉ làm vi phạm nặng hơn. Do đó

ghép được hết⟺#{i:l≤ai, bi≤r}≤r−l+1∀l≤r.

  • Đoạn tiền tố (ai=1): chỉ còn #{i:bi≤t}≤t với mọi t, kiểm tra bằng đếm phân phối O(n+M).
  • Kiểm tra mọi (l,r) bằng cây phân đoạn. Quét r tăng dần, giữ val(l)=cnt(l,r)+l, khởi tạo val(l)=l. Khi gặp đoạn có bi=r, cộng 1 trên [1,ai]. Điều kiện tại r là maxl≤rval(l)≤r+1. Một cây phân đoạn cộng đoạn, lấy max cho O((n+M)logM). Câu hỏi "k người đầu có ghép được không" thì tìm nhị phân theo k hoặc thêm dần và dừng ở lần vi phạm đầu tiên.
Định lý Kőnig

Trên đồ thị hai phía, kích thước cặp ghép cực đại bằng kích thước phủ đỉnh nhỏ nhất (tập đỉnh chạm mọi cạnh).

  • ≥: các cạnh ghép không chung đỉnh, mỗi cạnh cần một đỉnh phủ riêng, nên mọi phủ có ít nhất |M| đỉnh.
  • Dựng phủ đúng |M| đỉnh: lấy Z là tập đỉnh tới được từ mọi đỉnh trái tự do bằng đường luân phiên (trái sang phải theo cạnh bất kỳ, phải sang trái theo cạnh ghép). Phủ là

C=(L⧵Z)∪(R∩Z).

Cạnh (u,v) nào cũng bị phủ: nếu u∈Z thì v∈Z. Mỗi đỉnh của C là một đầu của đúng một cạnh ghép (đỉnh trái ngoài Z đều đã ghép vì đỉnh tự do nằm trong Z; đỉnh phải trong Z đã ghép vì M cực đại), và không cạnh ghép nào có cả hai đầu trong C (đỉnh phải trong Z kéo theo đối tác vào Z). Vậy |C|=|M|.

Trong ngôn ngữ lát cắt ở trên, Z chính là phía nguồn của lát cắt nhỏ nhất trong mạng dư.

Tập độc lập lớn nhất. Phần bù của một phủ đỉnh là tập độc lập (không có cạnh nào có cả hai đầu ngoài phủ) và ngược lại, nên trên đồ thị hai phía n đỉnh:

α(G)=n−ν(G),tập độc lập lớn nhất=(L∩Z)∪(R⧵Z).

Trên đồ thị tổng quát, tập độc lập lớn nhất là NP-khó; tính hai phía là điều kiện bắt buộc.

Phủ đường đi trên DAG

Cho DAG n đỉnh. Phủ đường đi rời đỉnh (mỗi đỉnh thuộc đúng một đường, đường đi theo cạnh của DAG) ít nhất bằng

n−ν(G′),

với G′ là đồ thị hai phía: mỗi đỉnh u có bản sao trái ura và bản sao phải uvào, mỗi cạnh u→v thành cạnh ura−vvào. Một cặp ghép chọn cho mỗi đỉnh nhiều nhất một "đỉnh kế tiếp" và mỗi đỉnh có nhiều nhất một "đỉnh đứng trước". Ban đầu n đường một đỉnh, mỗi cạnh ghép nối hai đường thành một. DAG không có chu trình nên các cạnh ghép không bao giờ khép vòng.

Định lý Dilworth và Mirsky

Một tập sắp thứ tự bộ phận (poset) trên DAG: u≤v nếu từ u tới được v. Xích là tập đôi một so sánh được (nằm trên một đường đi, có thể nhảy cóc), phản xích là tập đôi một không so sánh được.

Dilworth: số xích ít nhất phủ hết các phần tử = kích thước phản xích lớn nhất.

  • ≥: mỗi xích chứa nhiều nhất một phần tử của một phản xích.
  • Đạt được: xích được phép "nhảy cóc" qua đỉnh đã thuộc xích khác, nên số xích ít nhất chính là phủ đường đi rời đỉnh trên bao đóng bắc cầu (thêm cạnh u→v khi u tới được v): bằng n−ν. Áp dụng Kőnig lên đồ thị hai phía của bao đóng, lấy phủ C cỡ ν. Tập các v mà cả vra lẫn vvào đều không thuộc C có ít nhất n−ν phần tử, và là phản xích: nếu u<v thì cạnh ura−vvào không bị phủ, mâu thuẫn.

Mirsky (đối ngẫu): số phản xích ít nhất phân hoạch tập = độ dài xích dài nhất. Chứng minh rất ngắn: gọi h(v) là số đỉnh của xích dài nhất kết thúc ở v (quy hoạch động theo thứ tự tô pô). Nếu u<v thì h(u)<h(v), nên các đỉnh cùng giá trị h đôi một không so sánh được: chia theo h cho đúng (xích dài nhất) phản xích. Mirsky dễ và không cần ghép cặp; Dilworth khó hơn hẳn.

Với dãy số (poset i<j, ai<aj): xích là dãy con tăng ngặt, phản xích là dãy con không tăng. Mirsky cho "số dãy con không tăng ít nhất phân hoạch dãy = LIS" (thuật toán xếp bài patience), Dilworth cho "số dãy con tăng ngặt ít nhất = dãy con không tăng dài nhất". Bản tổng quát cho k xích là định lý Greene, xem Young tableau.

Ví dụ chạy tay

Hall và đại lượng thiếu hụt

Bên trái 1,2,3, bên phải a,b,c. Đỉnh 1 và 2 chỉ thích a; đỉnh 3 thích cả ba.

graph
6 5
1 4
2 4
3 4
3 5
3 6
name 4 a
name 5 b
name 6 c
pos 1 0 0
pos 2 0 80
pos 3 0 160
pos 4 200 0
pos 5 200 80
pos 6 200 160
highlight red 1 2 4

Tập S={1,2} có N(S)={a}: |S|−|N(S)|=1. Không tập nào thiếu hơn (S={1,2,3} có N(S)={a,b,c}, thiếu 0), nên ν=3−1=2, ví dụ ghép 1−a, 3−b. Đỉnh 2 không bao giờ được ghép cùng lúc với 1: đúng vật cản mà Hall chỉ ra.

Bản đoạn. Ba người muốn điểm trong các đoạn [1,2],[2,2],[1,2] và một người muốn [3,4], có 4 điểm. Với (l,r)=(1,2): có 3 đoạn nằm gọn trong [1,2] nhưng chỉ 2 điểm, vi phạm. Khi quét bằng cây phân đoạn, tại r=2 ta có val(1)=3+1=4>r+1=3, dừng ngay.

Kőnig: dựng phủ đỉnh từ cặp ghép

Bên trái 1..4, bên phải 5..7, cạnh 1−5, 2−5, 2−6, 3−6, 3−7, 4−6. Kuhn duyệt 1,2,3,4 cho cặp ghép 1−5, 2−6, 3−7 (đỉnh 4 không tìm được đường tăng), ν=3.

graph
7 6
1 5
2 5
2 6
3 6
3 7
4 6
pos 1 0 0
pos 2 0 70
pos 3 0 140
pos 4 0 210
pos 5 200 35
pos 6 200 105
pos 7 200 175
step Cặp ghép cực đại (xanh lá), đỉnh 4 tự do
highlight green 1-5 2-6 3-7
highlight orange 4
step Z: từ 4 sang 6, theo cạnh ghép về 2, sang 5, theo cạnh ghép về 1
highlight orange 4-6 6 2 2-5 5 1
step Phủ = (trái ngoài Z) + (phải trong Z) = {3, 5, 6}
clear
highlight red 3 5 6

Lan truyền từ đỉnh tự do 4: 4→6 (cạnh thường), 6→2 (cạnh ghép), 2→5, 5→1; đỉnh 1 không còn cạnh nào khác. Vậy Z={1,2,4,5,6}.

Đỉnh Phía Thuộc Z? Vào phủ?
1, 2, 4 trái có không
3 trái không có
5, 6 phải có có
7 phải không không

Phủ C={3,5,6} có đúng 3=ν đỉnh và chạm cả 6 cạnh. Tập độc lập lớn nhất là phần bù: {1,2,4,7}, cỡ 7−3=4.

Phủ đường đi, xích và phản xích trên DAG

DAG 5 đỉnh: 1→3, 2→3, 3→4, 3→5.

graph directed
5 4
1 3
2 3
3 4
3 5

Phủ đường đi rời đỉnh. Đỉnh 3 chỉ có một "đỉnh đứng trước" và một "đỉnh kế tiếp", nên cặp ghép cực đại có 2 cạnh, ví dụ 1ra−3vào và 3ra−4vào. Cần 5−2=3 đường: 1→3→4, 2, 5.

Phủ bằng xích (Dilworth). Bao đóng thêm 1→4, 1→5, 2→4, 2→5. Giờ ghép được 3 cạnh: 1ra−3vào, 3ra−4vào, 2ra−5vào, nên chỉ cần 5−3=2 xích: 1→3→4 và 2→5 (xích thứ hai "nhảy qua" đỉnh 3 đã dùng).

graph directed
5 8
1 3
2 3
3 4
3 5
1 4
1 5
2 4
2 5
path green 1 3 4
path orange 2 5
highlight red 4 5
label 4 phản xích
label 5 phản xích

Phản xích lớn nhất. Kőnig trên đồ thị hai phía của bao đóng cho phủ có 3 đỉnh, và các đỉnh v có cả hai bản sao nằm ngoài phủ là {4,5}: hai lá không tới được nhau, cỡ 2 bằng số xích. ({1,2} cũng là một phản xích cỡ 2.)

Mirsky trên cùng DAG: h(1)=h(2)=1, h(3)=2, h(4)=h(5)=3, nên xích dài nhất có 3 đỉnh và tập được chia thành 3 phản xích {1,2},{3},{4,5}.

Chương trình bên dưới với đầu vào 5 4 / 1 3 / 2 3 / 3 4 / 3 5 in đúng các con số trên:

3
1 3 4
2
5
2
1 3 4
2 5
2
4 5

Cài đặt

Chương trình đọc DAG n đỉnh, m cạnh (đỉnh đánh số từ 1), rồi in lần lượt: phủ đường đi rời đỉnh ít nhất (số đường và từng đường), phủ xích ít nhất (Dilworth, trên bao đóng bắc cầu), và một phản xích lớn nhất dựng theo Kőnig. Bao đóng dùng bitset theo thứ tự tô pô ngược. Ghép cặp dùng Kuhn cho gọn; với đồ thị lớn hãy thay bằng Hopcroft-Karp, phần trích đường và dựng phản xích giữ nguyên. Hằng MAXN = 1024 giới hạn số đỉnh của bao đóng, tăng lên nếu đề cho n lớn hơn.

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

// Bipartite graph: left copy u_out (0..n-1), right copy v_in (0..n-1).
struct Kuhn {
    int n;
    vector<vector<int>> adj;
    vector<int> matchL, matchR;  // matchL[u] = right partner of u, matchR[v] = left partner of v
    vector<int> seen;
    int stamp = 0;
    Kuhn(int n) : n(n), adj(n), matchL(n, -1), matchR(n, -1), seen(n, 0) {}
    bool tryKuhn(int u) {
        for (int v : adj[u]) {
            if (seen[v] == stamp) continue;
            seen[v] = stamp;
            // v is free, or its partner can move to another vertex
            if (matchR[v] == -1 || tryKuhn(matchR[v])) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        return false;
    }
    int run() {
        int res = 0;
        for (int u = 0; u < n; u++) {
            stamp++;
            if (tryKuhn(u)) res++;
        }
        return res;
    }
};

// Follow next pointers (matchL) from every vertex that has no predecessor.
vector<vector<int>> extractPaths(const Kuhn& K) {
    vector<vector<int>> paths;
    for (int v = 0; v < K.n; v++) {
        if (K.matchR[v] != -1) continue;  // v has a predecessor, not a path start
        vector<int> p;
        for (int x = v; x != -1; x = K.matchL[x]) p.push_back(x);
        paths.push_back(p);
    }
    return paths;
}

void printPaths(const vector<vector<int>>& paths) {
    printf("%d\n", (int)paths.size());
    for (auto& p : paths) {
        for (size_t i = 0; i < p.size(); i++) printf("%d%c", p[i] + 1, i + 1 == p.size() ? '\n' : ' ');
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<pair<int, int>> edges(m);
    for (auto& [u, v] : edges) { scanf("%d %d", &u, &v); u--; v--; }

    // 1) Minimum vertex-disjoint path cover: n - max matching on the edges of the DAG
    Kuhn A(n);
    for (auto [u, v] : edges) A.adj[u].push_back(v);
    A.run();
    printPaths(extractPaths(A));

    // 2) Minimum chain cover (Dilworth): same matching on the transitive closure
    const int MAXN = 1024;
    vector<bitset<MAXN>> reach(n);
    vector<vector<int>> out(n);
    vector<int> indeg(n, 0), order;
    for (auto [u, v] : edges) { out[u].push_back(v); indeg[v]++; }
    queue<int> q;
    for (int v = 0; v < n; v++) if (!indeg[v]) q.push(v);
    while (!q.empty()) { int u = q.front(); q.pop(); order.push_back(u); for (int v : out[u]) if (--indeg[v] == 0) q.push(v); }
    for (int i = n - 1; i >= 0; i--) {  // reverse topological order
        int u = order[i];
        for (int v : out[u]) { reach[u][v] = 1; reach[u] |= reach[v]; }
    }
    Kuhn B(n);
    for (int u = 0; u < n; u++)
        for (int v = 0; v < n; v++) if (reach[u][v]) B.adj[u].push_back(v);
    B.run();
    printPaths(extractPaths(B));

    // 3) Maximum antichain via Konig: Z = vertices reachable from free left vertices
    //    by alternating paths (left -> right by any edge, right -> left by matching edge).
    //    Min vertex cover = (L \ Z) + (R n Z); antichain = {v : v_L in Z and v_R not in Z}.
    vector<char> inZL(n, 0), inZR(n, 0);
    queue<int> bq;
    for (int u = 0; u < n; u++) if (B.matchL[u] == -1) { inZL[u] = 1; bq.push(u); }
    while (!bq.empty()) {
        int u = bq.front(); bq.pop();
        for (int v : B.adj[u]) {
            if (inZR[v]) continue;
            inZR[v] = 1;
            int w = B.matchR[v];  // v is matched, otherwise the matching was not maximum
            if (w != -1 && !inZL[w]) { inZL[w] = 1; bq.push(w); }
        }
    }
    vector<int> anti;
    for (int v = 0; v < n; v++) if (inZL[v] && !inZR[v]) anti.push_back(v);
    printf("%d\n", (int)anti.size());
    for (size_t i = 0; i < anti.size(); i++) printf("%d%c", anti[i] + 1, i + 1 == anti.size() ? '\n' : ' ');
    return 0;
}
Python
import sys
from collections import deque


def max_matching(n, adj):
    """Kuhn's algorithm. Returns (matchL, matchR)."""
    sys.setrecursionlimit(10000)
    matchL = [-1] * n
    matchR = [-1] * n

    def try_kuhn(u, seen):
        for v in adj[u]:
            if seen[v]:
                continue
            seen[v] = True
            # v is free, or its partner can move to another vertex
            if matchR[v] == -1 or try_kuhn(matchR[v], seen):
                matchL[u] = v
                matchR[v] = u
                return True
        return False

    for u in range(n):
        try_kuhn(u, [False] * n)
    return matchL, matchR


def extract_paths(n, matchL, matchR):
    paths = []
    for v in range(n):
        if matchR[v] != -1:
            continue  # v has a predecessor
        p, x = [], v
        while x != -1:
            p.append(x)
            x = matchL[x]
        paths.append(p)
    return paths


def main():
    data = sys.stdin.read().split()
    n, m = int(data[0]), int(data[1])
    edges = [(int(data[2 + 2 * i]) - 1, int(data[3 + 2 * i]) - 1) for i in range(m)]
    out = []

    def emit(paths):
        out.append(str(len(paths)))
        out.extend(" ".join(str(x + 1) for x in p) for p in paths)

    # 1) Minimum vertex-disjoint path cover
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
    mL, mR = max_matching(n, adj)
    emit(extract_paths(n, mL, mR))

    # 2) Transitive closure as bitmasks (Python int), in reverse topological order
    indeg = [0] * n
    for u, v in edges:
        indeg[v] += 1
    order, q = [], deque(v for v in range(n) if indeg[v] == 0)
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    reach = [0] * n
    for u in reversed(order):
        for v in adj[u]:
            reach[u] |= (1 << v) | reach[v]
    cadj = [[v for v in range(n) if reach[u] >> v & 1] for u in range(n)]
    mL, mR = max_matching(n, cadj)
    emit(extract_paths(n, mL, mR))

    # 3) Maximum antichain via Konig
    inZL, inZR = [False] * n, [False] * n
    q = deque()
    for u in range(n):
        if mL[u] == -1:
            inZL[u] = True
            q.append(u)
    while q:
        u = q.popleft()
        for v in cadj[u]:
            if inZR[v]:
                continue
            inZR[v] = True
            w = mR[v]
            if w != -1 and not inZL[w]:
                inZL[w] = True
                q.append(w)
    anti = [v + 1 for v in range(n) if inZL[v] and not inZR[v]]
    out.append(str(len(anti)))
    out.append(" ".join(map(str, anti)))
    print("\n".join(out))


main()

Cả hai bản đã được đối chiếu với vét cạn trên vài trăm DAG ngẫu nhiên đến 8 đỉnh: số đường, số xích bằng đáp án vét cạn, các đường đi theo đúng cạnh, các xích có hai phần tử liên tiếp so sánh được, và tập in ra đúng là phản xích có cỡ bằng số xích.

Muốn in phủ đỉnh hoặc tập độc lập của một đồ thị hai phía bất kỳ (bài xoá hàng/cột, chọn đoạn không giao), dùng y nguyên đoạn BFS ở bước 3 trên đồ thị đó: phủ là !inZL[u] bên trái cộng inZR[v] bên phải, tập độc lập là phần còn lại.

Độ phức tạp

Bước Thời gian Bộ nhớ
Phủ đường đi rời đỉnh (Kuhn) O(n·m) O(n+m)
Phủ đường đi rời đỉnh (Hopcroft-Karp) O(mn) O(n+m)
Bao đóng bắc cầu bằng bitset O(n·m/64) O(n2/64)
Dilworth: ghép cặp trên bao đóng (Kuhn / Hopcroft-Karp) O(n3) / O(n2.5) O(n2)
Dựng phủ đỉnh, tập độc lập, phản xích từ cặp ghép O(n+E) O(n)
Kiểm tra Hall cho đoạn bằng cây phân đoạn O((N+M)logM) O(M)

Vì sao như vậy? Kuhn chạy một DFS O(V+E) cho mỗi đỉnh trái. Bao đóng: mỗi cạnh u→v làm một phép OR n bit, tức n/64 từ máy. Bao đóng có thể có Θ(n2) cạnh (ví dụ thứ tự toàn phần), nên phần ghép cặp của Dilworth là phần đắt nhất; thực tế n≤1000 là thoải mái với Hopcroft-Karp, n≤500 với Kuhn. Dựng phủ chỉ là một BFS trên đồ thị đã có. Kiểm tra Hall: mỗi đoạn một lần cộng đoạn, mỗi r một lần lấy max.

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

  • Nhầm phủ đường đi rời đỉnh với phủ xích. Đề cho phép hai robot đi qua cùng một ô, hoặc "nhóm" chỉ cần so sánh được chứ không cần cạnh trực tiếp (búp bê lồng nhau, thứ tự bộ phận) thì phải ghép trên bao đóng bắc cầu. Ghép trên cạnh gốc cho đáp án lớn hơn (ví dụ trên: 3 thay vì 2). Ngược lại, đề yêu cầu mỗi đỉnh đúng một đường và đi theo cạnh thật thì không được lấy bao đóng.
  • Áp n−ν cho đồ thị có chu trình. Trên đồ thị có chu trình, cặp ghép có thể khép vòng (u→v→u), n−ν không còn là số đường. Với phủ xích, co thành phần liên thông mạnh trước (mỗi thành phần đi được trọn trong một xích) rồi mới làm Dilworth trên DAG co, cẩn thận trọng số đỉnh.
  • Dựng phủ Kőnig sai chiều. BFS phải xuất phát từ các đỉnh trái tự do, đi trái sang phải bằng mọi cạnh, phải sang trái chỉ bằng cạnh ghép; phủ là trái ngoài Z cộng phải trong Z. Đảo một trong ba điều này cho tập không phủ hết cạnh hoặc thừa đỉnh. Và cặp ghép phải là cực đại: chạy trên cặp ghép chưa xong cho kết quả sai mà không báo lỗi.
  • Phản xích lấy thiếu điều kiện. Đỉnh v vào phản xích khi cả hai bản sao vra, vvào nằm ngoài phủ. Chỉ xét một bản sao cho tập có phần tử so sánh được. Luôn tự kiểm tra: cỡ phản xích phải bằng n−ν.
  • Kiểm tra Hall bằng duyệt tập con, hoặc chỉ kiểm tra tiền tố khi đoạn có hai đầu. 2n tập là không khả thi; với đoạn tổng quát [ai,bi] chỉ xét #{bi≤t}≤t là thiếu (vi phạm có thể nằm ở đoạn giữa như [3,5]). Phải xét mọi (l,r), bằng cây phân đoạn như trên. Ngoài ra, chỉ điều kiện có ghép hết hay không mới quy về một đoạn; đại lượng thiếu hụt là tổng trên nhiều đoạn rời nhau, không phải max trên một đoạn.
  • Dùng Kőnig cho đồ thị không hai phía. α=n−ν và "phủ đỉnh = cặp ghép" sai ngay trên tam giác (ν=1, phủ cần 2). Trước khi áp dụng, chứng minh được đồ thị xung đột là hai phía (ví dụ đoạn ngang chỉ giao đoạn dọc).
  • Tràn bộ nhớ khi lưu bao đóng. Lưu bao đóng n=104 thành danh sách kề có thể tới 5·107 số nguyên. Khi n lớn hãy tìm cấu trúc riêng (thứ tự hai chiều thì Dilworth thành dãy con đơn điệu dài nhất, làm bằng Fenwick), hoặc duyệt kề trực tiếp trên bitset thay vì chuyển thành vector.
  • Dấu ngặt / không ngặt với dãy số. "Phân hoạch thành dãy tăng ngặt" có đối ngẫu là "dãy con không tăng dài nhất", không phải "giảm ngặt". Nhầm chỉ lộ ra khi dãy có giá trị lặp.

Biến thể / Mở rộng

  • Phủ cạnh nhỏ nhất (tập cạnh chạm mọi đỉnh, đồ thị không có đỉnh cô lập) có cỡ n−ν trên mọi đồ thị (định lý Gallai). Trên đồ thị tổng quát cần ν của Blossom.
  • Phủ đỉnh có trọng số trên đồ thị hai phía: mạng s→u sức chứa wu, v→t sức chứa wv, cạnh giữa ∞; lát cắt nhỏ nhất là đáp án, đúng như chứng minh Hall ở trên. Tập độc lập trọng số lớn nhất = tổng trọng số − lát cắt.
  • Hall có bội (mỗi đỉnh phải nhận cv người): |S|≤∑v∈N(S)cv, cùng chứng minh bằng luồng. Bài xếp lịch, xếp phòng theo mức tối thiểu thường thành điều kiện hậu tố "tổng nhu cầu mức ≥F ≤ tổng sức chứa mức ≥F".
  • Hall cho đồ thị chính quy: đồ thị hai phía k-chính quy luôn có cặp ghép hoàn hảo, và cạnh của nó phân hoạch được thành k cặp ghép hoàn hảo (dựng hình vuông Latin, xếp lịch thi đấu).
  • Ghép cặp trọng số: khi các cạnh có chi phí thì cần thuật toán Hungary hoặc luồng chi phí nhỏ nhất; Kőnig có bản trọng số là đối ngẫu quy hoạch tuyến tính (định lý Egerváry).
  • Greene và RSK: kích thước lớn nhất của hợp k phản xích (hoặc k xích) trong poset của một dãy số đọc được từ hình dạng bảng Young, xem Young tableau.

Bài tập luyện

  • Chọn Đoạn Không Giao (steeple): (Khó) Đoạn ngang chỉ giao đoạn dọc nên đồ thị xung đột là hai phía; đáp án là tập độc lập lớn nhất N−ν theo Kőnig.
  • Dòng xe vào bến (voi18_queue): (Khó) Tìm k lớn nhất để k xe đầu xếp được vào các điểm đỗ trong đoạn của mình; điều kiện Hall trên đoạn quyết định tính khả thi, kết hợp tìm nhị phân hoặc tham lam.
  • Kiểm tra dịch bệnh (dnaitst25_e): (Rất khó) Phủ đường đi rời đỉnh ít nhất trên DAG n≤1000: đúng công thức n−ν với Hopcroft-Karp.
  • Búp bê (hntst25_g): (Rất khó) Số nhóm búp bê lồng nhau ít nhất là phủ xích của thứ tự hai chiều; theo Dilworth bằng phản xích lớn nhất, tính cho từng truy vấn offline bằng Fenwick.
  • Xoá dấu theo hàng và cột (gr16_match): (Rất khó) Phủ đỉnh nhỏ nhất của đồ thị hàng-cột, phải in ra phủ: dựng tập Z từ các hàng chưa ghép như phần Kőnig, cần Hopcroft-Karp vì 105 cạnh.
  • Dãy tăng kép (dhbb26dx2711_c): (Chuyên gia) Theo Dilworth, dãy tách được thành hai dãy tăng ngặt khi và chỉ khi không có dãy con không tăng độ dài 3; đếm các dãy con như vậy bằng quy hoạch động với Fenwick.
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