Luồng trong mạng II: Thuật toán Edmonds-Karp -- Network Flow II: Edmonds-Karp Algorithm

Trong bài trước, chúng ta đã tìm hiểu thuật toán Ford-Fulkerson tìm luồng cực đại trong mạng (có khả năng thông qua nguyên). Thuật toán Ford-Fulkerson, về cơ bản, bắt đầu từ một luồng hợp lệ f (ví dụ luồng 0), và thực lặp lại 3 bước sau cho đến khi thu được luồng cực đại:

  1. Tìm đồ thị thặng dư (residual graph) G_f.
  2. Tìm đường tăng luồng (agumenting path) từ s tới t trong G_f.
  3. Thực hiện tăng luồng dọc theo đường tăng luồng tìm được ở bước 2.

Ta đã chứng minh, sau mỗi bước tăng luồng, luồng sẽ được tăng lên ít nhất 1 đơn vị. Do đó, ta có thể thực thi thuật toán Ford-Fulkerson trong thời gian O((V+E)F); ở đây F là giá trị của luồng cực đại.

Tuy nhiên, thuật toán Ford-Fulkerson không phải là thuật toán thời gian đa thức vì giá trị của luồng cực đại F có thể chỉ biểu diễn được bằng \log F bít. Trong bài này, chúng ta sẽ tìm hiểu 2 cách tìm đường tăng luồng khác nhau, đề xuất bởi Edmonds và Karp [1]. Cả 2 cách này đều cho chúng ta thuật toán thời gian đa thức.

Thuật toán đường ngắn

Edmonds và Karp để xuất:

Chọn đường tăng luồng có ít cung nhất

 
Đường tăng luồng này có thể tìm được bằng cách áp dụng BFS (Breath-First Search) trong đồ thị thặng dư. Edmonds và Karp chứng minh rằng nếu ta chọn đường tăng luồng như vậy, thuật toán Ford-Fulkerson sẽ kết thúc sau O(VE) bước tăng luồng. Kết quả này thực sự là một kết quả ngạc nhiên, vì nó cho thấy có sự khác biệt cơ bản giữa DFS và BFS trong tìm đường tăng luồng. Tất nhiên, phần khó nhất vẫn là phân tích thuật toán, mà ta sẽ tìm hiểu dưới đây.

Theorem 1: Nếu áp dụng giải thuật BFS để tìm đường tăng luồng thì thuật toán Ford-Fukerson sẽ kết thúc sau EV/2 bước và qua đó, ta thu được thuật toán tìm luồng cực đại với thời gian O(E^2V).

 

Gọi G_1,\ldots, G_\ell là các đồ thị, trong đó, G_i là đồ thị thặng dư tại bước thứ i. Gọi level_i(u) là số cung của đường đi có ít cung nhất từ s tới u trong G_i. Theo định nghĩa này thì level_i(s) = 0. Về mặt trực quan, level(u) chính là khoảng cách ngắn nhất từ s tới u trong G_i nếu ta gán trọng số 1 cho mọi cung của G_i. Dễ thấy, level_i(u) \leq V với mọi u,i.

to-do:vẽ hình

Nhắc lại, một cung u\rightarrow v được gọi là bị bão hòa bởi luồng f nếu f(u\rightarrow v) = c(u\rightarrow v). Theo định nghĩa đồ thị tăng luồng, nếu một cung u\rightarrow v bị bão hòa bởi luồng f thì nó sẽ không xuất hiện (mà cung ngược của nó sẽ xuất hiện) trong đồ thị thặng dư G_f. Ta nói u\rightarrow v bị biến mất khỏi đồ thị thặng dư G_f.

Remark: Nếu một cung bị biến mất khỏi đồ thị G_i thì có thể nó lại xuất hiện ở đồ thị G_j với j\leq i+1.

Ý tưởng trong chứng minh Theorem 1 của Edmond và Karp đó là mỗi cung u\rightarrow v sẽ bị biến mất không quá O(V) lần trong toàn bộ quá trình tăng luồng, và do mỗi lần tăng luồng, ít nhất 1 cung sẽ bị biến mất (bão hòa), do đó, số lần tăng luồng tối đa là O(VE).

