Trong post này, chúng ta tìm hiểu 3 biến thể khác nhau của bài toán luồng cực đại:

1. Luồng với nhiều đỉnh phát và đỉnh thu (multiple sources, multiple sinks)
2. Luồng với định mức của cạnh (maximum flow with edge demands)
3. Luồng cực đại có chi phí nhỏ nhất (min-cost maximum flow)

Hai biến thể đầu tiên, ta áp dụng phép quy dẫn để quy về bài toán luồng cơ bản. Bài toán thứ 2 chúng ta sẽ áp dụng thuật toán Bellman-Ford để tìm luồng có chi phí cực tiểu. Trong bài này, ta kí hiệu $G$ là mạng đầu vào.

Luồng với nhiều đỉnh phát và đỉnh thu

Trong biến thể này, mạng của chúng ta, ngoài khả năng thông qua, còn có một tập các đỉnh phát $S = \{s_1,s_2,\ldots, s_k\}$ và một tập các đỉnh thu $T = \{t_1,t_2,\ldots, t_\ell\}$. Xem ví dụ minh họa trong Figure 1(a). Luồng trong mạng này được định nghĩa là hàm $f: V\rightarrow \mathbb{R}^+$ thỏa mãn điều kiện thông qua và điều kiện bảo toàn luồng tại mọi đỉnh trong $V\setminus (S\cup T)$. Giá trị của luồng $f$ được định nghĩa là tổng luồng đi ra tại tất cả các đỉnh trong $S$:

$|f(G)| = \sum_{i=1}^k \partial f(s_i) \qquad (1)$

Bài toán của chúng ta là tìm một luồng có giá trị cực đại trong mạng.

Để quy về bài toán luồng cực đại với một đỉnh phát, một đỉnh thu mà chúng ta đã biết cách giải, ta sẽ thêm vào 2 đỉnh mới $s'$ và $t'$. Ta sẽ nối $s'$ với mỗi đỉnh phát $s_i$ bằng một cung $s' \rightarrow s_i$ và nối mỗi đỉnh $t_j$ với đỉnh $t'$ bằng một cung $t_j\rightarrow t'$. Với mỗi cung mới thêm, ta gán cho nó khả năng thông qua là $+\infty$.Xem ví dụ minh họa trong Figure 1(b). Gọi $H$ là mạng thu được. Ta sẽ chứng minh tìm luồng cực đại trong $G$ có thể được quy về tìm luồng cực đại trong $H$, mạng chỉ có một đỉnh phát và một đỉnh thu.

Figure 1: (a) một luồng với nhiều đỉnh phát/thu (b) đồ thị quy dẫn.

 
Chứng minh: Gọi $f_G,f_H$ lần lượt là luồng cực đại trong $G$ và $H$. Trước hết, ta chứng minh $|f_G| \leq |f_H|$. Gọi $f_G$ là một luồng cực trong $G$. Ta sẽ chuyển luồng này thành một luồng trong $H$. Gọi $f'_H$ là luồng trong đó:

$f'_H(u\rightarrow v) = f_G(u\rightarrow v) \quad \forall u\rightarrow v \in G$

và

$f'_H(s'\rightarrow s_i) = \partial f_G(s_i) \quad \forall s_i \in S $

$f'_H(t_j\rightarrow t') = -\partial f_G(t_j) \quad \forall t_j \in T $

Ta có thể dễ dàng kiểm tra điều kiện thông qua của $f'_H$ vì các cạnh mới trong $H$ đều có khả năng thông qua vô hạn. Để kiểm tra điều kiện bảo toàn luồng, ta chỉ cần kiểm tra với các đỉnh thuộc $S\cup T$. Ta có thể kiểm tra trực tiếp dựa vào định nghĩa. Do đó, luồng $f'_H$ là một luồng hợp lệ trong $H$. Do đó, $|f'_H| \leq |f_H|$. Ngoài ra, do $|f'_H| = |f_G|$, ta suy ra dpcm.

Chứng minh $|f_H| \leq |f_G|$, ta làm tương tự. Chi tiết coi như bài tập cho bạn đọc.

Remark: Ta sử dụng khả năng thông $+\infty$ chỉ để trình bày được dễ hiểu. Ở đây, ta có thể thay $+\infty$ bằng tổng khả năng thông qua của tất cả các cung.

Luồng cực đại với định mức cạnh

Giả sử mạng của chúng ta chỉ có một đỉnh phát và một đỉnh thu. Tuy nhiên, mỗi cung $u\rightarrow v$, ngoài khả năng thông qua, còn có một định mức: $d(u\rightarrow v)$ cho biết lượng luồng ít nhất trên cung $u\rightarrow v$.

