Bài này là bài đầu tiên trong chuỗi bài về luồng trong mạng(network flow). Trong bài viết này, chúng ta sẽ tìm hiểu:

1. Một số khái niệm cơ bản về luồng.
2. Phát biểu và chứng minh định lý luồng cực đại - lát cắt cực tiểu
3. Giải thuật Ford-Fulkerson tìm luồng cực đại trong đồ thị và một số hệ quả thú vị từ giải thuật này

Luồn trong mạng là một bài toán có lịch sử khá dài và được nghiên cứu dưới góc độ khoa học máy tính từ năm 1956 với thuật toán Ford-Fulkerson [1]. Sau đó, rất nhiều các giải thuật khác nhau (mà ta sẽ nghiên cứu một số tại blog này) đã được đề xuất nhằm cải tiến thuật toán Ford-Fulkerson. Nếu liệt kê các công trình về luồng thì có lẽ phải mất đến cả chục trang giấy. Ahuja, Magnanti và Orlin [2] xuất bản cuốn sách dầy gần 900 trang về bài toán này. Mặc dù vậy, cho đến gần đây (2013), Orlin [3] mới giải quyết được gần như hoàn toàn được bài toán luồng với thời gian $O(VE)$. Về ứng dụng của luồng thì có lẽ rất khó để liệt kê toàn bộ. Chúng ta sẽ tìm hiểu một số ứng dụng trong những bài viết sau này.

Một số khái niệm

Đầu vào của chúng ta là một đồ thị $G(V,E)$ có hướng, và có trọng số không âm. Ta kí hiệu cung (khái niệm cạnh dành cho đồ thị vô hướng) có hướng từ $u$ tới $v$ bởi $u \rightarrow v$. Trọng số trong ngữ cảnh bài toán này được gọi là khả năng thông qua (capacity) và thường kí hiệu là $c(.)$. Do đó, $c(u\rightarrow v)$ sẽ là khả năng thông qua của cung $u\rightarrow v$. Đồ thị $G(V,E)$ có hai đỉnh đặc biệt, ta kí hiệu là $s$ và $t$, trong đó $s$ được gọi là đỉnh phát (source) và $t$ được gọi là đỉnh thu (sink).

Luồng $(s,t)$ ($(s,t)$-flow) được định nghĩa là một hàm $f$, gán cho mỗi cung $u\rightarrow v$ một số không âm $f(u\rightarrow v)$ thỏa mãn đều kiện bảo toàn luồng (conservation constraint) tại mọi đỉnh $v$ của đồ thị, ngoại trừ $s$ và $t$:

$\sum_{u}f(u\rightarrow v) = \sum_{w}f(v\rightarrow w) \qquad (1)$

Về mặt trực quan, phương trình $(1)$ có thể hiểu là tổng luồng đi vào đỉnh $v$ bằng tổng luồng đi ra khỏi đỉnh $v$.

Ngoài ra, chúng ta còn muốn giá trị của luồng tại một cạnh không được vượt quá khả năng thông qua của cạnh đó.

$f(u\rightarrow v) \leq c(u\rightarrow v)\quad \forall u\rightarrow v \in E \qquad (2)$

Phương trình $(2)$ được gọi là điều kiện thông qua (capacity constraint) của luồng $f$. Một luồng thỏa mãn cả điều kiện bảo toàn và điều kiên thông qua được gọi là một luồng hợp lệ. Trong bài này, ta chỉ xét các luồng hợp lệ.

Với mỗi đỉnh $v$, ta định nghĩa $\partial f(v) = \sum_{w}f(v\rightarrow w) - \sum_{u}f(u\rightarrow v)\$ là tổng luồng thực đi ra (out net-flow) khỏi đỉnh $v$. Điều kiện bảo toàn luồng cho ta biết, ngoại trừ $s,t$ thì $\partial f(v) = 0$ với mọi $v$. Ta định nghĩa giá trị của luồng, kí hiệu là $|f|$, là tổng luồng thực đi ra khỏi $s$:

$|f| = \partial f(s) = \sum_{w}f(s\rightarrow w) - \sum_{u}f(u\rightarrow s) \qquad (3)$