Trước hết, ta sẽ chứng minh rằng, sau mỗi lần tăng luồng, level của các đỉnh không bao giờ giảm xuống.

Lemma 1: Với mọi i,j sao cho j \geq i+1 và với mọi đỉnh v, ta có level_i(v) \leq level_j(v).

 
Chứng minh: Ta chỉ cần chứng minh Lemma 1 đúng cho trường hợp j = i+1. Ta sẽ chứng minh bằng quy nạp trên hai biến ilevel. Dễ thấy level_i(s) luôn bằng 0 với mọi i, do đó, Lemma đúng với s.

Gọi u\rightarrow v là một cung của G_{i+1} sao cho level_{i+1}(v) = level_{i+1}(u)+1. Theo quy nạp, level_{i+1}(u) \geq level_i(u). Ta cần chứng minh level_i(v) \leq level_{i+1}(v). Ta có hai trường hợp:

  1. Nếu u\rightarrow v \in G_i, theo định nghĩa của level ta suy ra:

    level_i(v) \leq level_i(u) + 1 \leq level_{i+1}(u) + 1 = level_{i+1}(v) \qquad (1)

  2. Nếu u\rightarrow v \not\in G_i, do u\rightarrow v \in G_{i+1}, ta suy ra tồn tại cung v\rightarrow u trong G_i và cung này bị biến mất (bị bão hòa) sau khi tăng luồng dọc theo đường tăng luồng chứa cung này. Do đường tăng luồng trong G_i là đường từ BFS, level_i(v) = level_i(u) - 1. Do đó,

    level_i(v) \leq level_{i+1}(u) -1 = level_{i+1}(v) -2 \qquad (2)

    Từ đó ta suy ra dpcm.


Lemma 2: Mỗi cung u\rightarrow v\in G bị biến mất không quá V/2 lần.

 
Chứng minh: Giả sử cung u\rightarrow v \in G_i và cung này bị biến mất sau khi tăng luồng tại bước i+1. Theo định nghĩa, ta có:

level_{i}(u) +1 = level_{i}(v)  \qquad (3)

Gọi j là chỉ số nhỏ nhất lớn hơn i sao cho cung u\rightarrow v lại xuất hiện trong G_{j}.

Do u\rightarrow v xuất hiện trong G_{j} (nhưng không ở trong G_{j-1}), cung ngược của nó v\rightarrow u là cung bị biến mất khỏi G_{j-1}. Do đó, ta có

level_{j-1}(u) = level_{j-1}(v) + 1 \qquad (4)

Do i\leq j-1, theo Lemma 1, ta suy ra level_i(v) \leq level_{j-1}(v). Kêt hợp với (3), (4), ta suy ra:

level_{i}(u) + 2 \leq level_{j-1}(v) + 1 = level_{j-1}(u) \leq level_j(u)

Hay nói cách khác, mỗi khi cung u\rightarrow v biến mất và sau đó lại xuất hiện, mức của u lại tăng lên ít nhất 2 đơn vị. Do level_i(u) \leq V với mọi u,i, cung u\rightarrow v biến mất không quá V/2 lần (dpcm).


Chứng minh Theorem 1: Do mỗi lần tăng luồng, ít nhất 1 cung bị biến mất. Do đồ thị có E cung và mỗi cung biến mất không quá V/2 lần (theo Lemma 2), số lần tăng luồng không quá VE/2 lần. Do ta có thể tìm đường tăng luồng sử dụng BFS trong thời gian O(V+E), tổng thời gian của thuật toán là O(VE^2).


Remark: Trong phân tích trên, ta không hề sử dụng điều kiện nguyên của khả năng thông qua. Do đó, thuật toán đường ngắn sẽ cho ta luồng cực đại trong thời gian O(VE^2) ngay cả khi khả năng thông qua không phải là nguyên.

Thuật toán đường béo

Ý tưởng của giải thuật khá "tự nhiên":