$f(u\rightarrow v) \geq d(u\rightarrow v) \quad \forall u\rightarrow v\in G \qquad (2) $

Điều kiện này được gọi điều kiện định mức. Một luồng được gọi là hợp lệ trong trường hợp này, ngoài điều kiện thông qua và bảo toàn luồng, còn phải thỏa mãn điều kiện định mức. Ví dụ một mạng với định mức cạnh trong Figure 2(a). Bài toán của chúng ta đặt ra là tìm một luồng cực đại với định mức của cung.

Trước hết chúng ta giải bài toán đơn giản hơn: tìm một luồng hợp lệ với định mức của cung. Nếu ta tìm được một luồng hợp lệ $f(.)$, chúng ta có thể tìm luồng cực đại với điều kiện định mức bằng cách tăng luồng hợp lệ $f(.)$ này sử dụng ý tưởng của Ford-Fulkerson. Thực ra, khâu khó nhất của bài toán luồng cực đại với định mức chính là tìm một luồng hợp lệ. Trong bài toán luồng cổ điển, luồng với giá trị 0 trên mọi cung là một luồng hợp lệ.

Ta sẽ quy bài toán tìm luồng hợp lệ bằng về bài toán luồng cực đại cổ điển như sau. Thêm vào $G$ hai đỉnh mới $s'$ và $t'$. Thiết lập khả năng thông qua mới $c'(.)$ như sau:

