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. | Luồng trên mạng Trần Vĩnh Đức HUST Ngày 20 tháng 11 năm 2019 https tailieudientucntt 1 34 Tài liệu tham khảo S. Dasgupta C. H. Papadimitriou and U. V. Vazirani Algorithms July 18 2006. https 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án https tailieudientucntt Bài toán chuyển dầu ng 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 problem https 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ể. https 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 https 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 gt 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. https 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 . https 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 5 5 c 5 5 e .