Cấu trúc dữ liệu và Giải thuật Bài 137: Thuật toán Stoer-Wagner (Deterministic Global Min-Cut) - Thuật toán tất định tìm lát cắt cực tiểu toàn cục không cần mạng luồng.

Ở Bài 136, chúng ta đã tiếp cận bài toán Lát cắt cực tiểu toàn cục (Global Min-Cut) thông qua góc nhìn xác suất của thuật toán Karger-Stein. Dù đạt độ phức tạp $O(V^2 \log^3 V)$ , Karger-Stein vẫn là một thuật toán ngẫu nhiên hóa (Monte Carlo) — luôn tồn tại một xác suất nhỏ đưa ra kết quả sai lệch và đòi hỏi cơ chế sinh số ngẫu nhiên chất lượng cao.

Trước khi thuật toán của Mechthild Stoer và Frank Wagner ra đời vào năm 1997, phương pháp tất định (deterministic) duy nhất để tìm Global Min-Cut là cố định một đỉnh $s$ và chạy thuật toán Luồng cực đại ( $s-t$ Max-Flow) $V - 1$ lần tới mọi đỉnh $t$ còn lại, tiêu tốn $O(V^4)$ hoặc $O(V^2 E)$ với overhead đồ thị thặng dư rất lớn.

Thuật toán Stoer-Wagner giải quyết bài toán hoàn toàn tất định, không cần mạng luồng (Flow-free), với độ phức tạp $O(V \cdot E + V^2 \log V)$ khi dùng Fibonacci Heap, hoặc $O(V^3)$ trên ma trận kề với hằng số thực thi tối ưu.

1. Trực giác Thuật toán và Tư duy Co cụm (Contraction)

Cho đồ thị vô hướng $G = (V, E)$ với các trọng số cạnh không âm $w(u, v) \ge 0$ .

Giả sử ta chọn ra hai đỉnh bất kỳ $s, t \in V$ . Lát cắt cực tiểu toàn cục $C^*$ của $G$ chỉ có thể rơi vào đúng một trong hai trường hợp loại trừ lẫn nhau:

Trường hợp 1: $C^*$ phân tách $s$ và $t$ vào hai tập khác nhau ( $s \in S, t \in V \setminus S$ ). Khi đó, $C^*$ chính là một lát cắt $s-t$ cực tiểu trong $G$ .
Trường hợp 2: $C^*$ không phân tách $s$ và $t$ (cả $s$ và $t$ cùng thuộc $S$ , hoặc cùng thuộc $V \setminus S$ ). Khi đó, việc gộp (co cụm - contract) hai đỉnh $s$ và $t$ thành một đỉnh duy nhất sẽ không làm thay đổi giá trị của lát cắt cực tiểu toàn cục.

Chiến lược của Stoer-Wagner

Thuật toán chia quá trình tìm kiếm thành $n - 1$ pha (Phases):

Ở mỗi pha, thuật toán tìm ra một cặp đỉnh $s, t$ cụ thể sao cho ta có thể tính toán chính xác lát cắt $s-t$ cực tiểu trong thời gian ngắn mà không cần dùng thuật toán Max-Flow.
Ghi nhận lát cắt $s-t$ này như một ứng viên cho Global Min-Cut.
Co hai đỉnh $s$ và $t$ lại với nhau để giảm số đỉnh của đồ thị đi 1.
Lặp lại quy trình trên đồ thị thu nhỏ cho đến khi đồ thị chỉ còn lại đúng 1 đỉnh.
Giá trị nhỏ nhất trong số $n - 1$ ứng viên lát cắt $s-t$ được ghi nhận chính là Global Min-Cut toàn cục.

2. Tìm kiếm kề cực đại (Maximum Adjacency Search - MAS)

Điểm cốt lõi của Stoer-Wagner là: Làm thế nào để tìm ra một cặp $s, t$ và lát cắt $s-t$ cực tiểu tương ứng mà không dùng luồng? Câu trả lời nằm ở thuật toán Maximum Adjacency Search (MAS).

Trong mỗi pha:

Bắt đầu với một tập đỉnh $A$ rỗng và chọn một đỉnh tùy ý đưa vào $A$ .
Định nghĩa độ kết nối giữa một đỉnh $v \notin A$ với tập $A$ là tổng trọng số các cạnh nối từ $v$ vào các đỉnh đã thuộc $A$ :

$w(A, v) = \sum_{u \in A} w(u, v)$
Lặp lại việc tìm đỉnh $v \notin A$ có $w(A, v)$ lớn nhất và nạp $v$ vào $A$ (tương tự như thuật toán Prim nhưng chọn đỉnh có liên kết tích lũy vào $A$ mạnh nhất).
Thứ tự các đỉnh được nạp vào $A$ tạo thành một dãy: $v_1, v_2, \dots, v_{n-1}, v_n$ .
Gọi hai đỉnh cuối cùng được thêm vào dãy là:

