Bài giảng Toán rời rạc (Phần II: Lý thuyết đồ thị): Chương 6 - Nguyễn Đức Nghĩa

Bài giảng Toán rời rạc (Phần II: Lý thuyết đồ thị): Chương 6 - Bài toán luồng cực đại (Maximum flow problem). Những nội dung chủ yếu được trình bày trong chương này gồm có: 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.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc (Phần II: Lý thuyết đồ thị): Chương 6 - Nguyễn Đức Nghĩa Chương6 Bài toán luồng cực đạiMaximum Flow Problem 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/2BM Khoa học Máy tính • TOÁN RỜI RẠC • Fall 2005 • Nguyễn Đức NghĩaBài toán luồng cực đạiMaximum Flow Problem 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/2BM 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ụngToá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 ~) LesterRandolphFord,Jr.(bornSeptember23,1927),sonof 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 establishedthemaxflowmincuttheorem.Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 5 Delbert Ray Fulkerson (August14,1924January10,1976) Delbert Ray Fulkerson was a mathematician who co developed the FordFulkerson algorithm, one of the most usedalgorithmstocomputemaximalflowsinnetworks. Ph.D,Univ.ofWisconsinMadison,1951. In 1956, he published his famous paper on the Ford Fulkerson algorithm together with Lester Randolph Ford. In1979,therenownedFulkersonPrizewasestablished whichisnowawardedeverythreeyearsforoutstanding papers in discrete mathematics jointly by the Mathematical Programming Society and the American MathematicalSociety. 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 864pages! 11Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 2008/5/2 Mạng và luồng trong mạngToán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA Bộ môn KHMT 8 MẠNG (Network) MạnglàđồthịcóhướngG=(V,E): Códuynhấtmộtđỉnhskhôngcócungđivàogọi là đỉnh phát (nguồ ...