Chọn đường tăng luồng có lượng tăng luồng lớn nhất

 
Cuối bài, ta sẽ tìm hiểu cách tìm đường tăng luồng "béo" nhất (đường cho ta lượng tăng luồng lớn nhất) từ s đến t trong thời gian O(E\log V). Bay giờ chúng ta tạm thời thống nhất là đường béo có thể được tìm một cách hiệu quả. Câu hỏi tương tự phần trước là: thuật toán Ford-Fulkerson sẽ kết thúc sau bao nhiêu bước tăng luồng? Để trả lời câu hỏi này, chúng ta cần phải có cách nhìn khác về đường tăng luồng.

Nhắc lại, G_f là đồ thị thặng dư tương ứng với luồng f. Gọi P_f(s,t) là đường tăng luồng trong đồ thị G_f\delta_P là trọng số của cung nhỏ nhất trong P_f(s,t). Ta gọi \delta_Pđộ rộng của đường tăng luồng P_f(s,t). Đường "béo" nhất chính là đường có động rộng \delta_P lớn nhất. Nếu ta coi P_f(s,t) là một luồng trong đồ thị thặng dư, gọi là luồng thặng dư, thì luồng này có giá trị là \delta_P. Với cách nhìn đó, thay vì tăng luồng dọc theo đường tăng luồng, ta có thể tăng luồng (trong đồ thị gốc) dọc theo các cung có luồng không âm của luồng thặng dư, mà vẫn đảm bảo luồng sau khi tăng là một luồng hợp lệ. Ngoài ra, lượng tăng luồng sau mỗi bước tăng cũng đúng bằng giá trị của luồng thặng dư.

Remark: Bạn đọc cần phải phân biệt rõ ràng khái niệm luồng cực đại và luồng dư cực đại trước khi đọc tiếp. Luồng cực đại là luồng trong đồ thị gốc và luồng dư cực đại là luồng cực đại trong đồ thị thặng dư.

Ta gọi f^* là luồng cực đại (của đồ thị gốc). Gọi f_i là luồng sau khi thực hiện tăng luồng lần thứ i dọc theo đường tăng luồng béo nhất và f'_i là luồng thặng dư cực đại của đồ thị thặng dư G_{f_i}. Ban đầu f_0 = 0f'_0 = f^*. Theo phân tích ở trên, ta có:

f_i + f'_i = f^* \qquad (5)

Theo (5), ta dễ dàng suy ra nếu f_i được tăng lên một lượng \Delta (f_{i+1} = f_i +\Delta) thì f'_i sẽ bị giảm đi cùng một lượng \Delta (f'_{i+1} = f'_i -\Delta).

Cũng theo (5), nếu ta tìm được luồng dư cực đại thì chỉ cần 1 bước tăng luồng nữa là ta tìm được luồng cực đại trong đồ thị gốc. Tuy nhiên, tìm luồng dư cực đại không dễ hơn tìm luồng cực đại trong đồ thị gốc và chúng ta cũng không cố gắng đi tìm luồng dư cực đại. Ở đây, ta sẽ cố gắng liên hệ độ rộng của đường tăng luồng béo nhất với f'_i. Gọi \Delta_i là độ rộng của đường tăng luồng béo nhất trong đồ thị thặng dư G_{f_i}. Ta sẽ có:

Lemma 3:

\Delta_i \geq \frac{|f'_i|}{E} \qquad (6)

 
Chứng minh:Ta sẽ sử dụng theo định lý Ford-Fulkerson: khả năng thông qua của bất kì một lát cắt nào cũng lớn hơn giá trị của luồng cực đại. Gọi S_r là tập các đỉnh trong đồ thị thặng dư sao cho với mỗi v \in S_r, tồn tại một đường đi từ s tới v sao cho mọi cung trên đường đi này đều có trọng số lớn hơn (nhưng không bằng) \Delta_i. Gọi T_r = V\setminus S_r. Rõ ràng, t  \in T_r, vì nếu không, ta sẽ tìm được đường đi từ s đến t với độ rộng lớn hơn \Delta_i; điều này trái với định nghĩa của \Delta_i.

Theo định nghĩa của S_r, mọi cung từ S_r tới T_r đều có trọng số nhỏ hơn hoặc bằng \Delta_i. Do lát cắt (S_r,T_r) có tối đa E cung, ta có:

c(S_r,T_r) \leq E\Delta_i \qquad (7)

Kết hợp với định lý Ford-Fulkerson, ta suy ra điều phải chứng minh.


Lemma 4: Thuật toán Ford-Fulkerson sẽ kết thúc sau E\ln(|f^*|)+ 1 bước tăng luồng nếu ta tăng luồng dọc theo đường béo nhất.

 
Chứng minh: Theo nhận xét từ (5), mỗi bước ta tăng luồng của đồ thị gốc một lượng \Delta_i thì luồng dư cực đại cũng bị giảm đi \Delta_i. Do đó:

|f'_{i+1}| = |f'_i| - \Delta_i

Theo Lemma 3, ta có \Delta_i \geq \frac{|f'i|}{E}, ta suy ra:

|f'_{i+1}| \leq (1 -  \frac{1}{E})|f'_i| \qquad (8)

Từ (8), ta suy ra |f'_k| \leq (1 -  \frac{1}{E})^k |f'_0 | = (1 -  \frac{1}{E})^k |f^*|. Khi k = E\ln(|f^*|), ta có:

|f'_k| \leq (1 -  \frac{1}{E})^{E \ln(|f^*|)}|f^*| \leq \frac{1}{e^{\ln(|f^*|)}}|f^*|  = 1

Ở đây, ta sử dụng bất đẳng thức (1 -  \frac{1}{E})^E \leq \frac{1}{e} , e là cơ số của logarithm tự nhiên. Như vậy, luồng dư cực đại tại bước thứ k có giá trị không quá 1. Do khả năng thông qua là nguyên, ta chỉ cần tăng luồng thêm một lần nữa thì luồng dư cực đại tại bước k+1 sẽ là 0. Lúc đó, theo (5), luồng trong đồ thị gốc thu được là luồng cực đại.


Tìm đường tăng luồng rộng nhất: Tư tưởng tìm đường rộng nhất giống như tư tưởng tìm đường đi ngắn nhất của thuật toán Dijkstra. Mình sẽ không đi sâu vào chi tiết mà chỉ lượt qua ý tưởng cơ bản. Ta bắt đầu từ đỉnh s và xây dựng "cây đường đi béo nhất" (thay vì cây đường đi ngắn nhất trong Dijkstra) có gốc tại s. Với mỗi đỉnh u\in S, đường đi (duy nhất) từ s tới u trong cây chính là đường đi béo nhất trong G_f từ s tới u. Mỗi bước, ta sẽ thêm một đỉnh vào cây này (ban đầu cây chỉ có một đỉnh là s). Với mỗi đỉnh u không thuộc cây, gọi d[u] là trọng số của cung lớn nhất u\rightarrow v với v là đỉnh thuộc cây đã xây dựng. Nếu đỉnh u không có cung nào như vậy thì coi d[u] = 0. Ta sẽ thêm vào cây đỉnh u_0d[u_0] lớ nhất. Tiếp tục lặp lại cho đến khi ta thêm t vào cây, và đường đi béo nhất tương ứng sẽ là đường đi từ s tới t trên cây.

Chứng minh tính đúng đắn mình coi như bài tập cho bạn đọc (mình khuyến khích bạn đọc xem lại chi tiết và cách chứng minh thuật toán Dijkstra). Cũng như Dijkstra, thuật toán này có thể thực thi trong thời gian O((V+E)\log V). Kết hợp với Lemma 4, ta có:

Theorem 2: Thuật toán Edmonds-Karp với đường béo tìm luồng cực đại trong thời gian O(E^2\log V\ln(|f^*|))

 

Remark: Trong giải thuật đường béo, ta có sử dụng tính nguyên của khả năng thông qua để chứng minh tính dừng của giải thuật.

Tham khảo

[1] J. Edmonds and R.M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. Journal of the ACM (JACM) 19.2 (1972): 248-264.
[2] J. Erickson. Maxflow Algorithm Lecture Notes, UIUC, Fall 2013.

Facebook Comments

Tags: ,

Reply

Your email address will not be published. Required fields are marked *