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
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
c
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
c
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
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
3
Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA
Bộ môn KHMT
L. R. Ford; D. R. Fulkerson (1962). Flows in
Networks. Princeton, NJ: Princeton University Press.
4
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.