$s = v_{n-1}, \quad t = v_n$

   Tập A đang mở rộng:
   [v1] ---> nạp v2 ---> nạp v3 ---> ... ---> nạp s (v_{n-1}) ---> nạp t (v_n)
                                              \______________________________/
                                                Hai đỉnh cuối cùng của MAS

3. Định lý Then chốt của Stoer-Wagner

Định lý Stoer-Wagner: Trong dãy đỉnh sinh ra bởi thuật toán Maximum Adjacency Search, lát cắt phân tách đỉnh cuối cùng $t = v_n$ với phần còn lại của đồ thị $V \setminus \{t\}$ chính là một lát cắt $s-t$ cực tiểu của đồ thị hiện tại:

$\text{MinCut}(s, t) = w(\{t\}, V \setminus \{t\}) = \sum_{u \in V \setminus \{t\}} w(u, t)$

Phác thảo chứng minh (Proof by Active Vertices)

Xét một lát cắt $C = (S, V \setminus S)$ bất kỳ phân tách $s$ và $t$ (giả sử $s \in S, t \notin S$ ).

Ta gọi một đỉnh $v_i$ là đỉnh kích hoạt (active) nếu $v_i$ và đỉnh đi liền trước nó trong dãy MAS ( $v_{i-1}$ ) nằm ở hai phía khác nhau của lát cắt $C$ .
Bằng quy nạp toán học theo thứ tự xuất hiện của các đỉnh kích hoạt trong dãy MAS, ta chứng minh được rằng trọng số của lát cắt $C$ luôn lớn hơn hoặc bằng trọng số của các cạnh nối vào các đỉnh kích hoạt tại thời điểm chúng được thăm.
Vì $t$ là đỉnh cuối cùng và nằm khác phía với $s$ , $t$ chắc chắn là một đỉnh kích hoạt. Khi giải phóng điều kiện biên tại $t$ , ta thu được:

$w(C) \ge w(\{t\}, V \setminus \{t\})$
Bất đẳng thức này đúng với mọi lát cắt $C$ phân tách $s$ và $t$ . Do đó, lát cắt tách riêng đỉnh $t$ đạt giá trị nhỏ nhất trong tất cả các lát cắt $s-t$ .

4. Hiện thực hóa Thuật toán Stoer-Wagner bằng Golang

Đoạn mã Golang dưới đây cài đặt hoàn chỉnh thuật toán Stoer-Wagner sử dụng ma trận kề:

package main

import (
	"fmt"
	"math"
)

const INF = math.MaxInt64 / 4

type StoerWagner struct {
	n       int
	weights [][]int64 // Ma trận trọng số cạnh
	active  []bool    // active[i] = true nếu đỉnh i chưa bị co cụm
}

func NewStoerWagner(n int) *StoerWagner {
	weights := make([][]int64, n)
	for i := 0; i < n; i++ {
		weights[i] = make([]int64, n)
	}
	active := make([]bool, n)
	for i := 0; i < n; i++ {
		active[i] = true
	}
	return &StoerWagner{
		n:       n,
		weights: weights,
		active:  active,
	}
}

func (sw *StoerWagner) AddEdge(u, v int, w int64) {
	if u != v {
		sw.weights[u][v] += w
		sw.weights[v][u] += w
	}
}

// Thực hiện một pha Maximum Adjacency Search (MAS)
// Trả về: (s, t, cutOfThePhase)
func (sw *StoerWagner) minCutPhase(numActive int) (int, int, int64) {
	dist := make([]int64, sw.n)
	inA := make([]bool, sw.n)

	prev := -1
	curr := -1

	// Duyệt qua tất cả các đỉnh còn hoạt động
	for step := 0; step < numActive; step++ {
		maxWeight := int64(-1)
		nextVertex := -1

		// Tìm đỉnh chưa thuộc A có tổng liên kết vào A lớn nhất
		for i := 0; i < sw.n; i++ {
			if sw.active[i] && !inA[i] {
				if dist[i] > maxWeight {
					maxWeight = dist[i]
					nextVertex = i
				}
			}
		}

		if nextVertex == -1 {
			// Đồ thị không liên thông
			for i := 0; i < sw.n; i++ {
				if sw.active[i] && !inA[i] {
					nextVertex = i
					break
				}
			}
		}

		// Nạp nextVertex vào tập A
		inA[nextVertex] = true
		prev = curr
		curr = nextVertex

		// Cập nhật dist cho các đỉnh còn lại
		for i := 0; i < sw.n; i++ {
			if sw.active[i] && !inA[i] {
				dist[i] += sw.weights[curr][i]
			}
		}
	}

	s := prev
	t := curr
	cutOfPhase := dist[t]

	return s, t, cutOfPhase
}

