Lát cắt, đường tăng luồng, định lý Ford_fullkerson
Định nghĩa 9.3. 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 * = VX, trong đó s ∈ X, t ∈ X * . Khả năng thông qua của lát cắt (X, X * ) là số c(X,X * ) ...
Định nghĩa 9.3.
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* = VX, trong đó s ∈ X, t ∈ X* . Khả năng thông qua của lát cắt (X, X*) là số
c(X,X*) = c(v,w) v ∈ X w ∈ 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ổ đề 9.1.
Giá trị của 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 (X, X*) bất kỳ trong nó: val(f) ≤ c(X, X*).
Chứng minh.
Cộng các điều kiện cân bằng luồng Divf(v)=0 với mọi v∈ X. Khi đó ta có
( f(w,v ) - f(v,w) ) = -Val(f) v∈ X w∈ N-(v) w∈ N+(v)
tổng này sẽ gồm các số hạng dạng f(u,v) với dấu cộng hoặc dấu trừ mà trong đó có ít nhất một trong hai đỉnh u,v phải thuộc tập X. Nếu cả hai đỉnh u,v đều trong tập X, thì f(u,v) xuất hiện với dấu cộng trong Divf(v) và với dấu trừ trong Divf(u), vì thế, chúng triệt tiêu lẫn nhau. Do đó, sau khi giản ước các số hạng như vậy ở vế trái, ta thu được
- f(v,w) + f(v,w) = -val(f), v ∈ X v ∈ X*w∈ X* w∈ X
hay là
val(f) = f(v,w) - f(v,w) v ∈ X v ∈ X* w∈ X* w ∈ X
Mặt khác, từ điều kiện 1 rõ ràng là
f(v, w) ≤ c(v, w) v ∈ X v ∈ X* w∈ X* w∈ X
còn
- f(v,w) ≤ 0 v ∈ X*w∈ X
suy ra val(f)≤c(X, X*). Bổ đề được chứng minh.
Hệ quả 9.2.
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.
Ford và Fulkerson đã chứng minh rằng giá trị luồng cực đại trong mạng đúng bằng khả năng thông qua của lát cắt hẹp nhất. Để có thể phát biểu và chứng minh kết quả này chúng ra sẽ cần thêm một số khái niệm.
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 qui 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 được gọi là cung nghịch. Đồ thị Gf được gọi là đồ thị tăng luồng.
Ví dụ 9.1:
Các số viết cạnh các cung của G ở hình 9.1 theo thứ tự là khả năng thông qua và luồng trên cung.
Hình 9.1 Mạng G và luồng f. Đồ thị có trọng số G f tương ứng.
Giả sử P = (s = v0, v1, . . . , vk = t) là một đường đi từ s đến t trên đồ thị tăng luồng Gf. Gọi ε 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 theo qui tắc sau:
| f(u,v) + ε , nếu (u,v) ∈ P là cung thuận | |
| f’(u,v) = | f(u,v) - ε , nếu (v,u) ∈ P là cung nghịch |
| f(u,v), nếu (u,v) ∈ 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) + ε . 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.
Định nghĩa 9.4.
Ta gọi đường tăng luồng f là mọi đường đi từ s đến t trên đồ thị tăng luồng G(f).
Định lý 9.3
Các mệnh đề dưới đây là tương đương:
(i) f là luồng cực đại trong mạng;
(ii) không tìm được đường tăng luồng f;
(iii) val(f) = c(X,X*) với một lát cắt (X, X*) nào đó.
Chứng minh.
(i) ⇒ (ii). Giả sử ngược lại, tìm được đường tăng luồng P. Khi đó ta có thể tăng giá trị luồng bằng cách tăng luồng dọc theo đường P. Điều đó mâu thuẫn với tính cực đại của luồng f.
(ii) ⇒ (iii). Giả sử không tìm được đường tăng luồng. Ký hiệu X là tập tất cả các đỉnh có thể đến được từ đỉnh s trong đồ thị Gf, và đặt X*=VX. Khi đó (X, X*) là lát cắt, và f(v,w) = 0 với mọi v ∈ X*, w ∈ X nên
val(f) = f(v,w) - f(v,w) = f(v,w) v ∈ X v ∈ X* v∈ X w∈ X* w∈ X w∈ X*
Với v ∈ X, w ∈ X*, do (v,w) ∈ Gf, nên f(v,w) = c(v,w). Vậy
val(f) = f(v,w) = c(v,w) = c(X,X*) v ∈ X v ∈ X w∈ X* w∈ X*
(iii) ⇒ (i). Theo bổ đề 9.1, val(f) ≤ c(X,X*) với mọi luồng f và với mọi lát cắt (X,X*). Vì vậy, từ đẳng thức val(f) = c(X,X*) suy ra luồng f là luồng cực đại trong mạng.