Dễ thấy, luồng đi ra từ một đỉnh thì phải đi vào một đỉnh khác, do đó:

$\sum_{v \in V} \partial f(v) = 0 \qquad (4)$

Vì $\partial f(v) = 0 \quad \forall v \not\in \{s,t\}$, ta suy ra $\sum_{v \in V} = \partial(s) + \partial(t)$. Kết hợp với $(4)$, ta có:

$\partial f(s) = -\partial(t) \qquad (5)$

Ý nghĩa của $(5)$ là: tổng luồng đi ra từ $s$ bằng tổng luồng đi vào từ $t$. Xem hình minh họa trong Figure 1. Trong Figure 1(b), mỗi cung được chú thích theo dạng $c/f$ trong đó số màu xanh là khả năng thông qua và số màu đỏ là giá trị của luồng. Luồng trong hình có giá trị 10. Ta có thể dễ dàng kiểm tra các tính chất đã phát biểu ở trên cho luồng trong Figure 1(b).

Figure 1: (a) đồ thị đầu vào và (b) một luồng hợp lệ trên đồ thị đầu vào.

Cung $u\rightarrow v$ được gọi là bị bão hòa (saturated) bởi luồng $f$ nếu $f(u\rightarrow v) = c(u\rightarrow v)$. Ngược lại, cung $u\rightarrow v$ được gọi là chưa bị bão hòa. Trong Figure 1(b), cung $s\rightarrow a$ là cung bị bão hòa và cung $a\rightarrow b$ là cung chưa bị bão hòa.

Trong thực tế, ta có thể hình dung đồ thị $G(V,E)$ như một mạng đường ống dẫn dầu với khả năng thông qua của mỗi cung là lượng dầu tối đa có thể chuyển qua đường ống thông giữa 2 điểm đầu cuối của cung đó. Ta có thể coi một luồng $(s,t)$ giống như một cách chuyển dầu từ $s$ tới $t$. Tưởng tượng ta sẽ bơm dầu vào $s$ và lấy dầu đi ra từ $t$. Ngoại trừ $s,t$, rõ ràng tại một điểm nút của mạng đường ống này (tương ứng với đỉnh của đồ thị), lượng dầu đi vào điểm nút phải bằng lượng dầu đi ra khỏi điểm nút đó. Ta có thể thấy, bằng cách xác định luồng $f$ trên mỗi cạnh thỏa mã điều kiện thông qua và điều kiện bảo toàn luồng, ta đã xác định được một cách chuyển dầu từ $s$ tới $t$.

Trong thực tế, ta muốn biết xem mạng dẫn dầu cho trước có thể chuyển được tối đa bao nhiêu dầu? Hay nói cách khác, ta muốn xác định một luồng có giá trị $|f|$ cực đại. Đây chính là mục tiêu mà chúng ta hướng đến.

Quan hệ với bài toán lát cắt cực tiểu

Trong bài viết về cây khung, mà cụ thể là thuật toán Prim, trước đây, chúng ta đã tìm hiểu khái niệm lát cắt cho đồ thị vô hướng. Trong bài này, ta sẽ tìm hiểu khái niệm lát cắt cho đồ thị vô hướng, và khả năng thông qua của lát cắt.

Một lát cắt $(s,t)$ ($(s,t)$-cut) là một phân hoạch tập đỉnh $V$ thành hai tập $S$ và $T$ sao cho:

1. $S \cap T = \emptyset$.
2. $S \cup T = V$.
3. $s \in S$ và $t \in T$.

Khả năng thông qua của lát cắt $(S,T)$ được định nghĩa như sau:

$c(S,T) = \sum_{u\in S}\sum_{v\in T}c(u\rightarrow v) \qquad (6)$

