tailieunhanh - MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐỒ THỊ PHẦN 2

Định nghĩa: Mạng vận tải là một đồ thị có hướng, không có khuyên và có trọng số G=(V,E) với V={v0, v1, ., vn} thoả mãn: 1) Mỗi cung e E có trọng số m(e) là một số nguyên không âm và được gọi là khả năng thông qua của cung e. 2) Có một và chỉ một đỉnh v0 không có cung đi vào, tức là degt(v0)=0. Đỉnh v0 được gọi là lối vào hay đỉnh phát của mạng. 3) Có một và chỉ một đỉnh vn không có cung đi ra, tức là dego(vn)=0. Đỉnh vn được gọi là. | MỘT SỐ BÀI TOÁN TỐI ƯU TRÊN ĐÒ THỊ - PHẦN 2 BÀI TOÁN LUÒNG CựC ĐẠI. . Luồng vận tải . Định nghĩa Mạng vận tải là một đồ thị có hướng không có khuyên và có trọng số G V E với V v0 v1 . vn thoả mãn 1 Mỗi cung e e E có trọng số m e là một số nguyên không âm và được gọi là khả năng thông qua của cung e. 2 Có một và chỉ một đỉnh v0 không có cung đi vào tức là degt v0 0. Đỉnh v0 được gọi là lối vào hay đỉnh phát của mạng. 3 Có một và chỉ một đỉnh vn không có cung đi ra tức là dego vn 0. Đỉnh vn được gọi là lối ra hay đỉnh thu của mạng. . Định nghĩa Để định lượng khai thác tức là xác định lượng vật chất chuyển qua mạng vận tải G V E người ta đưa ra khái niệm luồng vận tải và nó được định nghĩa như sau. Hàm ọ xác định trên tập cung E và nhận giá trị nguyên được gọi là luồng vận tải của mạng vận tải G nếu ọ thoả mãn 1 ọ e 0 Ve e E. 2 e e Vv eV Wv0 v vn. Ở đây r- v eeE e có đỉnh cuối eel v eer v là v r v eeE e có đỉnh đầu là v . 3 ọ e m e Ve e E. Ta xem ọ e như là lượng hàng chuyển trên cung e u v từ đỉnh u đến đỉnh v và không vượt quá khả năng thông qua của cung này. Ngoài ra từ điều kiện 2 ta thấy rằng nếu v không phải là lối vào v0 hay lối ra vn thì lượng hàng chuyển tới v bằng lượng hàng chuyển khỏi v. Từ quan hệ 2 suy ra 4 E e E e v . eer V0 eel vn Đại lượng ọv ta còn ký hiệu là pn được gọi là luồng qua mạng hay cường độ luồng tại điểm vn hay giá trị của luồng ọ. Bài toán đặt ra ở đây là tìm ọ để ọv đạt giá trị lớn nhất tức là tìm giá trị lớn nhất của luồng. . Định nghĩa Cho mạng vận tải G V E và A G V. Ký hiệu r A u v eE veA u A r A u v eE ueA v A . Đối với tập cung M tuỳ ý đại lượng ọ M p e được gọi là luồng của e M tập cung M. Từ điều kiện 2 dễ dàng suy ra hệ quả sau. . Hệ quả Cho ọ là luồng của mạng vận tải G V E và A G V v0 vn . Khi đó ọ r- A ọ r A . . Bài toán luồng cực đại Cho mạng vận tải G V E . Hãy tìm luồng ọ để đạt pv max trên mạng G. Nguyên lý của các thuật toán giải bài toán tìm luồng cực đại là như sau. . Định