Bài giảng Toán rời rạc: Luồng trên mạng (V0.1) - Trần Vĩnh Đức

Bài giảng Toán rời rạc: Luồng trên mạng cung cấp cho người học những nội dung kiến thức như: 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.Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Luồng trên mạng (V0.1) - Trần Vĩnh Đức Luồng trên mạng V0.1 Trần Vĩnh Đức HUST Ngày 20 tháng 11 năm 2019CuuDuongThanCong.com https://fb.com/tailieudientucntt 1 / 34 Tài liệu tham khảo ▶ S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms, July 18, 2006.CuuDuongThanCong.com https://fb.com/tailieudientucntt 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ánCuuDuongThanCong.com https://fb.com/tailieudientucntt Bài toán chuyển dầung drawing with capacities drawing with flow flow rep 0 1 0 2 1 3 1 4 2 3 2 4 3 5 4 5 sink Anatomy of a network-flow problemCuuDuongThanCong.com https://fb.com/tailieudientucntt 4 / 34 Mô hình bài bài toán a 2 d 3 10 1 2 s 3 b 1 1 t 4 5 c 5 e ▶ Đồ thị có hướng biểu diễn mạng đường ống, dầu có thể được chuyển qua đường ống này ▶ Mục tiêu là chuyển dầu từ s đến t, nhiều nhất có thể.CuuDuongThanCong.com https://fb.com/tailieudientucntt 5 / 34 Một luồng chuyển 7 đơn vị dầu từ s tới t luồng khả năng thông qua a 2/2 d 2/3 0/10 1/1 2/2 s 1/3 b 1/1 0/1 t 4/4 5/5 c 5/5 e Liệu có cách nào làm tốt hơn?CuuDuongThanCong.com https://fb.com/tailieudientucntt 6 / 34 Mạng Định nghĩa Một mạng được định nghĩa là bộ G = (V, E, s, t, c), ở đây ▶ (V, E) là một đồ thị có hướng; ▶ s, t ∈ V, gọi là đỉnh nguồn và đỉnh đích; và ▶ c là một hàm gắn trên mỗi cạnh e của G một giá trị ce > 0 gọi là khả năng thông qua. Bài toán Ta muốn chuyển nhiều dầu nhất có thể từ s tới t mà không vượt quá khả năng thông qua trên mỗi cạnh.CuuDuongThanCong.com https://fb.com/tailieudientucntt 7 / 34 Định nghĩa (Luồng) Một luồng trên mạng G là một hàm f : E −→ R+ ∪ {0}, gắn mỗi cạnh e của G với một giá trị số fe , sao cho: 1. Không vi phạm khả năng thông qua: 0 ≤ fe ≤ ce với mọi e ∈ E 2. Với mọi đỉnh u, ngoại trừ s và t, tổng luồng vào u bằng tổng luồng ra khỏi u: ∑ ∑ fwu = fuz . (w,u)∈E (u,z) Nói cách khác, mạng là bảo toàn (theo luật Kirchhoff).CuuDuongThanCong.com https://fb.com/tailieudientucntt 8 / 34 Luồng và lượng dầu chuyển luồng khả năng thông qua a 2/2 d 2/3 0/10 1/1 2/2 s 1/3 b 1/1 0/1 t 4/4 ...