Đó chính là tổng khả năng thông qua của các cung $u\rightarrow v$ có đầu mút $u \in S$ và $v \in T$. Chú ý ta không tính các cung ngược từ $T$ sang $S$. Ví dụ với Figure 1(a) ở trên, nếu lấy $S = \{s,a\}$ ( và $T = V\setminus S$ thì $C(S,T) = 20$. Chú ý, theo định nghĩa, ta không tính khả năng thông qua của cung $c\rightarrow a$ trong ví dụ này.

Về mặt trực quan, do điều kiện thông qua, tổng luồng đi từ $S$ sang $T$ không thể vượt quá khả năng thông qua của lát cắt $S,T$. Ta sẽ chứng minh điều này một cách hình thức trong Lemma sau:

 
Chứng minh: Ta có:

$\begin{array} {l} |f| & = \partial f(s) \\ & = \sum_{v \in S}\partial f(v) \\&= \sum_{v \in S}(\sum_{w\in V}f(v\rightarrow w) - \sum_{u\in V}(u\rightarrow v)) \\ &= \sum_{v \in S}(\sum_{w\in T}f(v\rightarrow w) - \sum_{u\in T}f(u\rightarrow v)) \\ &\leq \sum_{v \in S}(\sum_{w\in T}f(v\rightarrow w)) \\ &\leq \sum_{v \in S}(\sum_{w\in T}c(v\rightarrow w)) \\ &= c(S,T)\end{array} \qquad (8)$

Phương trình đầu tiên là do định nghĩa của $|f|$. Phương trình thứ 2 là theo điều kiện bảo toàn luồng. Phương trình thứ 3 là theo định nghĩa của $\partial f(v)$. Phương trình thứ 4 là do với mỗi cùng $u\rightarrow v$ với $u,v\in S$, thì $f(u\rightarrow v)$ xuất hiện với dấu + trong $\partial f(u)$ và dấu - trong $\partial f(v)$, do đó, triệt tiêu nhau. Phương trình thứ 5 là do $f$ không âm. Phương trình thứ 6 là do điều kiện thông qua, và phương trình cuối cùng là theo định nghĩa $c(S,T)$.

Từ Lemma 1 ta suy ra giá trị của luồng cực đại (luồng có $|f|$ lớn nhất) luôn nhỏ hoặc bằng hơn khả năng thông qua của lát cắt cực tiểu (lát cắt có $c(S,T)$ nhỏ nhất). Ford và Fulkerson [1] còn chứng minh được, thông qua thuật toán Ford-Fulkerson, rằng giá trị của luồng cực đại bằng khả năng thông qua của lát cắt cực tiểu. Trong phần tiếp theo, ta sẽ tìm hiểu thuật toán này.

 
Thuật toán Ford-Fulkerson

Để trình bày được đơn giản hơn, ta sẽ giả sử đồ thị $G$ của chúng ta không có cung song song, kể cả song song ngược chiều. Nói cách khác, nếu $u\rightarrow v\in G$ thì $v\rightarrow \not\in G$. Cuối bài chúng ta sẽ tìm hiểu cách để loại bỏ giả sử này. Ngoài ra, ta giả sử khả năng thông qua của mỗi cạnh là một số nguyên. Cuối bài ta cũng thảo luận tại sao lại có giả sử này.

Trước khi trình bày thuật toán chi tiết, chúng ta hãy thử nghĩ một vài phương án có thể cho ta lời giải.

Expriemental thought

Ta bắt đầu với ví dụ trong Figure 1(b). Luồng này đã cực đại hay chưa? Câu trả lời là chưa, vì ta có thể chuyển thêm 2 đơn vị luồng dọc theo đường:

$s\rightarrow c \rightarrow d\rightarrow b\rightarrow t $

để thu được luồng trong Figure 2(a). Luồng mới này có giá trị 12. Tại sao không tăng 3 dọc theo đường này mà lại tăng 2? Dễ thấy nếu tăng 3 thì luồng trên cung $d\rightarrow b$ sẽ vượt quá khả năng thông qua của nó.

Nhận xét này cho chúng ta một ý tưởng: xây dựng đồ thị $H(V,E)$ với cùng tập đỉnh và cạnh của $G$ nhưng với trọng số $c_H(u\rightarrow v) = c(u\rightarrow v) - f(u\rightarrow v)$. Figure 2(b) minh họa là đồ thị $H$ và trọng số của nó; $H$ được xây dựng từ Figure 1(b).

Figure 2: (a) luồng thu được sau khi tăng 2 đơn vị dọc theo đường màu đỏ trong hình, và (b) đồ thị "luồng dư" $H$ thu được từ luồng trong Figure 1(b).

Sau khi đã xây dựng được $H$, ta sẽ tìm một đường đi từ $s$ tới $t$ trong $H$, kí hiệu $P_H(s,t)$ (đường màu đỏ trong Figure 2(b)). Gọi $\delta$ là cạnh có trọng số ($c_H(.)$) nhỏ nhất trong đường đi này ($\delta = 2$ trong ví dụ Figure 2(b)). Ta sẽ cộng thêm luồng trên đường đi tương ứng $P_G(s,t)$ trong $G$ với $\delta$, và như vậy ta đã tìm được luồng lớn hơn. Ta có thể tiếp tục lặp lại cho đến khi không tìm được đường nào nữa.

Cách này liệu có cho ta luồng tối ưu: câu trả lời là không. Nếu ta xây dựng đồ thị "luồng dư" $H$ như trên cho đồ thị và luồng trong Figure 2(a), ta sẽ thu được đồ thị trong Figure 3(a) dưới đây. Rõ ràng đồ thị này không có đường đi từ $s$ tới $t$, do đó ta không thể lặp lại thủ tục trên. Tuy nhiên, luồng trong Figure 2(a) không phải luồng cực đại. Luồng cực đại được minh họa trong Figure 3(b) với giá trị 15 (tại sao luồng này cực đại?). Làm thế nào mà ta có thể tìm được luồng này? Hay nói cách khác, làm thế nào mà ta có thể tiếp tục "tăng" được luồng trong Figure 2(b)? Đó chính là nội dung của phần tiếp theo.

Figure 3: (a) đồ thị "luồng dư" $H$ thu được từ luồng trong Figure 2(b), và (b) một luồng cực đại của đồ thị trong hình Figure 1(a).

Thuật toán

Thuật toán Ford-Fulkerson cũng xây dựng một đồ thị, $G_f(V,D)$ từ đồ thị $G(V,E)$ gọi là đồ thị luồng dư (residual graph). Sau đó, tìm một đường đi từ $s$ tới $t$ trong đồ thị luồng dư này, gọi là đường tăng luồng (agumenting path), và sau đó, tăng luồng của $G$ dọc theo luồng này.

Tuy nhiên, điểm khác biệt cơ bản của thuật toán Ford-Fulkerson so với ý tưởng trong phần experimental thought đó là cách xây dựng đồ thị luồng dư $G_f(V,D)$. Với mỗi cung $u\rightarrow v \in G$ có luồng $f(u\rightarrow v)$ > $0$, ta tạo ra 2 cung song song $u\rightarrow v$ và $v\rightarrow u$ trong $G_f$, và ta gán cho mỗi cung đó một trọng số (ta KHÔNG dùng khái niệm khả năng thông qua cho $G_f$ ) $c_f(.)$ như sau:

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

Theo định nghĩa này thì $G_f$ có cung song song trong khi $G$ không có.

Tại sao lại thêm một cung ngược $v\rightarrow u$ với trọng số $f(u\rightarrow v)$? Lí do là vì ta có thể "tăng" luồng theo cung ngược bằng cách giảm luồng theo cung xuôi, và lượng giảm lớn nhất theo cung xuôi có thể là $f(u\rightarrow v)$ (nếu giảm quá thì luồng bị âm).

Liệu cách mới này có cho ta đường tăng luồng? Kiểm tra với đồ thị và luồng trong Figure 2(a), đồ thị luồng dư tương ứng được minh họa trong Figure 4(a).

Figure 4: (a) Đồ thị luồng dư $G_f$ của luồng trong Figure 2(a) và (b) một đường tăng luồng trong $G_f$ từ $s$ đến $t$.

Bằng cách xây dựng luồng như Ford-Fulkerson, ta tìm được một đường tăng luồng từ $s$ tới $t$, chính là đường màu đỏ trong Figure 4(b). Đường này có $\delta = 3$.Tăng luồng dọc theo đường này, ta sẽ thu được luồng cực đại trong Figure 3(b). Chú ý cung $d\rightarrow a$ trong đường màu đỏ ở Figure 4(b). Cung này không thuộc $G$, do đó, tăng luồng dọc theo cung này chính là giảm luồng theo cung xuôi $a\rightarrow d$ (để ý trong Figure 3(b), cung này bị giảm luồng so với Figure 2(b)).

Điều ngạc nhiên là bằng cách xây dựng luồng dư như Ford-Fulkerson, và áp dụng thủ tục tăng luồng lặp đi lặp lại cho đến khi không còn đường tăng luồng nào trong đồ thị luồng dư, ta thu được luồng lớn nhất.

Giả mã:

Code C:

#define INFTY 100000000
int **C;	// the capacity matrix of the input graph
int **CF;	// the weighted adjacency matrix of the residual graph
int **F;	// the flow
int n,m;	// the number of vertices and arcs of the graph
int s,t;	// the source and the sink of the network

int *P;	   // the agumenting path, P[u] = v if u->v is in the path and we set P[t] = t

void FordFulkerson(){
// initialize the flow
F = (int **)(malloc(n*sizeof(int*)));
int i = 0;
for(i = 0; i < n; i++){
F[i]  = (int *)malloc(n*sizeof(int));
memset(F[i], 0 , n*sizeof(int));
}
while(1){
BuildResidualGraph();
FindAugmentingPath();
if (P[s] == -1){// there is no augmenting path
break;
}
int delta = INFTY;
int v = s;
while(P[v] != v){ // note that P[t] = t
delta = (CF[v][P[v]] < delta? CF[v][P[v]] : delta);
v = P[v];
}
Augment(delta);
}
}

Ta sẽ lần lượt giải thích các thủ tục trong thuật toán Ford-Fulkerson ở trên. Thủ tục ResidualGraph xây dựng đồ thị luồng dư từ $G$ và luồng hiện tại $f$. Chú ý đồ thị $G$ ta đã giả sử là không có cạnh song song ngược chiều.

Giả mã:

 
Code C:

void BuildResidualGraph(){
int i = 0;
for(i = 0; i < n; i++){
memset(CF[i],0 , n*sizeof(int)); // clear CF
}
int u = 0, v = 0;
for(u = 0;u < n; u++){
for(v = 0; v < n; v++){
if(C[u][v] > 0){
CF[u][v] = C[u][v] - F[u][v];
if(F[u][v] > 0) CF[v][u] = F[u][v];
}
}
}
}

Thủ tục FindAgumentingPath tìm một đường đi từ $s$ tới $t$ trong đồ thị luồng dư $G_f$. Giải thuật tìm đường có thể chọn là DFS, BFS. Mặc dù các giải thuật tìm đường khác nhau cho ta thuật toán khác nhau, trong phân tích ở phần này, giải thuật tìm đường là gì không quan trọng. Do đó, ta sẽ bỏ qua phần mô tả giả mã của thủ tục này.

Code C:

int *P;	   // the agumenting path, P[u] = v if u->v is in the path  and we set P[t] = t
int *Q;			// the reversal path of P
int *visited;	// to mark visited vertices by DFS
void FindAugmentingPath(){
// using DFS to find an augmenting path
memset(visited, 0, n*sizeof(int));
memset(Q,-1,n*sizeof(int));
memset(P,-1,n*sizeof(int));
visited[s] = 1;
Q[s] = s;
DFS(s);
// conver the path Q from t to s to the path P from s to t
P[t] = t;	// t is the end of the path
int v = t;
while(Q[v] != v && Q[v] != -1){
P[Q[v]] = v;
v = Q[v];
}
if(v != s){		// there is no agumenting path
P[s] = -1;	// mark P[s] = -1
}
}

void DFS(int v){
int i = 0;
for(i = 0; i < n; i++){
if(i != v && visited[i] == 0 && CF[v][i] > 0){
Q[i] = v;
visited[i] = 1;
DFS(i);
}
}
}

Thủ tục Augment thực hiện tăng luồng của đồ thị gôc $G$ dọc theo đường tăng luồng đã tìm được ở bước trứơc. Lượng tăng luồng ở đây là $\delta$, trọng số nhỏ nhất trên đường $P$. Chú ý ở đây, $P$ là đường đi trong $G_f$, do đó, cung của nó có thể không thuộc $G$. Nếu cung nào đó của $P$ không thuộc $G$, theo định nghĩa của $G_f$, cung ngược của nó phải thuộc $G$. Do đó, tăng luồng dọc theo cung này tương đương với giảm luồng theo cung ngược.

 
Code C:

void Augment(int delta){
int i = 0;
// augment
int v = s;
while(P[v] != v){
if(C[v][P[v]] > 0) F[v][P[v]] += delta;
else F[P[v]][v] -= delta;
v = P[v];
}
}

Tính đúng đắn của thuật toán Ford-Fulkerson

Chứng minh tính đúng đắn của thuật toán Ford-Fulkerson ở trên không hề đơn giản. Mình sẽ chia chứng minh thành các bước nhỏ để bạn đọc theo dõi dễ hơn.

Trước hết, ta chứng minh luồng sau khi tăng là một luồng hợp lệ:

 
Chứng minh: Gọi $f$ và $f'$ lần lượt là luồng trước khi tăng và sau khi tăng. Theo giả thiết, $f$ là một luồng hợp lệ, i.e, $f$ thỏa mãn điều kiện bảo toàn luồng và điều kiện thông qua. Gọi $P$ là một đường tăng luồng tìm được trong $G_f$. Để chứng minh Lemma 2, ta phải chứng minh điều kiện thông qua và điều kiện toàn luồng của $f'$.

Trước hết, ta chứng minh điều kiện bảo toàn luồng. Do luồng chỉ thay đổi trên các cung dọc theo $P$, ta chỉ cần chứng minh $\partial f'(v) = 0$ với mọi $v \in P \setminus \{s,t\}$. Gọi $u\rightarrow v$ và $v\rightarrow w$ là 2 cung liên tiếp thuộc $P$. Ta sẽ có 4 trường hợp, phụ thuộc vào 2 cung này có thuộc $G$ hay không. Ở đây mình chỉ chứng minh 2 trường hợp, các trường hợp còn lại chứng minh tương tự.

• Nếu cả 2 cung này đều thuộc $G$ thì ta có thể thấy ngay $\partial f'(v) = \partial f(v) = 0$, vì lượng tăng luồng tại cung $f(u\rightarrow v)$ bằng lượng tăng luồng cung $f(v\rightarrow w)$. Trường hợp 2 cung đều không thuộc $G$ chứng minh tương tự.
• Trường hợp có đúng một trong 2 cung, giả sử $u\rightarrow v \not \in G$ và $v\rightarrow w \in G$. Theo định nghĩa, đại lượng $\partial f'(v) - \partial f(v)$ chính là lượng tăng luồng trên cung $v\rightarrow w$ trừ đi lượng giảm luồng trên cung $v\rightarrow u$. Theo cách chúng ta tăng luồng, lượng luồng tăng trên cung $v\rightarrow w$ chính bằng lượng luồng giảm trên cung $v\rightarrow u\in G$. Do đó, $\partial f'(v) = \partial f(v) = 0$

Tiếp theo, ta chứng minh $f'$ thỏa mãn điều kiện thông qua. Ta chỉ cần chứng minh điều kiện thông qua với các cung trong $E$ mà nó hoặc cung ngược của nó nằm trên $P$. Gọi $u\rightarrow v \in E$ là một cung có luồng thay đổi. Ta xét hai trường hợp:

• $(u\rightarrow v) \in P$, dễ thấy $f'(u\rightarrow v) \geq 0$ vì ta chỉ tăng luồng theo cung này. Ngoài ra, do $c_f(u\rightarrow v) \geq \delta$, theo định nghĩa của $\delta$. Thay $c_f(u\rightarrow v) = c(u\rightarrow v) - f(u\rightarrow v)$ và $f'(u\rightarrow v) = f(u\rightarrow v) + \delta$, ta thu được $f'(u\rightarrow v) \leq c(u\rightarrow v)$ (dpcm).
• $(u\rightarrow v) \not\in P$ (suy ra $v\rightarrow u \in P$), dễ thấy $f'(u\rightarrow v) \leq c(u\rightarrow v)$ vì luồng chỉ giảm trên cung $u\rightarrow v$. Chứng minh $f'(u\rightarrow v)\geq 0$ tương tự như trường hợp đầu, do đó, ta bỏ qua chi tiết ở đây.

Như vậy $f'$ là một luồng hợp lệ.

Tiếp theo, ta sẽ chứng minh sau mỗi lần tăng luồng, giá trị của luồng luôn tăng.

 
Chứng minh: Trước hết ta thấy rằng, do khả năng thông qua là nguyên, bằng quy nạp, ta chứng minh được mọi luồng trung gian có giá trị nguyên, vì ta bắt đầu bằng một luồng nguyên và mỗi bước ta thay đổi một lượng $\delta$ cũng là số nguyên. Ngoài ra, lượng luồng đi ra từ $s$ tăng $\delta$ đơn vị sau khi tăng luồng, và do $\delta$ nguyên, lượng tăng này ít nhất là $1$ đơn vị.

Tiếp theo, ta sẽ chứng minh sau khi thuật toán Ford-Fulkerson kết thúc, i.e, $G_f$ không có đường nào nối $s$ và $t$, thì luồng thu được là cực đại.

 
Chứng minh: Theo Lemma 3 và chứng minh của Lemma 3, sau mỗi bước tăng luồng, luồng thu được có giá trị nguyên và tăng ít nhất 1 đơn vị. Trong mỗi bước tăng luồng, ta có thể:

1. Tìm đồ thị luồng dư trong thời gian $O(V+E)$, do đồ thị luồng dư có $V$ đỉnh và tối đa $2E$ cung.
2. Tìm đường tăng luồng trong đồ thị luồng dư trong thời gian $O(V+E)$ sử dụng BFS/DFS.
3. Tăng luồng dọc theo đường tăng luồng trong thời gian $O(V+E)$.

Do đó, ta có thể thực thị mỗi bước tăng luồng là $O(V+E)$, và như vậy thuật toán sẽ kết thúc tối đa sau $F$ bước tăng luồng, cho ta thuật toán $O((V+E)F)$.

Giờ ta chỉ cần chứng minh luồng thu được sau khi thuật toán kết thúc là một luồng cực đại. Ta sẽ dựa vào Lemma 1. Gọi $f'(.)$ là luồng thu được sau khi thuật toán kết thúc. Ta sẽ chứng minh khi $s$ và $t$ không liên thông trong $G_{f'}$ thì tồn tại một lắt cát $(S,T)$ sao cho $c(S,T) = |f'|$. Theo Lemma 1, luồng $f'(.)$ phải là luồng cực đại.

