Luồng cực đại trong mạng và một số bài toán ứng dụng
Nguyễn Văn Trường
Bài toán luồng cực đại trong mạng 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ộng rãi trong thực tế cũng như những ứng dụng thú vị trong lý thuyết tổ hợp. Bài toán được đề xuất vào đầu những năm 1950, và gắn liền vơi tên tuổi của hai nhà toán học Mỹ là Ford và Fulkerson. Trong nội dung bài viết này chúng tôi muốn trình bày thuật toán của hai ông và cài đặt nó cũng như đưa ra một số bài toán ứng dụng của thuật toán.
1. Một số khái niệm
Định nghĩa 1. Mạng là một đồ thị có hướng G = (V,E), trong đó có duy nhất một đỉnh s không có cung đi vào gọi là điểm phát và có duy nhất một đỉnh t không có cung đi ra gọi là điểm thu và mỗi cung e = (v,w) thuộc E được gán với một số không âm c(e) = c(v,w) gọi là khả năng thông qua của cung e (nếu không có cung (v,w) thì khả năng thông qua c(v,w) được gán bằng 0).
Định nghĩa 2. Một luồng f trong mạng G = (V,E) là ánh xạ f : E → R+ gán cho mỗi cung e = (v,w) thuộc E một số thực không âm f(e) = f(v,w), gọi là luồng trên cung e, thoả mãn các điều kiện sau:
1) Luồng trên mỗi cung e thuộc E không vượt quá khả năng thông qua của nó:
0 ≤ f(e) ≤ c(e).
2) Điều kiện cân bằng luồng trên mỗi đỉnh của mạng là tổng luồng trên mỗi cung đi 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 và v ≠ t thì:
Divf(v) = Σf(w,v) - Σ f(v,w) = 0
w thuộc G - (v) w thuộc G + (v)
trong đó G - (v) là tập các đỉnh của mạng mà từ đó có cung đến v, và G + (v) là tập các đỉnh của mạng mà từ v có cung đến nó.
G - (v) = { w thuộc V : (w,v) thuộc E}; G + (v) = { w thuộc V : (v,w) thuộc E};
3) Giá trị của luồng f là số:
val( f ) = Σ f(s,w) = Σ f(w,t)
w thuộc G + (v) w thuộc G - (v)
Bài toán luồng cực đại trong mạng:
Cho mạng G = (V,E). Hãy tìm luồng f*trong mạng với giá trị luồng val(f*) là lớn nhất. Luồng như vậy sẽ được gọi là luồng cực đại trong mạng.
Bài toán như vậy có thể xuất hiện rất nhiều trong ứng dụng thực tế mà chúng ta sẽ nghiên cứu trong phần 3 tiếp theo dưới đây.
Định nghĩa 3. Lát cắt (X,X*) là một cách phân hoạch tập đỉnh V của mạng ra thành hai tập X và X* = VX, trong đó s thuộc X và t thuộc X*. Khả năng thông qua của lát cắt (X,X*) là số:
c(X,X*) = Σ c(v,w).
v thuộc X
w thuộc X*
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.
Bổ đề 1. Giá trị của mọi luồng f trong mạng luôn nhỏ hơn hoặc bằng khả năng thông qua của lát cắt bất kỳ của nó: val(f) ≤ c(X,X*).
