BM Khoa học Máy tính • TOÁN RỜI RẠC • Fall 2005 • Nguyễn Đức Nghĩa
Ch ng 6ươ
Bài toán luồng cực đại
Bài toán luồng cực đại
Maximum Flow Problem
w
s
v
u
t
z
3/3
1/9
1/1
3/3
4/7
4/6
3/5
1/1
3/5
2/2
BM Khoa học Máy tính • TOÁN RỜI RẠC • Fall 2005 • Nguyễn Đức Nghĩa
Bài toán luồng cực đại
Maximum Flow Problem
w
s
v
u
t
z
3/3
1/9
1/1
3/3
4/7
4/6
3/5
1/1
3/5
2/2
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
3
NỘI DUNG
Bài toán luồng cực đại trong mạng.
Lát cắt, Đường tăng luồng.
Định lý về luồng cực đại và lát cắt hẹp nhất.
Thuật toán Ford-Fulkerson
Thuật toán Edmond-Karp.
Các ứng dụng
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
4
L. R. Ford; D. R. Fulkerson (1962). Flows in
Networks. Princeton, NJ: Princeton University Press.
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
5
Lester Randolph Ford, Jr (1927 ~)
Lester Randolph Ford, Jr. (born September 23, 1927), son of
Lester R. Ford, Sr., is an American mathematician
specializing in network flow programming. His 1956 paper
with D. R. Fulkerson on the maximum flow problem
established the maxflow-mincut theorem.