Gọi $S$ là tập tất cả các đỉnh $v$ sao cho tồn tại ít nhất một đường đi có hướng từ $s$ tới $v$ trong $G_{f'}$ và $T = V\setminus S$. Ta sẽ chứng minh $c(S,T) = |f'|$. Ta có nhận xét:

• $f'(v\rightarrow u) =c(u\rightarrow v)$ với mọi $v \in S, u\in T$ vì nếu không $c_{f'}(v\rightarrow u)$ > $0$, và do đó, có cung $u\rightarrow v \in G_{f'}$. Hay nói cách khác, $v\in S$, điều này trái với định nghĩa của $S$.
• $f'(w\rightarrow u) = 0$ với mọi $w\in T, v\in S$ vì nếu không, theo định nghĩa của luồng dư, $G_{f'}$ sẽ có cạnh ngược $v\rightarrow w$ với trọng số dương. Hay nói cách khác, $w\in S$, trái với định nghĩa của $S$.

Từ nhận xét trên, kết hợp điều kiện dấu bằng của phương trình $(8)$, ta suy ra $|f'| = c(S,T)$.

Để phân tích thời gian, ta chỉ cần nhận xét mỗi bước tăng luồng có thể thực thi trong thời gian $O(V+E)$ bằng cách sử dụng BFS/DFS tìm đường tăng luồng trong $G_f$, và số bước tăng luồng tối đa là $F$ bước.

