CHƯƠNG VIII: MỘT SỐ BÀI TOÁN QUAN TRỌNG CỦA ĐỒ THỊ
8.2. BÀI TOÁN TÌM LUỒNG CỰC ĐẠI TRÊN MẠNG
Bài toán. Cho một đồ có hướn G = <V, E>, V = { x1, x2,.., xn}. Với mỗi cung (xi, xj) có một số qij gọi là khả năng thông qua của cung. Đồ thị có hai đỉnh đặc biệt: đỉnh s gọi là đỉnh phát, đỉnh t gọi là đỉnh thu. Tập hợp các số zij xác định trên các cung (xi,xj)∈E gọi là luồng trên các cung nếu thỏa mãn:
∑ ∑
Γ
∈ ∈Γ− ⎪⎩
⎪⎨
⎧
−
=
−
)
( i 1( ) 0
j x j i
x x x
ki
ij v
v z
z
0 ≤ zij≤ qij với mọi (i,j) ∈V . cho các đỉnh còn lại.
nếu x = t, nếu x = s,
Trong đó, Γ(xi) là tập hợp các cung đi ra khỏi xi, Γ-1(xi) là tập hợp các cung đi ra khỏi xi. Giá trị v được gọi là giá trị luồng. Bài toán được đặt ra là tìm luồng có giá trị v lớn nhất.
Thuật toán Ford-Fullkerson: Tư tưởng thuật toán được bắt đầu từ một luồng chấp nhận nào đó (có thể là luồng có giá trị 0), sau đó ta thực hiện tăng luồng bằng cách tìm các đường đi tăng luồng. Để tìm đường đi tăng luồng ta áp dụng phương pháp đánh dấu các đỉnh. Nhãn của một đỉnh sẽ chỉ ra theo các cun nào có thể tăng luồng và tăng được bao nhiêu. Mỗi khi tìm được đườn đi tăng luồng, ta tăng luồng theo đường đi đó, sau đó xóa hết tất cả các nhãn và sử dụng luồng mới thu được để đánh dấu lại các đỉnh. Thuật toán kết thúc khi không tìm đường đi tăng luồng nào cả.
Khi xét các đỉnh của đồ thị, mỗi đỉnh của mạng sẽ ở một trong ba trạng thái: đỉnh chưa có nhãn, đỉnh có nhãn nhưng chưa được xét đến, đỉnh có nhãn và đã xét. Nhãn của một đỉnh xi gồm có hai phần thuộc một trong hai dạng sau:
Dạng thứ nhất: (+xj, σ(xi)), có nghĩa là có thể tăng luồng theo cung (xj, xi) với lượng lớn nhất là σ(xi).
Dạng thứ 2: (-xj, σ(xi)), có nghĩa là có thể giảm luồng theo cung (xj, xi) với lượng lớn nhất là σ(xi).
Quá trình gán nhãn cho đỉnh tương ứng với thủ tục tìm đường đi tăng luồng từ s đến x.
Thuật toán gán nhãn được thực hiện thông qua các bước sau:
Bước 1. Đánh dấu đỉnh s bởi nhãn (+s,+∞). Đỉnh s là đỉnh có nhãn và chưa xét, tất cả các đỉnh còn lại đều chưa có nhãn.
Bước 2. Chọn một đỉnh có nhãn nhưng chưa xét, chẳng hạn đỉnh xi, với nhãn là (±xk, σ(xi)).
Đối với đỉnh xi này ta xác định hai tập:
K+(xi) = { xj: xj ∈Γ(xi), zij <qij, xj chưa có nhãn}
K-(xi) = { xj: xj ∈Γ-1(xi), zji >0, xj chưa có nhãn}
Với mỗi đỉnh xj∈ K+(xi) ta gán cho nhãn (-xi, σ(xj)), trong đó σ(xj) = min { σ(xi), zij}.
Với mỗi đỉnh xj∈ K-(xi) ta gán cho nhãn (-xi, σ(xj)), trong đó σ(xj) = min { σ(xi), zji}.
Bây giờ đỉnh xi đã có nhãn và đã xét, còn các đỉnh xj∈K+(xi) và xj∈K-(xj) đã có nhãn nhưng chưa được xét.
Bước 3. Lặp lại bước 2 cho đến khi một tron hai khả năng sau xảy ra:
Đỉnh t được đánh dấu, chuyển sang bước 4.
Đỉnh t không có nhãn và không thể đánh dấu tiếp tục được nữa. Khi đó luồng đang xét là luồng cực đại. Nếu kí hiệu X0 là tập các đỉnh có nhãn, Y0 là tập các đỉnh không có nhãn thì (X0,Y0) sẽ là lát cắt hẹp nhất. Thuật toán dừng.
Bước 4. Đặt x=t.
Bước 5. Tiến hành tăng luồng:
Nếu đỉnh x có nhãn là (+u, σ(x)) thì tăng luồng theo cung (u,x) từ z(u,x) lên z(u,x)+
σ(t).
Nếu đỉnh x có nhãn là (-u, σ(x)) thì giảm lượng vận chuyển trên cung (u,x) từ z(u,x) xuống còn (z(u,x)- σ(t)).
Bước 6. Nếu u=s thì xóa tất cả các nhãn và quay lại bước 1 với luồng đã điều chỉnh ở bước 5. Nếu u≠s thì đặt x=u và quay lại bước 5.
Ví dụ. Tìm luồng cực đại của đồ thị G=<V,E> được cho như dưới đây.
x3
4 4 1
x1 x4 2 x6
2 4 2
x2 2 x5
Hình 8.2. Mạng G=<V,E>
Giải. Kí kiệu Vx là tập các đỉnh có nhãn và đã xét, Vc là tập các đỉnh có nhãn nhưng chưa xét.
Lần lặp số 1. Xuất phát từ luồng zij =0 với mọi i,j
Bước 1. Gán nhãn cho x1 là (+x1, ∞). Ta có Vx=φ, Vc = {x1}.
Bước 2. Xét đỉnh x1, ta có
K+(x1) = { x2, x3}, K-(x1) = φ.
Nhãn của x2 là {+x1, min(∞, 2-0)}=(+x1,2).
Nhãn của x3 là {+x1, min(∞, 4-0)}=(+x1,4).
Hai tập Vx = {x1}, Vc={ x2, x3} Bước 2. chọn đỉnh x2 đã xét, ta có
K+(x2) = { x4, x5}, K-(x2) = φ.
Nhãn của x4 là {+x2, min(2, 4-0)}=(+x2,2).
Nhãn của x5 là {+x2, min(2, 2-0)}=(+x2,2).
Hai tập Vx = {x1, x2 }, Vc={ x3, x4, x5 }.
Bước 2. xét đỉnh x4, ta có
K+(x4) = { x6}, K-(x4) = φ.
Nhãn của x6 là {+x4, min(2, 2-0)}=(+x4,2).
Đỉnh t = x6 đã được gán nhãn.
Bước 4. Đặt x = t.
Bước 5. Đỉnh x = x6 có nhãn là (+u, σ(x))= (+x4,2). Tăng luồng trên cung ( x4, x6 ) từ 0 lên 0+σ(t)=2.
Bước 6. Vì u=x4≠ s nên đặt x= x4.
Bước 5. Đỉnh x= x4 có nhãn là (+u, σ(x)) =(+x2,2). Tăng luồng trên cung (x2,x4) từ 0 lên 0 +σ(t)=2.
Bước 6. Vì u = x2 ≠ s nên đặt x = x2.
Bước 5. Đỉnh x = x2 có nhãn (+u, σ(x)) =(+x1, 2). Tăng luồng trên cung (x1,x2) từ 0 lên 0+σ(t)=2.
Bước 6. Vì u = x1 =s nên xóa tất cả các nhãn và quay lại bước 1.
Lần lặp thứ 2:
Bước 1. Gán nhãn cho x1 là (+x1,∞), Vx=φ, Vc= {x1}.
Bước 2. Xét đỉnh x1, ta có
K+(x1) = { x3}, K-(x1) = φ.
Nhãn của x3 là {+x1, min(∞, 4-0)}=(+x1,4).
Hai tập Vx = {x1}, Vc={ x3}.
Bước 2. xét đỉnh x3, ta có
K+(x3) = { x4, x5}, K-(x3) = φ.
Nhãn của x6 là {+x3, min(4, 1-0)}=(+x3,1).
Đỉnh t = x6 đã được gán nhãn.
Bước 4. Đặt x = t.
Bước 5. Đỉnh x = x6 có nhãn là (+u, σ(x))= (+x3,1). Tăng luồng trên cung ( x3, x6 ) từ 0 lên 0+σ(t)=1.
Bước 6. Vì u=x3≠ s nên đặt x= x3.
Bước 5. Đỉnh x= x3 có nhãn là (+u, σ(x)) =(+x1,4). Tăng luồng trên cung (x1,x3) từ 0 lên 0 +σ(t)=1.
Bước 6. Vì u = x1 =s nên xóa tất cả các nhãn và quay lại bước 1.
Lần lặp thứ 3:
Bước 1. Gán nhãn cho x1 là (+x1,∞), Vx=φ, Vc= {x1}.
Bước 2. Xét đỉnh x1, ta có
K+(x1) = { x3}, K-(x1) = φ.
Nhãn của x3 là {+x1, min(∞, 4-1)}=(+x1,3).
Hai tập Vx = {x1}, Vc={ x3}.
Bước 2. Xét đỉnh x3, ta có
K+(x3) = { x4}, K-(x3) = φ.
Nhãn của x4 là {+x3, min(3, 4-0)}=(+x3,3).
Hai tập Vx = {x1, x3}, Vc={ x4}.
Bước 2. Xét đỉnh x4, ta có
K+(x4) = φ, K-(x4) = {x2}.
Nhãn của x2 là {-x4, min(3, 2)}=(-x4,2).
Hai tập Vx = {x1, x3, x4}, Vc={ x2}.
Bước 2. Xét đỉnh x2, ta có
K+(x2) = {x5}, K-(x2) = φ.
Nhãn của x5 là {+x2, min(3, 2-0}=(x2,2 ).
Hai tập Vx = {x1, x3, x4,x2}, Vc={ x5}.
Bước 2. Xét đỉnh x5, ta có
K+(x5) = {x6}, K-(x5) = φ.
Nhãn của x6 là {+x5, 2). Đỉnh t = x6 đã được gán nhãn.
Dùng bước 4, 5 và 6 ta tìm được đường đi tăng luồng là:
x1 →x3 → x4 ← x2 → x5 → x6
Trên các cung thuận ta tăng vận chuyển lên một lượng là σ(t) = 2, trên cung ngược ta giảm vận chuyển đi một lượng là σ(t).
Lần lặp thứ 4:
Bước 1. Gán nhãn cho x1 là (+x1,∞), Vx=φ, Vc= {x1}.
Bước 2. Xét đỉnh x1, ta có
K+(x1) = { x3}, K-(x1) = φ.
Nhãn của x3 là {+x1, 1}.
Hai tập Vx = {x1}, Vc={ x3}.
Bước 2. Xét đỉnh x3, ta có
K+(x3) = { x4}, K-(x3) = φ.
Nhãn của x4 là {+x3, min(1, 4-2)}=(+x3,1).
Hai tập Vx = {x1, x3}, Vc={ x4}.
Bước 2. Xét đỉnh x4, ta có K+(x4) = φ, K-(x4) = φ.
Tại bước này ta không thể đánh nhãn tiếp tục được nữa, đỉnh t =x6 không được gán nhãn.
Vậy luồng luồng chỉ ra như trên là luồng cực đại. Lát cắt hẹp nhất là X0 = {x1, x3, x4}, Y0= {x2, x5, x6}.