Bài giảng môn Lý thuyết đồ thị - Chương 6: Bài toán luồng cực đại

Bài giảng Lý thuyết đồ thị - Chương 6: Bài toán luồng cực đại, cung cấp cho người đọc những kiến thức như: 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.
Nội dung trích xuất từ tài liệu:
Bài giảng môn Lý thuyết đồ thị - Chương 6: Bài toán luồng cực đại Chương 6 Bài toán luồng cực đại Maximum Flow Problem c v 3/3 4/6 1/1 t 4/7 s 3/3 w 1/1 1/9 3/5 3/5 u z 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 c v 3/3 4/6 1/1 t 4/7 s 3/3 w 1/1 1/9 3/5 3/5 u z 2/2 BM Khoa học Máy tính • TOÁN RỜI RẠC • Fall 2005 • Nguyễn Đức Nghĩa 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 3 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 4 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. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 5 Delbert Ray Fulkerson (August 14, 1924 - January 10, 1976) Delbert Ray Fulkerson was a mathematician who co- developed the Ford-Fulkerson algorithm, one of the most used algorithms to compute maximal flows in networks. Ph.D, Univ. of Wisconsin-Madison, 1951. In 1956, he published his famous paper on the Ford- Fulkerson algorithm together with Lester Randolph Ford. In 1979, the renowned Fulkerson Prize was established which is now awarded every three years for outstanding papers in discrete mathematics jointly by the Mathematical Programming Society and the American Mathematical Society. Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 6 Network Flows Ravindra K. Ahuja, Thomas Magnanti and James Orlin. Network Flows. Prentice Hall, 1993. 11 42 21 1 s 2 t 32 31 864 pages! 11 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 7 Mạng và luồng trong mạng Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 8 MẠNG (Network) Mạng là đồ thị có hướng G = (V,E) : Có duy nhất một đỉnh s không có cung đi vào gọi  là đỉnh phát (nguồn) và duy nhất một đỉnh t không có cung đi ra gọi là đỉnh thu (đích). Mỗi cung e của G được gắn với một số không âm  c(e) được gọi là khả năng thông qua của e. Ví dụ: v 3 6 1 7 t s 3 w 1 9 5 5 u z 2 Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 9 LUỒNG TRONG MẠNG Định nghĩa. Luồng f trong mạng G=(V,E) là p ...