Luồng mạng (Network Flow)

Luồng mạng mô hình hóa bài toán vận chuyển tối đa qua mạng có sức chứa giới hạn. Bài toán cơ bản: tìm luồng cực đại từ nguồn $s$ đến đích $t$.

Định lý Max-Flow Min-Cut: Luồng cực đại = lát cắt cực tiểu.

Các trang con

• Max Flow (Dinic) — Luồng cực đại $O(V^{2}E)$
• Min Cost Flow — Luồng cực đại chi phí nhỏ nhất (MCMF)
• Bipartite Matching — Ghép cặp hai phía bằng Kuhn
• Hopcroft-Karp — Ghép cặp hai phía nhanh $O(E\sqrt{V})$

Mô hình hóa thường gặp