// Solve tính toán Global Min-Cut toàn cục
func (sw *StoerWagner) Solve() int64 {
	var minCut int64 = INF

	// Thuật toán lặp qua n - 1 pha co cụm
	for numActive := sw.n; numActive > 1; numActive-- {
		s, t, cutOfPhase := sw.minCutPhase(numActive)

		if cutOfPhase < minCut {
			minCut = cutOfPhase
		}

		// Co cụm t vào s:
		// 1. Cộng dồn trọng số các cạnh kề với t vào s
		for i := 0; i < sw.n; i++ {
			if sw.active[i] && i != s && i != t {
				sw.weights[s][i] += sw.weights[t][i]
				sw.weights[i][s] += sw.weights[i][t]
			}
		}

		// 2. Vô hiệu hóa đỉnh t
		sw.active[t] = false
	}

	return minCut
}

func main() {
	// Khởi tạo đồ thị gồm 8 đỉnh có trọng số
	// Cấu trúc 2 cụm liên kết mạnh nối bởi các cạnh cầu yếu (Global Min-Cut kỳ vọng = 4)
	n := 8
	sw := NewStoerWagner(n)

	// Cụm 1: {0, 1, 2, 3}
	sw.AddEdge(0, 1, 10)
	sw.AddEdge(0, 2, 10)
	sw.AddEdge(1, 2, 10)
	sw.AddEdge(1, 3, 10)
	sw.AddEdge(2, 3, 10)

	// Cụm 2: {4, 5, 6, 7}
	sw.AddEdge(4, 5, 10)
	sw.AddEdge(4, 6, 10)
	sw.AddEdge(5, 6, 10)
	sw.AddEdge(5, 7, 10)
	sw.AddEdge(6, 7, 10)

	// Các cạnh cầu nối giữa Cụm 1 và Cụm 2 (Tổng trọng số = 1 + 3 = 4)
	sw.AddEdge(3, 4, 1)
	sw.AddEdge(2, 5, 3)

	minCut := sw.Solve()

	fmt.Printf("Đồ thị gồm %d đỉnh có trọng số.\n", n)
	fmt.Printf("Trọng số Lát cắt Cực tiểu Toàn cục (Global Min-Cut): %d\n", minCut)
}

5. Phân tích độ phức tạp thuật toán

Cấu trúc triển khai	Chi phí một pha (MAS)	Số lượng pha	Tổng độ phức tạp thời gian	Bộ nhớ phụ trợ
Ma trận kề (Dense Graphs)	$O(V^2)$	$V - 1$	$O(V^3)$	$O(V^2)$
Fibonacci Heap (Sparse Graphs)	$O(E + V \log V)$	$V - 1$	$O(V \cdot E + V^2 \log V)$	$O(V + E)$
Binary Heap (Thư viện chuẩn)	$O(E \log V)$	$V - 1$	$O(V \cdot E \log V)$	$O(V + E)$

6. So sánh Stoer-Wagner và Karger-Stein

Tiêu chí	Stoer-Wagner (1997)	Karger-Stein (1996)
Bản chất thuật toán	Tất định (Deterministic)	Ngẫu nhiên hóa (Monte Carlo)
Độ chính xác	Tuyệt đối 100%	Xác suất cao ( $1 - \epsilon$ )
Hỗ trợ trọng số cạnh	Tự nhiên (hỗ trợ trọng số thực bất kỳ $\ge 0$ )	Phức tạp hơn (phải chọn cạnh theo phân phối xác suất tỉ lệ trọng số)
Bộ nhớ phụ trợ	Nhỏ ( $O(V^2)$ hoặc $O(V + E)$ tại chỗ)	Lớn hơn (lưu cây đệ quy các đồ thị con)
Khả năng song song hóa	Khó (các pha phụ thuộc tuần tự vào nhau)	Cực kỳ dễ (các nhánh đệ quy chạy song song)
Truy vết lát cắt	Dễ dàng (lưu lại danh sách đỉnh gom cụm)	Dễ dàng (lưu lại các siêu đỉnh cuối cùng)

7. Ứng dụng thực tế

Tối ưu hóa Phân vùng Mạch vi điện tử (VLSI Circuit Partitioning): Chia mạch tích hợp gồm hàng triệu bóng bán dẫn thành các khối vật lý độc lập sao cho số lượng đường dây tín hiệu liên kết xuyên khối là ít nhất, giảm điện dung ký sinh và độ trễ truyền dẫn.
Cân bằng tải cụm máy chủ phân tán (Distributed Graph Partitioning): Phân chia đồ thị dữ liệu người dùng lên các máy chủ lưu trữ khác nhau sao cho các giao dịch phân tán xuyên máy chủ (cross-node transactions) đạt mức tối thiểu.
Đo lường Độ kết nối cạnh (Edge-Connectivity Testing): Kiểm tra xem đồ thị có phải là $k$ -edge-connected hay không bằng cách so sánh giá trị Global Min-Cut với ngưỡng $k$ .

cấu trúc dữ liệu