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:

 
Đườ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.

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.

 
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 $i$ và $level$. 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.

 
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":

 
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$ và $\delta_P$ là trọng số của cung nhỏ nhất trong $P_f(s,t)$. Ta gọi $\delta_P$ là độ 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 = 0$ và $f'_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ó:

 
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.

 
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_0$ có $d[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ó:

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.