Bài giảng Toán rời rạc - Bài 21: Luồng trên mạng - Trần Vĩnh Đức
Định lý (Luồng Nguyên)
Nếu các khả năng thông qua là số nguyên, thì có tồn tại luồng cực
đại nguyên.
Chứng minh.
Thuật toán Ford-Fulkerson kết thúc và luồng cực đại nó tìm được
là luồng nguyên.
Liên quan đến thuật toán Ford-Fulkerson
▶ Làm thế nào tính được lát cắt cực tiểu? Dễ thôi, xem chứng
minh Định lý Max Flow-Min Cut.
▶ Làm thế nào để tìm đường tăng luồng? Dùng BFS!
▶ Nếu thuật toán kết thúc thì luồng thu được có là luồng cực
đại? Có chứ. Lát cắt cực tiểu là bằng chứng.
▶ Thuật toán có luôn kết thúc? Có, mỗi lần tìm được đường
tăng luồng là luồng lại tăng lên. Luồng không thể tăng vô hạn.
42 trang |
Chia sẻ: hachi492 | Ngày: 08/01/2022 | Lượt xem: 462 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Bài giảng Toán rời rạc - Bài 21: Luồng trên mạng - Trần Vĩnh Đức, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Luồng trên mạng
V0.1
Trần Vĩnh Đức
HUST
Ngày 20 tháng 11 năm 2019
1 / 34
Tài liệu tham khảo
▶ S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani,
Algorithms, July 18, 2006.
2 / 34
Nội dung
Bài toán luồng cực đại trên mạng
Thuật toán Ford-Fulkerson
Luồng cực đại và lát cắt cực tiểu
Tính hiệu quả của thuật toán
Bài toán chuyển dầu
ptg12441863
887Network-flow algorithms
SIMPLY lLL ALL PIPES TO FULL CAPACITY /THERWISE NOT ALL PIPES ARE
FULL BUT OIL mOWS THROUGH THE NETWORK CONTROLLED BY SWITCH
SETTINGS AT THE JUNCTIONS SATISFYING A LOCAL EQUILIBRIUM con-
DITION AT THE JUNCTIONS THE AMOUNT OF OIL mOWING INTO EACH
JUNCTION IS EQUAL TO THE AMOUNT OF OIL mOWING OUT &OR