$\begin{array} {l} c'(u\rightarrow v) & = c(u\rightarrow v) - d(u\rightarrow v) \qquad \forall u\rightarrow v \in E \\ c'(s'\rightarrow v)& = \sum_{u\in V} d(u\rightarrow v) \qquad \forall v \in G \\ c'(v\rightarrow t')& = \sum_{w\in V} d(v\rightarrow w) \qquad \forall v \in G \\ c'(t\rightarrow s)& = +\infty \end{array} \qquad (3)$

Gọi đồ thị mới là $G'$. Chú ý, các cung trong $G'$ không có định mức (định mức bằng $0$). Figure 2(b) dưới đây minh họa phép quy dẫn áp dụng cho đồ thị ở Figure 2(a).

Figure 2: (a) Một mạng với định mức của cạnh. Với mỗi cung dạng $a/b$, $a$ là khả năng thông qua và $b$ là định mức. (b) Đồ thị quy dẫn về bài toán luồng cực đại cổ điển.
Ta sẽ chứng minh tìm luồng hợp lệ trong $G$ có thể quy về tìm luồng cực đại trong $G'$. Ta gọi luồng $f'(.)$ trong $G'$ là một luồng bão hòa nếu mọi cung đi ra từ $s'$ đều bị bão hòa. Một cách hình thức:

$f'(s'\rightarrow v) = c'(s\rightarrow v) \forall v\in G \qquad (4)$

Theo định lý luồng cực đại và lắt cắt cực tiểu, luồng bão hòa cũng chính là một luồng cực đại. Do đó, tìm luồng bão hòa trong $G'$ cũng chính là tìm luồng cực đại.

 
Chứng minh: Ta sẽ phải chứng minh hai chiều: (1) từ một luồng $f(.)$ hợp lệ của $G$, ta sẽ phải biến đổi nó thành một luồng bão hòa trong $G'$ và (2) từ một luồng bão hòa trong $G'$, ta phải biến đổi nó thành một luồng hợp lệ của $G$.

Chứng minh (1). Gọi $f(.)$ là một luồng hợp lệ của $G$. Ta sẽ gán cho mỗi cung của $G'$ một luồng với giá trị như sau:

$\begin{array} {l} f'(u\rightarrow v) & = f(u\rightarrow v) - d(u\rightarrow v) \qquad \forall u\rightarrow v \in E \\ f'(s'\rightarrow v)& = \sum_{u\in V} d(u\rightarrow v) \qquad \forall v \in G \\ f'(v\rightarrow t')& = \sum_{w\in V} d(v\rightarrow w) \qquad \forall v \in G \\ f'(t\rightarrow s)& = |f|\end{array} \qquad (4)$

Dễ thấy $f'(u'\rightarrow v') \geq 0$ với mọi cung $u'\rightarrow v'$ do $f(.)$ thõa mãn điều kiện định mức. Ngoài ra, ta dễ dàng kiểm tra được $f'(.)$ bão hòa các cung đi ra từ $s'$. Luồng $f'(.)$ thỏa mãn điều kiện thông qua do $f(.)$ thỏa mãn điều kiện thông qua. Ta chỉ còn phải kiểm tra điều kiện bảo toàn luồng của $f'(.)$. Ta thấy với mỗi đỉnh $u$ khác $s,t$ của $G'$, luồng đi vào $u'$ trong $G'$ bằng luồng đi vào $u$ trong $G$ và luồng đi ra từ $u'$ trong $G'$ bằng luồng đi ra từ $u$ trong $G$. Tại $s$, luồng đi ra có giá trị $|f|$ (giả sử luồng cực đại của $f$ của $G$ không có luồng quay ngược lại $s$). Do ta gán luồng trên cung $t\rightarrow s$$ cũng bằng $|f|$. Do đó, điều kiện bảo toàn luồng thỏa mãn với mọi đỉnh thuộc $G'$, ngoại trừ $s',t'$.

Chứng minh (2) tương tự như (1) và coi như bài tập cho bạn đọc.

Sau khi ta đã có được một luồng hợp lệ với định mức cạnh, ta sẽ sử dụng ý tưởng Ford-Fukerson để tìm đường tăng luồng trong đồ thị thặng dư và thực hiện tăng luồng để tìm luồng cực đại. Tuy nhiên, trong trường hợp này, chúng ta cần phải cần thận trong bước tăng luồng để đảm bảo luồng của các cung sau khi tăng vẫn phải thỏa mãn điều kiện định mức. Ta định nghĩa đồ thị thặng dư như sau. Với mỗi cung $u\rightarrow v$ có luồng $f(u\rightarrow v)$ không âm, ta định nghĩa 2 cung song song với trọng số:

$\begin{array} {l} c_f(u\rightarrow v) &= c_f(u\rightarrow v) - f(u\rightarrow v) \\ c_f(v\rightarrow u)& = c(v\rightarrow u) + f(u\rightarrow v) - d(u\rightarrow v) \end{array} \qquad (5)$

Sau đó, ta thực hiện tìm đường tăng luồng và tăng như trong thuật toán gốc của Ford-Fukerson.

Luồng cực đại có chi phí nhỏ nhất

Trong phiên bản này, ngoại trừ khả năng thông qua, mỗi cung $u\rightarrow v$ của $G$ còn có một chi phí $cost(u\rightarrow v)$. Chi phí này là chi phí phải trả cho mỗi đơn vị luồng trên cung. Chi phí của một luồng $f(.)$ trong $G$ được định nghĩa như sau:

$cost(f) = \sum_{u\rightarrow v \in E} cost(u\rightarrow v)f(u\rightarrow v) \qquad (6)$

Trong Figure 3 là một luồng cực đại với chi phí $234$.

Figure 3: Một luồng cực đại với chi phí. Mỗi cung có dạng $a/b/c$ trong đó $a$ là khả năng thông qua, $b$ là giá trị của luồng trên cung và $c$ là chi phí cho mỗi đơn vị của luồng.

Bài toán đặt ra cho chúng ta là trong số các luồng cực đại của $G$, tìm luồng cực đại có chi phí nhỏ nhất.

Nhìn dưới góc độ bài toán dẫn dầu như trong bài trước, một công ty muốn chuyển dầu qua mạng đường ống có sẵn sẽ phải trả tiền cho phần ống mà họ chuyển dầu qua. Công ty muốn chuyển được lượng dầu nhiều nhất với chi phí nhỏ nhất, họ sẽ phải tìm luồng cực đại với chi phí cực tiểu.

Ta sẽ giả sử đầu thì đầu vào $G$ không có cung song song, i.e, nếu $u\rightarrow v \in E$ thì $v\rightarrow u \not\in E$ và ngược lại. Tính chất này có thể được đảm bảo bằng cách thêm một đỉnh mới vào một trong 2 cung song song (xem lại kĩ thuật tương tự trong bài trước).

Ý tưởng của thuật toán gồm 2 bước: (1) Tìm một luồng cực đại trong $G$ mà chưa cần quan tâm đến chi phí và (2) thực hiện thay đổi luồng cực đại để thu được một luồng cực đại khác với chi phí nhỏ hơn. Bước (2) sẽ được lặp lại cho đến khi ta không thể thay đổi được luồng cực đại nữa thì luồng cuối cùng thu được sẽ là luồng cực đại có chi phí nhỏ nhất. Bước (1) ta có thể áp dụng bất kì thuật toán tìm luồng cực đại nào. Thực hiện bước (2), ta dựa trên nhận xét: "tăng" luồng dọc theo một chu trình có hướng (trong đồ thị thặng dư) không làm thay đổi giá trị cực đại của luồng.

Ví dụ trong Figure 4, hình (b) là luồng thu được sau khi tăng luồng cực đại trong Figure 3 dọc theo một chu trình của đồ thị thặng dư (chu trình màu đỏ). Luồng thu được sau khi tăng có giá trị 15, bằng giá trị của luồng trong Figure 3.

Figure 4: (a) Đồ thị thặng dư của luồng trong Figure 3 (b) Luồng cực đại thu được sau khi "tăng" luồng cực đại trong Figure 3 dọc theo chu trình màu đỏ trong (a).

Do đó, ta có thể thay đổi một luồng cực đại thành một luồng cực đại khác bằng cách tăng luồng dọc theo chu trình.

Để giảm chi phí của luồng cực đại mỗi khi thay đổi luồng, ta phải tìm một chu trình trong đồ thị thặng dư sao cho khi tăng luồng dọc theo chu trình này, chi phí của luồng cực đại sẽ giảm đi. Do đó, ta cần phải đưa thêm chi phí vào trong định nghĩa của đồ thị thặng dư, mà ta gọi là đồ thị chi phí thặng dư và kí hiệu là $G_{cf}$. Với mỗi cung $u\rightarrow v$ mà $f(u\rightarrow v)$ dương, ta định nghĩa cung ngược $v\rightarrow u$ trong $G_{cf}$ với trọng số $w_{cf}(v\rightarrow u) = -cost(u\rightarrow v)$. Nếu $f(u\rightarrow v)$ < $c(u\rightarrow v)$, ta định nghĩa cung $u\rightarrow v$ với trọng số $w_{cf}(u\rightarrow v) = cost(u\rightarrow v)$. Xem ví dụ trong Figure 5. Về cơ bản, đồ thị chi phí thặng dư có cấu trúc giống đồ thị thặng dư, chỉ khác trọng số ở đây là chi phí.

Figure 5: Đồ thị chi phí thặng dư của luồng trong Figure 3.

Ta sẽ tìm một chu trình âm trong $G_{cf}$ với trọng số $w_{cf}(.)$ (sử dụng Bellman-Ford chẳng hạn), và thực hiện tăng luồng dọc theo chu trình âm này. Dễ thấy sau khi tăng luồng, chi phí của luồng cực đại sẽ giảm đi $\delta_f*cost(C)$, trong đó $\delta_f$ là lượng luồng tăng dọc theo chu trình âm và $cost(C)$ là chi phí (trọng số) của chu trình âm. Trong Figure 5, chu trình âm tìm được là chu trình mà đỏ với chi phí $-6$ và $\delta_f = 2$ (xem Figure 4(b)). Do đó nêu tăng luồng dọc theo chu trình âm này, chi phí sẽ giảm đi $12$ đơn vị.

Phân tích thuật toán: Luồng cực đại có thể tìm được trong thời gian $O(VE)$ (sử dụng thuật toán Orlin[2]). Chu trình âm có thể tìm được trong thời gain $O(VE)$ sử dụng Bellman-Ford. Mỗi bước tăng luồng, chi phí của luồng cực đại giảm đi ít nhất 1 đơn vị. Do đó, cần tối đa $O(C)$ bước tăng luồng, trong đó $C$ là chi phí của luồng cực đại. Như vậy, ta có thể thực thi thuật toán này trong thời gian O(VEC). Tất nhiên đây không phải là thời gian đa thức vì $C$ có thể biểu diễn được bằng $O(\log C)$ bít. Một số kĩ thuật như Edmond-Karp cũng không áp dụng được ở đây vì bài toán tìm chu trình âm với chi phí nhỏ nhất và bài toán tìm chu trình âm có ít cạnh nhất đều là các bài toán NP-Hard. Goldberg và Tajan [3] đưa ra thuật toán tìm chu trình âm với chi phí trung bình nhỏ nhất (chi phí trung bình ở đây là chi phí trung bình trên mỗi cạnh) trong thời gian đa thức và chứng minh rằng phép tăng luồng sẽ kết thúc sau đa thưc bước, do đó, cho ta thuật toán thời gian đa thức.

Tham khảo

[1] J. Erickson. Maxflow Extensions Lecture Notes, UIUC, Fall 2013.
[2] J.B. Orlin.Max Flows in O (nm) Time, or Better. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pp. 765-774. ACM, 2013.
[3] A. V. Goldberg and R. E. Tarjan. Finding minimum-cost circulations by canceling negative cycles. J. Assoc. Comput. Mach., 36(4):873-886, 1989.