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. | 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 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 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 L. R. Ford; D. R. Fulkerson (1962). Flows in Networks. Princeton, NJ: Princeton University Press. 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. 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. , 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. 2008/5/2 Network Flows s t 3 1 1 4 3 2 2 2 1 1 1 1 2 1 864 pages! Ravindra K. Ahuja, Thomas Magnanti and James Orlin. Network Flows. Prentice Hall, 1993. Mạng và luồng trong mạng 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ụ: w s v u t z 3 9 1 3 7 6 5 1 5 2 LUỒNG TRONG MẠNG Định nghĩa. Luồng f trong mạng G=(V,E) là phép gán số f(e) cho mỗi cạnh e ( f(e) được gọi là | 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 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 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 L. R. Ford; D. R. Fulkerson (1962). Flows in Networks. Princeton, NJ: Princeton University Press. 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. 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