Một hệ quả dễ thấy từ chứng minh của Theorem 2 đó là tồn tại một lắt cắt $(S,T)$ có khả năng thông qua chính bằng giá trị của luồng cực đại. Kết quả này chính là Theorem 1 mà ta phát biểu ở trên. Trong phần tới, ta quay lại trường hợp $G$ có cung song song.

Đồ thị có cung song song

Nếu đồ thị đâu vào có cung song song, cách đơn giản nhất là với mỗi cung song song $u\rightarrow v$ và $v\rightarrow u$, ta xóa cung $u\rightarrow v$ và thêm 2 cung mới $u\rightarrow w, w\rightarrow v$ với cùng khả năng thông qua bằng nhau và bằng $c(u\rightarrow v)$ (xem Figure 5). Tiếp tục làm như vậy ta sẽ loại bỏ được cung song song. Về mặt phức tạp, đồ thị cuối cùng sẽ có tối đa $V + E$ đỉnh và $2E$ cung, do đó độ phức tạp của thuật toán FordFulkerson cuối cùng vẫn là $O((V+E)F)$ (tất nhiên ta sẽ phải cài đặt sử dụng danh sách kề).

Figure 5: (a) cung song song trong $G$ và (b) loại bỏ cung song song bằng cách thêm một đỉnh mới.

