Đang chuẩn bị liên kết để tải về tài liệu:
Giáo trình lý thuyết đồ thị - Bài 15

Mạng vận tải Khi điều hành một hệ thống vận tải, bao giờ chúng ta cũng mong muốn tìm ra một phương án vận chuyển được nhiều hàng hoá nhất. Chương này của cuốn sách sẽ mô hình hoá toán học hệ thống vận tải và xây dựng thuật toán hữu hiệu chỉ ra phương án tối ưu ấy. | BÀI 15 Chương 9 Mạng vận tải Khi điều hành một hệ thống vận tải bao giờ chúng ta cũng mong muốn tìm ra một phương án vận chuyển được nhiều hàng hoá nhất. Chương này của cuốn sách sẽ mô hình hoá toán học hệ thống vận tải và xây dựng thuật toán hữu hiệu chỉ ra phương án tối ưu ấy. 9.1. 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. 9.1.1. Mạng vận tải Định nghĩa 9.1 Mạng vận tải là một đồ thị có hướng G V E không có đỉnh nút trong đó 1 có duy nhất một đỉnh x0 không có cạnh đi vào F-1 x0 0 đỉnh phát 2 có duy nhất một đỉnh z không có cạnh đi ra F z 0 đỉnh thu 3 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. 9.1.2. Luồng qua mạng Với một mạng G V E ta ký hiệu W- x a x G E I a G V - đó là tập các cạnh đi vào đỉnh x. W x x b G E I b G V - đó là tập các cạnh đi ra khỏi đỉnh x. Định nghĩa 9.2 Hàm t E N được gọi là một luồng đi qua mạng G c nếu a V e G 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 V x x0 và z t W- x t W x - luồng trên các đỉnh phải cân bằng. Với tập B c V ta ký hiệu W- B a b G E I a B b G B - tập cạnh từ ngoài B đi vào B W B a b G E I a G B b Ề B - tập cạnh từ B đi ra khỏi B. Hình 9.1. Tập cạnh vào và ra của một tập đỉnh Hiển nhiên nếu tập con các đỉnh B không chứa x0 và z thì f W- B t W B . Thật vậy theo tính chất b của luồng X t W x 2t W x . te B teB Trong số các 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. 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 . Hình 9.2. Các cạnh kề với một tập đỉnh Từ nhận xét trên nếu lấy B V x0 z thì - khi G không có cạnh x0 z ta có W xo W B .