CHƯƠNG 6 LUỒNG CỰC ĐẠI TRONG MẠNG
Luồng trong mạng
Bài toán luồng cực đại
Thuật toán Ford Fulkerson
Một số ứng dụng của bài toán luồng cực đại
Gắn liền với tên tuổi của 2 nhà toán học Mỹ: Ford(Lester Randolph Ford: 1927 - ) và Fulkerson(Delbert Ray Fulkerson: 1924 - 1976).
Luồng cực đại là một trong những bài toán tối ưu trên đồ thị tìm được những ứng dụng rất rộng rãi trong cả thực tế cũng như trong lý thuyết tổ hợp.
Bài toán được đề xuất vào đầu những năm 1950
Mạng (network) là một đồ thị có hướng G= (V, E) trongCó duy nhất một đỉnh s không có cung đi vào, được gọilà đỉnh phát (source) Có duy nhất một đỉnh t không có cung đi ra, được gọi làđỉnh thu (sink) Mỗi cạnh e = (u, v) E được gán một số nguyênkhông âm c(e) = c[u, v] và gọi là khả năng thông quacủa cung đó (capacity). Ta quy ước nếu mạng không có cung (u, v) thì ta thêm vàocung (u, v) với khả năng thông qua c[u, v] bằng 0.
W-(x) = {(u, v) E | u V}: tập các cung đi vào đỉnh v.
W+(x) = {(v, u) E | u V}: tập các cung đi ra khỏi đỉnh v.
Với một mạng G = (V, E, c)
Giả sử cho mạng G = (V, E). Ta gọi luồng f trong mạng là ánh xạ f: E R+gán cho mỗi cung e = (u, v) E một số thực không âm f(e)=f[u, v], thoả mãn các điều kiện sau:
ĐK 1 (Capacity Constraint): Luồng trên mỗi cung e E không vượt quá khả năng thông qua của nó:
0 ≤ f(e) ≤ c(e)
ĐK 2 (Flow Conversion): Điều kiện cân bằng luồng trên mỗi đỉnh của mạng: Tổng luồng trên các cung vào đỉnh v bằng tổng luồng trên các cung đi ra khỏi đỉnh v, nếu v s, t.
t(W-(x)) = t(W+(x)), x s, t
Giá trị của một luồng được tính bằng tổng giá trị trên các cung đi ra từ đỉnh nguồn s, hoặc tổng giá trị trên các cung đi vào đỉnh thu t. val(f) = t(W+(s)) = t(W-(t))
TRANG TỔNG HỢP LÝ THUYẾT ĐỒ THỊ TẠI ĐÂY
