Cho đồ thị vô hướng $G(V,E)$, với trọng số $w(.): E\rightarrow \mathbb{R}^+$ không âm. Gọi $X,Y \subseteq V$ là hai tập đỉnh rời nhau, i.e, $X \cap Y = \emptyset$. Ta sẽ sử dụng $(X,Y)$ để kí hiệu tập các cạnh của đồ thị có đúng một đầu mút trong $X$ và đầu mút còn lại trong $Y$. Trọng số của tập cạnh $(X,Y)$, kí hiệu là $w(X,Y)$, được định nghĩa là tổng trọng số của các cạnh trong $(X,Y)$:
$w(X,Y) = \sum_{e \in (X,Y)}w(e) \qquad (1)$
Gọi $A\subseteq V$ là một tập đỉnh con của đồ thị. Một lát cắt tương ứng với $A$ là tập cạnh $(A,V\setminus A)$. Bài toán đặt ra cho chúng ta là thiết kế thuật toán hiệu quả để tìm lát cắt cực tiểu. Bài viết này giới thiệu giải thuật Stoer-Wagner tìm lát cắt cực tiểu trong thời gian $O(VE + V^2\log V)$. Theo mình, đây là một thuật toán khá đơn giản (chứng minh tính đúng đắn hơi phức tạp) và cần phải được phổ biến rộng rãi hơn nữa.
Remark 1: Ta có thể áp dụng bài toán luồng cực đại để tìm lát cắt cực tiểu. Cụ thể, với mỗi cặp $u,v$, ta sẽ tìm một lát cắt $u,v$ cực tiểu trong đồ thị $G(V,E)$ áp dụng luồng cực đại. Thuật toán nhanh nhất tìm luồng cực đại (do đó lắt cắt cực tiểu) là $O(VE)$. Bằng cách thử tất cả các cặp $u,v$ (có $O(V^2)$ cặp) và lấy min, ta có thể tìm được lắt cắt cực tiểu trong thời gian $O(V^3E)$. Ta có thể giảm thuật toán này xuống còn $O(V^2E)$ bằng cách gộp đỉnh, như thuật toán trình bày dưới đây. Tuy nhiên, độ phức tạp vẫn khá lớn. Ngoài ra thực thi luồng trong thời gian $O(VE)$ không hề đơn giản.
Remark 2: Thuật toán Stoer-Wagner về cơ bản có nhiều điểm tương đồng với thuật toán Prim tìm cây khung nhỏ nhất. Đặc biệt trong cách thực thi của thuật toán này, ta có thể áp dụng nhiều nhận xét trong các thực thi thuật toán Prim. Do đó, mình khuyến khích (nhưng không bắt buộc) bạn đọc xem lại thuật toán Prim trước khi đọc phần thực thi thuật toán.
Thuật toán Stoer-Wagner
Gọi $T$ là một cây (không nhất thiết là cây khung) trong đồ thị $G$. Gọi $v$ là một đỉnh không nằm trong $T$. Độ kết dính (stickiness) của $v$ với $T$, kí hiệu là $\ell(v,T)$, được định nghĩa là tổng trọng số của các cạnh từ $v$ tới các đỉnh trong $T$:
$\ell(v,T) = \sum_{u \in T}w(u,v) \qquad (2)$
Thuật toán Stoer-Wagner thực hiện theo từng pha (phase) độc lập với nhau. Mỗi pha thuật toán sẽ tìm một cây khung của đồ thị bằng cách liên tục thêm đỉnh vào cây khung hiện tại (điểm này giống thuật toán Prim). Trong số các đỉnh chưa được thêm vào cây, ta sẽ thêm đỉnh có độ kết dính lớn nhất với cây hiên tại. Trong giả mã dưới đây, mảng $L[1,\ldots, |V|]$ sẽ là mảng độ kết dính, i.e, $L[v] = \ell(v,T)$ với $T$ là cây khung xây dựng trong bước hiện tại.
$ n \leftarrow |V| $
if $n = 2$ $\ll$ the graph only has 2 vertices $\gg$
return $E$
for each $v \in V$
$L[v] \leftarrow 0$ $\ll L[v]$ is the stickiness of $v\gg$
$T\leftarrow \emptyset$
while $|T| \not= n$
$v \leftarrow $ MaxStickiness$(V\setminus T, L)$
$T\leftarrow T \cup \{v\}$
for each $u \in V\setminus T$
if $uv \in E$
$L[u] \leftarrow L[u] + w(u,v)$
if $|T| = n-2$
$s\leftarrow v$
if $|T| = n$
$t \leftarrow v$
Merge$(G, s,t)$
return $L[t]$
$C \leftarrow +\infty$
while $|V| \geq 2$
$C \leftarrow \min(C, $ MinCutPhase($G$)$)$
return $C$
Thủ tục MaxStickiness$(V\setminus T, L)$ trả lại đỉnh có độ kết dính với $T$ lớn nhất trong số các đỉnh nằm trong $V\setminus T$ (ta sẽ mô tả thủ tục này kĩ hơn trong phần thực thi thuật toán). Hai đỉnh $s,t$ trong giả mã trên là hai đỉnh cuối cùng được thêm vào cây. Theo định nghĩa $L[t]$ chính là độ kết dính của $t$ với cây $T$ tại bước cuối cùng, do đó:
$L[t] = \sum_{tu\in E}w(t,u) \qquad (3)$
Như vậy, thủ tục MinCutPhase($G(V,E)$) sẽ trả về tổng trọng số của các cạnh đi ra từ $t$, trong đó $t$ là đỉnh cuối cùng trong một pha của thuật toán.
Thủ tục Merge$(G, s,t)$ sẽ gộp hai đỉnh $s,t$ thành một đỉnh mới. Gọi $x$ là đỉnh mới sau khi gộp. Với mỗi $u \in V$, ta sẽ gán:
$w(x,u) = w(u,s) + w(u,t)\qquad (4)$
Trong phương trình $(4)$, ta coi $w(u,s) = 0$ nếu cạnh $us$ không nằm trong $E$. Tương tự như vậy với $w(u,t)$. Nếu tồn tại cạnh $st$ trong đồ thị, ta sẽ xóa cạnh này sau phép gộp. Ví dụ gộp hai cạnh $s,t$ được minh họa trong Figure 1.
Figure 1: Gộp hai đỉnh trong hình (a) thành một đỉnh trong hình (b).
Thủ tục StoerWagnerMinCut($G(V,E)$) sẽ trả lại giá trị nhỏ nhất trong tất cả các pha của thuật toán. Chú ý, mỗi pha ta sẽ gộp hai đỉnh lại làm một, do đó, tổng số pha tối đa là $V-1$. Trong các phân tích dưới đây, ta sẽ chứng minh rằng giá trị nhỏ nhất này chính là trọng số của lát cắt nhỏ nhất của $G$. Việc tìm lát cắt không khó, vì ta chỉ cần ghi lại lát cắt tương ứng với giá trị nhỏ nhất đó.
Trước khi đi sâu vào chi tiết phân tích thuật toán, ta sẽ thử xem thuật toán thực hiện như thế nào với đồ thị trong ví dụ sau.
Figure 2: Hình (a) là đồ thị đầu vào. Hình (b,c,d,e,f), mỗi hình tương ứng với một pha. Giá trị trả về của mỗi pha tương ứng là $4,5,4,2,4$. Do đó, giá trị cực tiểu trong tất cả các pha là $2$, và đây cũng chính là trọng số của lát cắt cực tiểu của đồ thị.
Điểm kì diệu của thuật toán Stoer-Wagner chính là mỗi pha của thuật toán sẽ trả lại trọng số của lát cắt cực tiểu giữa $s$ và $t$ ($s,t$ là hai đỉnh cuối cùng được xét trong mỗi pha).
Giả sử Lemma 1 là đúng (ta chứng minh sau), ta có:
Chứng minh: Gọi $(A,V\setminus A)$ là lát cắt cực tiểu của đồ thị. Ta xét pha hiện tại của thuật toán. Nếu $s \in A$ và $t\in V\setminus A$ thì theo Lemma 1, pha hiện tại sẽ trả về lát cắt cực tiểu giữa hai đỉnh $s$ và $t$. Do đó, lát cắt đó cũng là lát cắt cực tiểu của đồ thị.
Nếu cả hai đỉnh $s,t$ đều thuộc $A$ (trường hợp cả hai đỉnh thuộc $V\setminus A$ tương tự), ta có thể gộp hai đỉnh này vào làm một đỉnh $x$ và tìm lát cắt cực tiểu của đồ thị sau khi gộp. Do đó, [giá trị] lát cắt cực tiểu của đồ thị sau khi gộp cũng chính là [giá trị] lát cắt cực tiểu của đồ thị ban đầu. Pha tiếp sau đó của thuật toán Stoer-Wagner đi tìm chính lát cắt này. Do đó, thuật toán Stoer-Wagner trả về [giá trị] của lát cắt cực tiểu của đồ thị.
Chứng minh Lemma 1: Gọi $(A,V\setminus A)$ là một lát cắt giữa $s$ và $t$. Ta sẽ chứng minh, bằng quy nạp, lát cắt này có trọng số lớn hơn trọng số của lát cắt $(\{t\},V\setminus \{t\})$ (chính là $L[t]$). Gọi $v_1,v_2,\ldots, v_n$ là thứ tự các đỉnh được thêm vào $T$ trong thủ tục MinCutPhase($G(V,E)$). Ta có $v_{n-1} = s$ và $v_n = t$. Gọi $B_{i-1} = \{v_1,\ldots, v_{i-1}\}$. Đỉnh $v_i$ được gọi là đỉnh tới hạn (critical vertex) nếu $v_i$ và $v_{i-1}$ không cùng nằm trong $A$. Gọi $X_{i-1} = B_{i-1} \cap A$ và $Y_{i-1} = B_{i-1} \setminus X_{i-1}$. Gọi $C_i$ là tập các cạnh của lát cắt $(A,V\setminus A)$, sao cho đầu mút của các cạnh này chỉ nằm trong $B_{i}$. Một cách hình thức, ta có:
$ C_i = \begin{cases} (X_{i-1}\cup \{v_i\}, Y_{i-1}), & \mbox{if } v_i \in A\\ (X_{i-1}, Y_{i-1}\cup \{v_i\}), & \mbox{if } v_i\not\in A\end{cases} \qquad (5)$
Ta sẽ chứng minh, với mọi đỉnh tới hạn $v_i$:
$ w(\{v_i\}, B_{i-1}) \leq w(C_i) \qquad (6)$
Chú ý $v_n$ là một đỉnh tới hạn, và $B_{n}= V$. Do đó, $C_n = (A,V\setminus A)$. Bất đẳng thức $(6)$ sẽ tương đương với $c(\{t\},V\setminus \{t\}) \leq c(A,V\setminus A)$, đó là dpcm. Trong đoạn dưới đây, ta sẽ tập trung chứng minh $(5)$ bằng quy nạp.
Gọi $v_i$ là đỉnh tới hạn đầu tiên. Nếu $v_i \in A$, $X_{i-1}$ phải là tập rỗng do $v_i$ là điểm tới hạn đầu tiên. Do đó, $Y_{i-1} = B_{i-1}$ . Tương tự, Nếu $v_i \not\in A$, $Y_{i-1} = \emptyset$ và $X_{i-1} = B_{i-1}$. Như vậy, $C_i$ chính là các cạnh $(\{v_i\}, B_{i-1})$. Do đó, bất đẳng thức $(6)$ đúng.
Gọi $j$ < $i$ là hai số trong đó $v_j,v_i$ là hai đỉnh tới hạn liên tiếp nhau, i.e, với mọi $j $ < $k$ < $i$ thì $v_k$ không phải là đỉnh tới hạn. Ta xét trường hợp $v_i \in A$ (trường hợp $v_i \not\in A$ tương tự và coi như bài tập cho bạn đọc). Trong trường hợp này, $C_i = (X_{i-1}\cup \{v_i\}, Y_{i-1})$. Do $v_i \in A$, tất cả các đỉnh $v_{j}, v_{j+1}, \ldots, v_{i-1}$ đều thuộc $V\setminus A$. Do đó, ta suy ra:
$X_{i-1} = X_{j-1}, Y_{i-1} = Y_{j-1} \cup \{v_{j}, v_{j+1}, \ldots, v_{i-1}\}$.
Ta có (xem thêm Figure 3):
$\begin{array} {l} w(v_i, B_{i-1})& = w(v_i, X_{i-1}) + w(v_i, Y_{i-1}) \\ & = w(v_i, X_{j-1}) + w(v_i, Y_{i-1}) \\ &\leq w(v_i, X_{j-1}) + w(v_i, Y_{j-1}) + w(v_i, Y_{i-1}) \\ &\leq w(v_j, X_{j-1}) + w(v_j, Y_{j-1}) + w(v_i, Y_{i-1}) \\ &\leq w(X_{j-1}, Y_{j-1} \cup \{v_j\}) + w(v_i, Y_{i-1}) \\ &\leq w(X_{j-1}, Y_{i-1}) + w(v_i, Y_{i-1}) = w(C_i) \end{array} \qquad (7)$
Figure 3: Hình minh họa chứng minh bất đẳng thức $(7)$.
Ta sẽ từng bước kiểm tra $(7)$. Ba (bất) đẳng thức đầu tiên bạn đọc có thể dễ dàng kiểm tra. Bất đẳng thức thứ tư là do $v_{j}$ là đỉnh có độ kết dính lớn nhất tại bước $j$. Bất đẳng thức thứ năm là do quy nạp trên $(6)$. Chú ý ở đây $C_j = (X_{j-1}, Y_{j-1} \cup \{v_j\})$. Bất đẳng thức thứ 7 cũng dễ dàng kiểm tra. Từ đó ta suy ra dpcm.
Thực thi thuật toán Stoer-Wagner
Phần này có nhiều điểm tương đồng với thuật toán Prim. Mình sẽ ôn lại một chút về thực thi thuật toán Prim tại đây. Ta có hai cách thực thi thuật toán Prim, một cách trong thời gian $O(V^2)$ và cách khác trong thời gian $O((V+E)\log V)$ sử dụng Heap nhị phân. Nếu thay Heap nhị phân bằng Fibonacci Heap, ta có giảm thời gian thực thi thuật toán Prim xuống còn $O(E + V\log V)$.
Do đó, mỗi pha của thuật toán Stoer-Wagner, ta có thể thực thi trong thời gian $O(E + V\log V)$ sử dụng Fibonacci Heap. Do thuật toán Stoer-Wagner thực hiện trong tối đa $V$ pha, ta suy ra:
Sau đây, mình sẽ minh họa một cách thực thi với thời gian $O(V^3)$, mỗi pha thực hiện trong thời gian $O(V^2)$. Cách thực thi này hoàn toàn khớp với Theorem 2 khi đồ thị đầu vào là một đồ thị dầy, i.e, $E = O(V^2)$. Gọi $n,m$ lần lượt là số đỉnh, cạnh của đồ thị đầu vào. Ta sẽ dùng ma trận kề để biểu diễn đồ thị, kí hiệu là $W[1,\ldots, n][1,\ldots, n]$, trong đó $W[u,v] = W[v,u] = w(u,v)$
Do mỗi pha ta được phép sử dụng thời gian $O(V^2)$, ta sẽ được phép thực thị thi mỗi vòng lặp while trong thủ tục MinCutPhase($G(V,E)$) với thời gian $O(V)$. Như vậy, ta có thể đơn giản thực thi MaxStickiness$(V\setminus T, L)$ bằng cách duyệt qua toàn bộ mảng $L[1,\ldots, n]$ và tìm đỉnh $v$ không nằm trong $T$ có giá trị $L[v]$ lớn nhất. Để thực thi thủ tục Merge$(G, s,t)$, ta sẽ gộp $t$ vào $s$. Cụ thể, ta sẽ đánh dấu $t$ là đỉnh đã bị xóa (sử dụng một mảng boolean) và cập nhật lại trọng số của các cạnh kề với $s$:
$w(s,u) = w(s,u)+ w(t,u)$
$u \leftarrow -1$
$max\leftarrow -1$
for each $v \in X$
if $L[v]$ > $max$
$u \leftarrow v$
$max \leftarrow L[v]$
return $u$
for each $v \in V$
if $v \not\in \{s,t\}$
$W[s,v] \leftarrow W(s,v) + w(t,v)$
$W[v,s) \leftarrow W[s,v] $
$Del[t] \leftarrow $ True
Code C:
#define TRUE 1
#define FALSE 0
#define INFTY 1000000
#define MAX 1000
int W[MAX][MAX]; // the weight matrix
int Del[MAX];
int n; // the number of veritces
int m; // the number of edges
int StoerWagner(){
int V = n;
int C = INFTY;
memset(Del, FALSE, n*sizeof(int));
for(V = n; V > 1; V--){
int cutValue = minCutPhase(V);
C = (C < cutValue ? C: cutValue);
}
return C;
}
// V is the number of vertices of the current (merged) graph
int minCutPhase(int V){
int i = 0, j = 0;
int s[2];
if(V == 2) {
for( i = 0; i < n; i++){
if(Del[i] == FALSE){
s[j] = i; j++;
}
}
return W[s[0]][s[1]];
}
int L[n], T[n];
memset(L, 0, n*sizeof(int));
memset(T, FALSE, n*sizeof(int));
i = 1; // the number of vertices in the tree T
j = 0;
int v,u;
while( i <= V){
v = maxStickiness(T,L);
T[v] = TRUE;
for(u = 0; u < n; u++){
if(W[v][u] != 0 && Del[u] == FALSE && T[u] == FALSE){
L[u] = L[u] + W[u][v];
}
}
if( i >= V-1){
s[j] = v; j++;
}
i++;
}
merge(s[0], s[1]);
return L[s[1]];
}
void merge(int s, int t){
int v = 0;
for(v = 0; v < n; v++){
if(Del[v] == FALSE && v != s && v!= t){
W[s][v] = W[s][v] + W[v][t];
W[v][s] = W[s][v];
}
}
Del[t] = TRUE;
}
int maxStickiness(int *T, int *L){
int i = 0;
int v = 0;
int max = 0;
for(i = 0; i < n; i++){
if(Del[i] == FALSE && T[i] == FALSE && max < L[i]){
v = i;
max = L[i];
}
}
return v;
}
Code đầy đủ: Stoer-Wagner.
Tham khảo
[1] M. Stoer and F. Wagner. A simple min cut algorithm. European Symposium on Algorithms. Springer Berlin Heidelberg, 1994.
[2] H. Nagamochi and T. Ibaraki. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics 5.1 (1992): 54-66.
Recent Comments