Lesson 39 — Ghép cặp đồ thị 2 phía
Ba module tương tác: kiểm tra 2 phía bằng tô 2 màu, thuật toán Kuhn tìm maximum matching qua đường tăng, và định lý König (max matching = min vertex cover).
Module 1 — Kiểm tra đồ thị 2 phía (tô 2 màu)
Tô đỉnh xuất phát màu Xanh; mọi hàng xóm phải khác màu (BFS lan toả). Nếu một cạnh nối 2 đỉnh cùng màu → có chu trình lẻ → KHÔNG 2 phía.
Chưa tô
Xanh (phía L)
Đỏ (phía R)
Đang xét
Chọn đồ thị rồi bấm "Bước tiếp".
Module 2 — Thuật toán Kuhn (maximum matching)
Lần lượt cho mỗi đỉnh trái đi tìm bạn bằng DFS. Đường tăng (augmenting path) được tô vàng; khi tới một đỉnh phải tự do → flip để tăng matching lên 1.
0
Matching
—
Đang xử lý
Cạnh thường
Cạnh trong M
Đường tăng đang thử
Bấm "Ghép đỉnh trái kế" để chạy Kuhn từng bước.
Module 3 — Định lý König
Trong đồ thị 2 phía: max matching = min vertex cover. Module này tính maximum matching rồi dựng min vertex cover (cấu trúc König) và kiểm chứng hai số bằng nhau.
—
Max matching
—
Min vertex cover
—
Max indep. set
Cạnh matching
Đỉnh trong vertex cover
König: max matching = ? = min vertex cover.
Bấm "Tính matching + cover".