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.

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.

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à khả năng thông qua và luồng trên cung
Đườ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:
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:
Như thí dụ trên có mạng G như sau:
Tương tự mạng G'
Áp dụng Thuật toán Ford-Fulkerson tìm luồng cực đại cho mạng G’ ta được mạng cực đại và ma trận biểu diễn nó như sau