tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 8 - TS. Lê Nhật Duy

Bài giảng Lý thuyết đồ thị: Chương 8 Luồng trong mạng, được biên soạn gồm các nội dung chính sau: Bài toán luồng cực đại; Định lý Ford-Fulkerson; Thuật toán tìm luồng cực đại trong mạng. Mời các bạn cùng tham khảo! | Chương 8 Luồng trong mạng Nội dung I. Bài toán luồng cực đại II. Định lý Ford-Fulkerson III. Thuật toán tìm luồng cực đại trong mạng Chương 8 Luồng trong mang 2 Lý thuyết đồ thị I. Bài toán luồng cực đại Mạng Mạng là một đồ thị có hướng G V E đỉnh s Điểm phát mà deg- s 0 đỉnh t Điểm thu mà deg t 0 cung e v w E được gán với một số không âm c e c v w 0 gọi là Khả năng thông qua của cung e. s Điểm phát t Điểm thu Nếu không có cung v w thì c v w 0 Chương 8 Luồng trong mang 3 I. Bài toán luồng cực đại Luồng trong mạng Cho mạng G V E ta gọi luồng f trong mạng G là một ánh xạ f E R với mọi cung e v w E được gán với một số không âm f e f v w 0 gọi là luồng trên cung e thỏa mãn các điều kiện sau Luồng trên mỗi cung e E không vượt quá khả năng thông qua của nó 0 f e c e Với mọi đỉnh v không trùng với đỉnh phát s và đỉnh thu t tổng luồng trên các cung đi vào v bằng tổng luồng các cung đi ra khỏi v. Div f v f w v f v w 0 w Γ v w Γ v Γ v w V w v E Với Γ v w V v w E Điều kiện cân bằng luồng Chương 8 Luồng trong mang 4 I. Bài toán luồng cực đại Luồng trong mạng Giá trị của luồng f là tổng luồng trên các cung đi ra khỏi đỉnh phát bằng tổng luồng trên các cung đi vào đỉnh thu . val f f s w f w t w Γ s w Γ t Chương 8 Luồng trong mang 5 I. Bài toán luồng cực đại Luồng trong mạng 2 3 3 Γ- v Γ v 9 5 v 6 12 f w v 2 3 9 6 20 w Γ v f v w 3 5 12 20 w Γ v Div f v 20 20 0 Chương 8 Luồng trong mang 6 I. Bài toán luồng cực đại Luồng trong mạng 2 3 Γ- t 3 5 Γ s t s 9 12 6 f w t 2 3 9 6 20 w Γ t f s w 3 5 12 20 w Γ s val f 20 Chương 8 Luồng trong mang 7 I. Bài toán luồng cực đại Các số màu xanh Khả năng thông qua trên mỗi cung Các số màu đỏ Luồng trên mỗi cung Giá trị của luồng val f 5 4 2 3 3 s Điểm phát 2 2 9 0 8 1 t Điểm thu s t Nếu không có 1 1 3 3 5 1 10 1 cung v w thì 10 2 20 1 c v w 0 Chương 8 Luồng trong mang 8 I. Bài toán luồng cực đại Bài toán luồng cực đại Cho mạng G V E hãy tìm luồng f trong mạng sao cho giá trị luồng là lớn nhất. Luồng f như vậy gọi là luồng cực đại Ứng dụng Bài .