Luồng cực đại

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 và gắn liền với tên tuổi của 2 nhà toán học Mỹ Lester Randolph Ford và Delbert Ray Fulkerson.

Mạng

Mạng (network) 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, được gọi là đỉ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ên không âm c(e) = c[u, v] và gọi là khả năng thông qua của cung đó (capacity).

Ta quy ước nếu mạng không có cung (u, v) thì ta thêm vào cung (u, v) với khả năng thông qua c[u, v] bằng 0.
Với một mạng G = (V, E, c), ta ký hiệu:

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.

Luồng trên mạng

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

Tính chất của luồng

Với tập B ⊆ V, ký hiệu:

W^-(B) = { (a, b) ∈ E | a ∉ B, b ∈ B } - tập cạnh từ ngoài B đi vào B.

W⁺(B) = { (a, b) ∈ E | a ∈ B, b ∉ B } - tập cạnh từ B đi ra khỏi B.

Khi đó nếu tập con các đỉnh B không chứa x0 và z thì: t (W^-(B)) =t (W⁺(B)).Theo tính chất b) của luồng: ∑ t (W^-(x)) =∑ t (W⁺(x)).

Cạnh kề với đỉnh x nếu có đỉnh đầu và đỉnh cuối đều nằm trong tập B thì nó sẽ có mặt ở cả hai vế củađẳng thức đúng một lần, do đó có thể giản ước.

Giá trị của luồng

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 thứ t.

val(f) = t(W⁺(s)) = t(W^-(t))

Thumb — Hình 1: Luồng cực đại với giá trị luồng và khả năng thông qua của từng cặp cạnh. 1 là đỉnh phát, 6 là đỉnh thu.

Ứng dụng thực tế. Ví dụ

Xét đồ thị tương ứng hệ thống ống dẫn dầu. Trong đó các ống tương ứng với các cung, điểm phát là tàu chở dầu, điểm thu là bể chứa, các điểm nối của ống là các nút của đồ thị. Khả năng thông qua của các cung tương ứng là tiết diện các ống. Cần phải tìm luồng dầu lớn nhất có thể bơm từ tàu chở dầu vào bể chứa.
Xác định cường độ lớn nhất của dòng vận tải giữa 2 nút của một bản đồ giao thông.
Bài toán cặp ghép: có m chàng trai và n cô gái. Mỗi chàng trai ưa thích một số cô gái. Hãy tìm cách ghép cặp sao cho số cặp ghép được là nhiều nhất.

Bài toán luồng cực đại trên mạng:

Lát cắt. Đường tăng luồng

Định nghĩa. Ta gọi 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*=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.

Bổ đề 1. giá trị của mọi luồng f trong mạng luôn nhỏ hơn bằng khả năng thông qua lát cắt (X,X*) bất kỳ trong nó: val(f) £ c(X,X*).

Hệ quả 1. 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. Giả sử f là một luồng trong mạng G = (V,E). Từ mạng G = (V,E) ta xây dựng đồ thị có trọng số trên cung Gf =(V,Ef), với tập cung Ef và trọng số trên các cung được xác định theo quy tắc sau:

 *  Nếu e = (v,w) ∈ E với f(v,w) = 0, thì (v,w)∈ Ef với trọng số c(v,w);
 *  Nếu e = (v,w) ∈ E với f(v,w) = c(v,w), thì (w,v)∈ Ef với trọng số f(v,w);
 *  Nếu e = (v,w) ∈ E với 0 <f(v,w) < c(v,w), thì (v,w)∈ Ef với trọng số c(v,w) - f(v,w) và (w,v) ∈ Ef với trọng số f(v,w).

Các cung của Gf đồng thời cũng là cung của G được gọi là cung thuận, các cung còn lại gọi là cung nghịch. Đồ thị Gf được gọi là đồ thị tăng luồng.

Ví dụ: Các số viết cạnh các cung của G ở hình 1 theo thứ tự là luồng trên cung và khả năng thông qua

Đường tăng luồng. Giả sử P = (s = v0,v1,v2,…,vk= t) là một đường đi từ s đến t trên đồ thị tăng luồng Gf. Gọi d là giá trị nhỏ nhất của các trọng số của các cung trên đường đi P. Xây dựng luồng f' trên mạng G theo quy tắc sau:

  f(u,v) + d, nếu (u,v) ∈ P là cung thuận
  f(u,v) =  f(u,v) - d, nếu (u,v) ∈ P là cung nghịch
  f(u,v), nếu (u,v) không ∈ P

Dễ dàng kiểm tra được rằng f' được xây dựng như trên là luồng trong mạng và val(f')= val(f) + d. Ta sẽ gọi thủ tục biến đổi luồng vừa nêu là tăng luồng dọc theo đường P.

Sau biến đổi ta có luồng mới mang giá trị 9. val(f,) = 4 + 3 - 3 + 2 + 3 = 9

Thuật toán Ford-Fulkerson

Đến Thuật toán

Luồng cực đại với khả năng thông qua các cung và các đỉnh:

Giả sử trong đồ thị G = (V,E), ngoài khả năng thông qua của các cung c(u,v), ở mỗi đỉnh còn có khả năng thông qua của đỉnh là d(v), và đòi hỏi tổng luồng đi vào đỉnh v không còn vượt quá d(v), tức là ∑ f (w, v) < d(v), với w ∈ 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 hai đỉnh (v⁺ v^-) trong G’, mỗi cung (u,v) trong G ứng với cung (u,v⁺) trong G’ mỗi cung (v,w) trong G ứng vớ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.

Giải quyết bài toán Từ mạng G = (V,E) khả năng thông qua các cung và các đỉnh. Ta sẽ giải quyết theo hai bước sau:

* Xác định mạng G’. 
* Tìm luồng cực đại trong mạng G’. Bắt đầu từ luồng 0 với khả năng thông qua cung.

Ma trận biểu diễn đồ thị của bài toán luồng cực đại 1 Biểu diễn mạng G với khả năng thông qua các cung và đỉnh Giả sử mạng G = (V,E), |V| = n. Ta có thể biểu diễn bởi ma trận trọng số A cấp n x n như sau:

A=(a_{ij})={\begin{cases}d_{i}&{\text{nếu }}i=j\\c[i,j]&{\text{nếu }}[i,j]\in E\\0&{\text{nếu }}[i,j]\not \in E\end{cases}}

Trong đó: di là khả năng thông qua đỉnh i; C[i,j] khả năng thông qua cung [i,j].

2 Biểu diễn mạng G’ tương ứng với mạng G Mạng tương ứng với G = (V,E), |V | = n là mạng G’ = (V’,E’), |V’| = 2 |V |, |E’| = 2 |E | - 1. Được biểu diễn thông qua ma trận A’ cấp (2n x 2n) như sau: