Tiểu Luận Luồng cực đại

Mục lục

26. Luồng Cực Đại 2
26.1 Các mạng luồng. 3
26.2. Phương pháp Ford - Fulkerson. 11
26.3. So khớp hai nhánh cực đại 27
26.4. Các thuật toán đầy luồng trước. 33
26.5. Thuật toán nâng tới trước. 45

Bài toán luồng cực đại là bài toán đơn giản nhất liên quan đến các mạng luồng. Nó đặt vấn đề, Đâu là tốc độ lớn nhất mà vật có thể chuyển đi từ nguồn đến bồn mà không vi phạm bất kỳ hạn chế dung lượng nào? Như sẽ thấy trong chương này, bài toán này có thể được giải quyết bằng các thuật toán hiệu quả. Hơn nữa, ta có thể thích ứng các kỹ thuật căn bản mà các thuật toán này sử dụng để giải quyết các bài toán luồng mạng khác.
Chương này trình bày hai phương pháp chung để giải quyết bài toán luồng cực đại.
- Đoạn 26.1 trình bày các khái niệm về các mạng luồng và các luồng lưu chuyển, chính thức định nghĩa bài toán luồng cực đại.
- Đoạn 26.2 mô tả phương pháp cổ điển của Ford và Fulkerson để tìm các luồng cực đại.
- Đoạn 26.3 mô tả một ứng dụng của phương pháp này: tìm một so khớp cực đại trong một đồ thị hai nhánh không hướng.
- Đoạn 26.4 trình bày phương pháp đẩy luồng trước [preflow - push], làm cơ sở cho nhiều thuật toán nhanh nhất để giải quyết các bài toán luồng mạng.
- Đoạn 26.5 đề cập thuật toán "nâng tới trước" [lift - to - front], một thực thi cụ thể của phương pháp đẩy luồng trước chạy trong thời gian O(V[SUP]3[/SUP]). Tuy thật toán này không phải là thuật toán nhanh nhất được biết, song nó minh họa vài kỹ thuật được dùng trong các thuật toán nhanh nhất theo tiệm cận, và nó tương đối hiệu quả trong thực tế.