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 đến đích .
Đị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
- Min Cost Flow — Luồng cực tiểu chi phí
- Bipartite Matching — Ghép cặp hai phía
Mô hình hóa thường gặp
| Bài toán | Mô hình |
|---|---|
| Ghép cặp hai phía | Max flow với trái, phải , capacity 1 |
| Vertex cover (König) | Ghép cặp → tìm min vertex cover |
| Bài toán phân công | Bipartite matching |
| Lưu lượng mạng lưới | Max flow trực tiếp |
| Circulation | Biến đổi thành max flow |
Bình luận