Cách thứ 2 là ta giữ nguyên đồ thị đầu vào, và thay đổi cách định nghĩa đồ thị luồng dư. Tại mỗi bước của thuật toán, ta sẽ đảm bảo rằng, với mọi cung song song $u\rightarrow v$ và $v\rightarrow u$, tối đa một cung có luồng dương. Nghĩa là nếu $f(u\rightarrow v)$ > $0$ thì $f(v\rightarrow u) = 0$ và ngược lại. Với luồng như vậy, ta sẽ định nghĩa trọng số $c_f(.)$ của đồ thị luồng dư như sau: Với mỗi cung $u\rightarrow v \in G$ có $f(u\rightarrow v)$ > $0$,

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

Phép tìm đường tăng luồng và phép tăng, giảm luồng vẫn không thay đổi. Chứng minh tính đúng đắn thì chỉ cần thay đổi một chút chứng minh ở trên.

Remark 1: Trong thuật toán FordFulkerson, ta không thể bỏ điều kiện nguyên của khả năng thông qua của các cung. Zwick [5] đã chứng minh được rằng nếu khả năng thông qua không nguyên thì thuật toán FordFulkerson có thể lặp vô hạn. Xem thêm ví dụ cụ thể trong Note của Erickson [4].

Remark 2: Thời gian chạy $O((V+E)F)$ của thuật toán Ford-Fulkerson KHÔNG phải là thời gian đa thức, do giá trị luồng cực đại $F$ có thể biểu diễn được chỉ sử dụng $\log_2 F$ bít. Lí do chính là thuật toán Ford-Fulkerson không quy định cách ta tìm đường tăng luồng. Do đó, ta có thể tìm phải những đường tăng luồng chỉ cho ta đúng 1 đơn vị tăng luồng sau mỗi bước tăng. Xem ví dụ trong Figure 6

Figure 6: Trường hợp xấu của thuật toán Ford-Fulkerson.

Nếu ta chỉ chọn một trong hai đường $(s,a,b,t), (s,b,a,t)$ trong đồ thị $G_f$ để tăng luồng thì mỗi lần ta chỉ tăng được đúng 1 đơn vị luồng, trong khi luồng cực đại là $2\times 10^9$. Do đó, nếu không cẩn thận, ta phải tăng luồng 2 tỉ lần mới thu được luồng cực đại.

Trong loạt bài tiếp theo, ta sẽ nghiên cứu các cách tìm đường tăng luồng khác nhau, mỗi cách cho chúng ta một thuật toán thời gian đa thức để tìm luồng.

Code C: Code này mình giả sử đồ thị đầu vào không có cung song song. Download.

Tham khảo

[1] L.R. Ford and D.R. Fulkerson.Maximal Flow Through a Network. Canadian Journal of Mathematics 8.3 (1956): 399-404.
[2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice–Hall, Upper Saddle River, NJ, 1993
[3] 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.
[4] J. Erickson. Maxflow Algorithm Lecture Notes, UIUC, Fall 2013.
[5] U. Zwick. The Smallest Networks on which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate. Theoretical Computer Science 148.1 (1995): 165-170.