Một số bài toán luồng tổng quát

Xét mạng G với p điểm phát s₁, s₂, . . ., sp và q điểm thu t₁, t₂,. . . , tq. Giả sử rằng luồng có thể đi từ một điểm phát bất kỳ đến tất cả các điểm thu. Bài toán tìm luồng cực đại từ các điểm phát đến các điểm thu có thể đưa về bài toán với một điểm phát và một điểm thu bằng cách đưa vào một điểm phát giả s và một điểm thu giả t và cạnh nối s với tất cả các điểm phát và cạnh nối các điểm thu với t.

Hình 4 minh hoạ cho cách đưa mạng với nhiều điểm phát và nhiều điểm thu về mạng chỉ có một điểm phát và một điểm thu. Khả năng thông qua của cung nối s với điểm phát sk sẽ bằng +∞ nếu không có hạn chế về lượng phát của điểm phát sk, và nếu lượng phát của sk bị hạn chế bởi bk thì cung (s, sk) có khả năng thông qua là bk. Cũng như vậy, đối với các cung nối tk với điểm thu t, giả sử khả năng thông qua của (tk, t) sẽ là giới hạn hoặc không giới hạn tuỳ theo lượng thu của điểm thu này có bị giới hạn hay không.

Trường hợp một số điểm thu chỉ nhận "hàng" từ một số điểm phát ta có bài toán nhiều luồng là một bài toán phức tạp hơn rất nhiều so với bài toán luồng cực đại giữa điểm phát s và điểm thu t.

Hình 4. Mạng với nhiều điểm phát và thu.

Giả sử trong đồ thị G, ngoài khả năng thông qua của các cung c(u,v), ở mỗi đỉnh v∈ V còn có khả năng thông qua các đỉnh là d(v), và đòi hỏi tổng luồng đi vào đỉnh v không được vượt quá d(v), tức là.

f(w,v) ≤ d(v)v ∈ V

Cần phải tìm luồng cực đại giữa s và t trong mạng như vậy.Xây dựng một mạng G’ sao cho: mỗi đỉnh v của G tương ứng với 2 đỉnh v⁺, v^- trong G’, mỗi cung (u,v) trong G ứng với cung (u-,v⁺) trong G’, mỗi cung (v, e) trong G ứng với mỗi cung (v^-, w⁺) trong G’. Ngoài ra, mỗi cung (v⁺, v^-) trong G’ có khả năng thông qua là d(v), tức là bằng khả năng thông qua của đỉnh v trong G.Do luồng đi vào đỉnh v⁺ phải đi qua cung (v⁺, v^-) với khả năng thông qua d(v), nên luồng cực đại trong G’ sẽ bằng luồng cực đại trong G với khả năng thông qua của các cung và các đỉnh.

Hình 5. Hình 5a cho ví dụ mạng G với khả năng thông qua ở cung và đỉnh.

Hình 5b là mạng G’ tương ứng chỉ có khả năng thông qua trên các cung.

Xét mạng G mà trong đó mỗi cung (u, v) có khả năng thông qua (cận trên của luồng trên cung) c(u,v) và cận dưới của luồng là d(u,v). Bài toán đặt ra là liệu có tồn tại luồng tương thích từ s đến t, tức là luồng  f(u,v): u, v ∈ V thoả mãn thêm ràng buộc

d(u,v) ≤ f(u,v) ≤ c(u,v) , ∀ u, v∈ E,

hay không?

Đưa vào mạng G đỉnh phát sa và đỉnh thu ta và xây dựng mạng Ga theo qui tắc:

Mỗi cung (u,v) mà d(u,v) ≠ 0 sẽ tương ứng với 2 cung (sa, v) va (u, ta) với khả năng thông qua là d(u,v). Giảm c(u,v) đi d(u,v) tức là thay khả năng thông qua của cung (u,v) bởi c(u,v) –d(u,v) còn cận dưới của nó đặt bằng 0. Ngoài ra thêm vào cung (t,s) với c(t,s) = ∞ .

Hình 6. Mạng với khả năng thông qua bị chặn hai phía.

Hình 6(a) cho ví dụ mạng G với khả năng thông qua của các cung bị chặn cả hai phía. Đồ thị Ga tương ứng được cho trong hình 6(b).

Ký hiệu d^* =  d(u,v).

                   d(u,v)≠0

Định lý 4.

1) Nếu luồng lớn nhất trong mạng Ga từ sa đến ta bằng d^* thì tồn tại luồng tương thích trong G.

2) Nếu luồng lớn nhất trong mạng Ga từ sa đến ta là khác d^* thì không tồn tại luồng tương thích trong G.