1/46
CHƯƠNG 9
MẠNG VẬN TẢI
2/46
NỘI DUNG
Mạng vận tải
Luồng qua mạng
Bài toán luồng lớn nhất
Thuật toán Ford - Fulkerson
Một số ứng dụng của bài toán luồng lớn nhất
3/46
9.1. BÀI TOÁN LUỒNG LỚN NHẤT
Bài toán luồng lớn nhất là một trong những bài
toán tối ưu của Lý thuyết Đồ thị, được đề xuất vào
đầu những năm 1950 và trở nên nổi tiếng với thuật
toán Ford - Fulkerson.
4/46
MẠNG VẬN TẢI
Định nghĩa 9.1. Mạng vận tải là một đồ thị có hướng
G= (V, E) không có đỉnh nút, trong đó:
- Có duy nhất một đỉnh x0không có cạnh đi vào,
F-1(x0) = (đỉnh phát)
- Có duy nhất một đỉnh zkhông có cạnh đi ra,
F(z) = (đỉnh thu)
- Mỗi cạnh eđược gán một số nguyên không âm c(e)
và gọi là khả năng thông qua của cạnh.
5/46
MẠNG VẬN TẢI (tiếp)
Ví dụ mạng vận tải:
x0
x1
x5
z
x4x7
x2
x6
x0
7/8
3/4
6/6
6-7/9
4/4
6-7/8
5/5 3-2/4
2-3/4 2-3/4
11/12
5/5
3/4
2/4
4/4