Bài giảng Bài toán luồng cực đại

Cho mạng G=(V,E). Hãy tìm luồng f* trong mạng với giá trị luồng val(f*) là

lớn nhất. Luồng như vậy ta sẽ gọi là luồng cực đại trong mạng.

Bài toán như vậy có thể xuất hiện trong rất nhiều ứng dụng thực tế. Chẳng hạn

khi cần xác định cường độ lớn nhất của dòng vận tải giữa hai nút của một bản đồ giao

thông. Trong thí dụ này lời giải của bài toán luồng cực đại sẽ chỉ cho ta các đoạn

đường xe đông nhất và chúng tạo thành chỗ hẹp tương ứng của dòng giao thông xét

theo hai nút đã chọn.