tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 9 - PGS.TS. Hoàng Chí Thành

Bài giảng Lý thuyết đồ thị: Chương 9 Mạng vận tải, cung cấp cho người đọc những kiến thức như: Mạng vận tải; Luồng qua mạng; Bài toán luồng lớn nhất; Thuật toán Ford - Fulkerson; Một số ứng dụng của bài toán luồng lớn nhất. Mời các bạn cùng tham khảo! | CHƯƠNG 9 MẠNG VẬN TẢI 1 46 NỘI DUNG Mạng vận tải Luồng qua mạng Bài toán luồng lớn nhất Thuật toán Ford - Fulkerson Một số ứng dụng của bài toán luồng lớn nhất 2 46 . BÀI TOÁN LUỒNG LỚN NHẤT Bài toán luồng lớn nhất là một trong những bài toán tối ưu của Lý thuyết Đồ thị được đề xuất vào đầu những năm 1950 và trở nên nổi tiếng với thuật toán Ford - Fulkerson. 3 46 MẠNG VẬN TẢI Định nghĩa . Mạng vận tải là một đồ thị có hướng G V E không có đỉnh nút trong đó - Có duy nhất một đỉnh x0 không có cạnh đi vào F-1 x0 đỉnh phát - Có duy nhất một đỉnh z không có cạnh đi ra F z đỉnh thu - Mỗi cạnh e được gán một số nguyên không âm c e và gọi là khả năng thông qua của cạnh. 4 46 MẠNG VẬN TẢI tiếp Ví dụ mạng vận tải x1 4 4 3 4 7 8 3 4 x5 6 6 5 5 x2 x0 2 4 5 5 x6 11 12 z 3-2 4 6-7 8 x0 2-3 4 6-7 9 2-3 4 x4 4 4 x7 5 46 LUỒNG QUA MẠNG Với một mạng G V E c ta ký hiệu W- x a x E a V - tập các cạnh đi vào đỉnh x. W x x b E b V - tập các cạnh đi ra khỏi đỉnh x. 6 46 LUỒNG QUA MẠNG tiếp Định nghĩa . Hàm t E N là một luồng đi qua mạng G c nếu a e E t e c e - luồng trên mỗi cạnh không được vượt quá khả năng thông qua của cạnh đó. b x x0 và z t W- x t W- x - luồng trên các đỉnh phải cân bằng. 7 46 TÍNH CHẤT CỦA LUỒNG Với tập B V ký hiệu W- B a b E a B b B - tập cạnh từ ngoài B đi vào B. W B a b E a B b B - tập cạnh từ B đi ra khỏi B. 8 46 TÍNH CHẤT CỦA LUỒNG tiếp W- B B B W B Hình . Tập cạnh vào và ra của một tập đỉnh 9 46 TÍNH CHẤT CỦA LUỒNG tiếp Khi đó nếu tập con các đỉnh B không chứa x0 và z thì t W- B t W B . Theo tính chất b của luồng t W- x t W x Cạnh kề với đỉnh x nếu có đỉnh đầu và đỉnh cuối đều nằm trong tập B thì nó sẽ có mặt ở cả hai vế của đẳng thức đúng một lần do đó có thể giản ước. 10 46 TÍNH CHẤT CỦA LUỒNG tiếp Sau khi giản ước tổng ở vế trái chỉ còn lại các cạnh mà đỉnh đầu ở ngoài B đỉnh cuối trong B tức là tập W- B . Tương tự tổng ở vế phải chỉ còn lại các cạnh mà đỉnh đầu ở trong B đỉnh cuối ngoài B tức là tập W B . B Hình . Các cạnh kề với một tập .