Bài giảng Lý thuyết đồ thị: Chương 7 - Bài toán luồng cực đại trong mạng

Bài giảng Lý thuyết đồ thị: Chương 7 - Bài toán luồng cực đại trong mạng giới thiệu tới các bạn những nội dung về khái niệm mạng; luồng trên mạng; lát cắt; đồ thị tăng luồng; thuật toán tìm luồng cực đại và một số nội dung khác. Mời các bạn tham khảo. | Chương 7 Bài toán luồng cực đại trong mạng Khái niệm mạng Định nghĩa. Mạng là một đồ thị có hướng G = , trong đó: Có duy nhất một đỉnh s không có cạnh đi vào, gọi là điểm phát. Có duy nhất một đỉnh t không có cung đi ra, gọi là điểm thu. Mỗi cạnh của đồ thị được gán với một con số không âm gọi là khả năng thông qua (băng thông) của cạnh đó. 5/14/2020 4:53:09 AM Lý thuyết đồ thị s t 1 2 3 4 4 3 3 2 3 1 4 3 Luồng trên mạng Định nghĩa. Xét mạng G = . Ta gọi luồng f trong mạng là ánh xạ f: E R+, gán cho mỗi cạnh e = (u,v) một số thực không âm f(e), 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 không đượt vượt quá khả năng thông qua của nó: f(e) c(e). Tại mỗi đỉnh, tổng luồng đi vào phải bằng tổng luồng đi ra (trừ tại s và t). Giá trị của mỗi luồng f được tính bằng tổng luồng đi ra tại s (cũng chính là tổng luồng đi vào tại t). 5/14/2020 4:53:09 AM Lý thuyết đồ thị Luồng trên mạng (tt) VD: Ký hiệu Điều kiện cân bằng luồng: Giá trị của luồng | Chương 7 Bài toán luồng cực đại trong mạng Khái niệm mạng Định nghĩa. Mạng là một đồ thị có hướng G = , trong đó: Có duy nhất một đỉnh s không có cạnh đi vào, gọi là điểm phát. Có duy nhất một đỉnh t không có cung đi ra, gọi là điểm thu. Mỗi cạnh của đồ thị được gán với một con số không âm gọi là khả năng thông qua (băng thông) của cạnh đó. 5/14/2020 4:54:40 AM Lý thuyết đồ thị s t 1 2 3 4 4 3 3 2 3 1 4 3 Luồng trên mạng Định nghĩa. Xét mạng G = . Ta gọi luồng f trong mạng là ánh xạ f: E R+, gán cho mỗi cạnh e = (u,v) một số thực không âm f(e), 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 không đượt vượt quá khả năng thông qua của nó: f(e) c(e). Tại mỗi đỉnh, tổng luồng đi vào phải bằng tổng luồng đi ra (trừ tại s và t). Giá trị của mỗi luồng f được tính bằng tổng luồng đi ra tại s (cũng chính là tổng luồng đi vào tại t). 5/14/2020 4:54:40 AM Lý thuyết đồ thị Luồng trên mạng (tt) VD: Ký hiệu Điều kiện cân bằng luồng: Giá trị của luồng f: 5/14/2020 4:54:40 AM Lý thuyết đồ thị s t 1 2 3 4 4 3 3 2 3 1 4 3 (1) (3) (1) (1) (1) (1) (2) (3) Val(f) = 4 Lát cắt Một lát cắt (X,X*) là một cách phân hoạch tập đỉnh V của mạng thành hai tập X và X* = V\X, trong đó s X và t X*. Khả năng thông qua của lát cắt (X,X*) là số: Lát cắt với khả năng thông qua nhỏ nhất được gọi là lát cắt hẹp nhất 5/14/2020 4:54:40 AM Lý thuyết đồ thị Lát cắt (tt) VD: Xét lát cắt (X,X*) với X = {s, 3, 4}, X* = {t, 1, 2} Ta có c(X, X*) = 4 + 1 + 2 + 4 = 11 Lát cắt nhỏ nhất??? Lát cắt nhỏ nhất là: X = {s, 1}, X* = {t, 2, 3, 4} 5/14/2020 4:54:40 AM Lý thuyết đồ thị s t 1 2 3 4 4 3 3 2 3 1 4 3 Lát cắt (tt) Bổ đề: Giá trị của luồng f trong mạng luôn nhỏ hơn hay bằng khả năng thông qua của lát cắt bất kỳ. Bổ đề: Giá trị luồng cực đại trong mạng không vượt quá khả năng thông qua của lát cắt hẹp nhất trong mạng. 5/14/2020 4:54:40 AM Lý thuyết đồ thị Đồ thị tăng luồng Xét mạng G với luồng f như sau: 5/14/2020 4:54:40 AM Lý thuyết đồ thị s t 1

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.