Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Lý thuyết đồ thị: Chương 6 - Ngô Hữu Phúc

"Bài giảng Lý thuyết đồ thị - Chương 6: Bài toán luồng cực đại" trình bày luồng vận tải, thuật toán Ford-Fulkerson. Mời các bạn cùng tham khảo bài giảng để nắm chi tiết nội dung kiến thức. | CHƯƠNG VI 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 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à deg- 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à deg vn 0. Đỉnh vn được gọi là lối ra hay đỉnh thu của mạng. 93 CHƯƠNG VI BÀI TOÁN LUỒNG CỰC ĐẠI Luồng vận tải Định nghĩa Để 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à đượ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 e E. 2 v V v v0 v vn e e - v e E e có đỉnh cuối là v e v e v v e E e có đỉnh đầu là v 94 CHƯƠNG VI BÀI TOÁN LUỒNG CỰC ĐẠI Luồng vận tải 3 ϕ e m e 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. 4 e e v n e v0 Đại lượng ϕe vn ký vn hiệu là ϕn đượ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 ϕ để ϕvn đạt giá trị lớn nhất tức là tìm giá trị lớn nhất của luồng. 95 CHƯƠNG VI BÀI TOÁN LUỒNG CỰC ĐẠI Luồng vận tải Định nghĩa Cho mạng vận tải G V E và A V. Ký hiệu Γ A u v E v A u A Γ A u v E u A v A . Đối với tập cung M tuỳ ý đại lượng được gọi là luồng của tập cung M. M e M e Hệ quả Cho ϕ là luồng của mạng vận tải G V E và A V v0 vn . Khi đó ϕ Γ A ϕ Γ A . 96 CHƯƠNG VI 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 ϕvn max trên mạng G. Định nghĩa Cho A V là tập con tuỳ ý không chứa lối vào v0 và chứa lối ra vn. Tập Γ A được gọi là một thiết diện của mạng vận tải G. Đại lượng m A m e e A được gọi là khả năng thông qua của thiết diện Γ A 97 CHƯƠNG VI BÀI TOÁN LUỒNG CỰC ĐẠI Định nghĩa Cung e trong mạng vận tải G với luồng vận