Cấu trúc dữ liệu và Giải thuật Bài 136: Thuật toán Karger-Stein (Randomized Global Min-Cut) - Thuật toán ngẫu nhiên hóa co cạnh tìm lát cắt cực tiểu toàn cục.

Trong lý thuyết đồ thị, bài toán Lát cắt cực tiểu giữa hai đỉnh nguồn - đích ($s-t$ Min-Cut) có thể giải quyết tất định bằng định lý Luồng cực đại - Lát cắt cực tiểu (Max-Flow Min-Cut) qua các thuật toán như Dinic ($O(V^2 E)$) hoặc Push-Relabel.

Tuy nhiên, trong bài toán Lát cắt cực tiểu toàn cục (Global Minimum Cut), đồ thị vô hướng không có cặp đỉnh $s, t$ được chỉ định trước: mục tiêu là phân chia tập đỉnh $V$ thành hai tập con không rỗng $(S, V \setminus S)$ sao cho tổng số cạnh (hoặc trọng số) nối giữa hai tập này là nhỏ nhất có thể.

Nếu giải bài toán này bằng cách cố định một đỉnh $s$ và chạy $V - 1$ lần thuật toán $s-t$ Min-Cut với mọi đỉnh $t$ còn lại, chi phí thời gian sẽ lên tới $O(V \cdot \text{MaxFlow}) \approx O(V^3 E)$. Năm 1993, David Karger đưa ra một cách tiếp cận ngẫu nhiên hóa (Randomized Algorithm) với phép co cạnh (Edge Contraction) đơn giản. Sau đó, vào năm 1996, David Karger và Clifford Stein nâng cấp thuật toán bằng kỹ thuật chia để trị đệ quy, khai sinh ra Thuật toán Karger-Stein — đưa thời gian chạy xuống mức $O(V^2 \log^3 V)$ với xác suất thành công cao tùy ý.

1. Định nghĩa bài toán Global Min-Cut

Cho một đa đồ thị vô hướng liên thông $G = (V, E)$ gồm $n = \vert{}V\vert{}$ đỉnh và $m = \vert{}E\vert{}$ cạnh.

Một lát cắt (Cut) $(S, V \setminus S)$ là một phép phân hoạch tập đỉnh $V$ thành hai tập con rời nhau, không rỗng:

$$S \subset V, \quad S \neq \emptyset, \quad S \neq V$$

Kích thước của lát cắt (ký hiệu $\vert{}\delta(S)\vert{}$) là số lượng các cạnh có một đầu mút thuộc $S$ và đầu mút còn lại thuộc $V \setminus S$:

$$\delta(S) = \{ (u, v) \in E \mid u \in S, v \in V \setminus S \}$$

Mục tiêu là tìm lát cắt có kích thước cực tiểu toàn cục:

$$C^* = \arg\min_{\emptyset \subset S \subset V} \vert{}\delta(S)\vert{}$$

           Tập S                 Tập V \ S
          +-----+                 +-----+
          | (1) |                 | (3) |
          |  |  | === Lát cắt === |  |  |
          | (2) |                 | (4) |
          +-----+                 +-----+
               2 cạnh nối giữa S và V \ S

2. Thuật toán co cạnh cơ bản của Karger (Karger's Contraction)

Phép toán hạt nhân của thuật toán là Co cạnh (Edge Contraction):

• Cho một cạnh $e = (u, v)$. Co cạnh $e$ đồng nghĩa với việc gộp hai đỉnh $u$ và $v$ thành một siêu đỉnh mới $w$.

• Tất cả các cạnh nối từ đỉnh khác vào $u$ hoặc $v$ bây giờ sẽ nối vào $w$ (duy trì đa cạnh - multi-edges).

• Mọi khuyên tự nối (self-loops) sinh ra giữa $u$ và $v$ bị xóa bỏ.

    Trước khi co cạnh (u, v):          Sau khi co cạnh (u, v) thành w:
          (a) --- (u)                        (a) ===== (w)
                   |                                    |
          (b) --- (v)                        (b) -------+

Thuật toán Karger cơ bản:

1. Lặp lại việc chọn ngẫu nhiên đều một cạnh $e \in E$ và co cạnh đó.

2. Dừng lại khi đồ thị chỉ còn lại đúng 2 siêu đỉnh.

3. Tập các cạnh còn lại giữa hai siêu đỉnh này chính là một lát cắt ứng viên.

Phân tích xác suất thành công của Karger cơ bản

Gọi $k = \vert{}C^*\vert{}$ là kích thước lát cắt cực tiểu toàn cục.

1. Bậc của mọi đỉnh trong đồ thị phải $\ge k$. Do đó:

   $$2\vert{}E\vert{} = \sum_{v \in V} \deg(v) \ge n \cdot k \implies \vert{}E\vert{} \ge \frac{nk}{2}$$

2. Xác suất chọn trúng một cạnh thuộc $C^*$ ở bước đầu tiên:

   $$P(\text{chọn } e \in C^*) = \frac{k}{\vert{}E\vert{}} \le \frac{k}{nk/2} = \frac{2}{n}$$

   Do đó, xác suất không làm hỏng lát cắt tối ưu ở bước này là $\ge 1 - \frac{2}{n} = \frac{n-2}{n}$.

3. Khi đồ thị còn $i$ đỉnh, xác suất không chọn trúng cạnh thuộc $C^*$ là $\ge \frac{i-2}{i}$.

4. Xác suất để lát cắt $C^*$ tồn tại nguyên vẹn qua toàn bộ quá trình co từ $n$ đỉnh xuống 2 đỉnh:

   $$P(\text{thành công}) \ge \prod_{i=3}^n \frac{i-2}{i} = \frac{1}{3} \times \frac{2}{4} \times \frac{3}{5} \times \dots \times \frac{n-2}{n} = \frac{2}{n(n-1)} = \frac{1}{\binom{n}{2}} = \Theta\left(\frac{1}{n^2}\right)$$

Vì xác suất thành công là $\approx \frac{2}{n^2}$, ta phải lặp lại thuật toán này $N = \Theta(n^2 \ln n)$ lần độc lập để đạt xác suất tìm ra lát cắt tối ưu $\ge 1 - \frac{1}{n}$. Mỗi lần co tốn $O(n^2)$, dẫn đến tổng thời gian là $O(n^4 \log n)$ — quá chậm đối với đồ thị lớn.

3. Thuật toán Karger-Stein: Đột phá bằng Chia để trị đệ quy

Karger và Stein nhận ra một đặc điểm xác suất:

• Ở những bước đầu (khi $n$ còn rất lớn), xác suất chọn phải cạnh của $C^*$ là cực nhỏ ($\approx \frac{2}{n}$).

• Xác suất này chỉ tăng cao nguy hiểm khi số đỉnh còn lại rất ít (ví dụ khi $n = 4$, xác suất hỏng là $2/4 = 50\%$).

Ý tưởng cốt lõi của Karger-Stein:

Thay vì co thẳng một mạch từ $n$ đỉnh xuống 2 đỉnh, ta co đồ thị từ $n$ đỉnh xuống ngưỡng $t = \lceil 1 + n / \sqrt{2} \rceil$ đỉnh. Tại ngưỡng này, xác suất lát cắt tối ưu còn sống sót là:

$$\prod_{i = \lceil n/\sqrt{2} \rceil + 1}^n \frac{i-2}{i} \approx \frac{(n/\sqrt{2})^2}{n^2} = \frac{1}{2}$$

Sau đó, ta rẽ thành 2 nhánh độc lập (Branching), mỗi nhánh tiếp tục đệ quy co tiếp đồ thị đã thu nhỏ.

                         G (n đỉnh)
                        /          \
            (Co xuống n / √2)   (Co xuống n / √2)
                 G1                     G2
               /    \                 /    \
            (Co tiếp) (Co tiếp)    (Co tiếp) (Co tiếp)

Cấu trúc đệ quy:

Plaintext

KargerStein(G):
    Nếu |V(G)| <= 6:
        Dùng Karger cơ bản (hoặc Brute Force) tìm Min-Cut trực tiếp.
    t = ceil(1 + |V(G)| / sqrt(2))
    G1 = CoNgauNhien(G, t)
    G2 = CoNgauNhien(G, t)
    c1 = KargerStein(G1)
    c2 = KargerStein(G2)
    Trả về min(c1, c2)

Phân tích độ phức tạp thời gian

Mỗi bước co từ $n$ đỉnh xuống $n / \sqrt{2}$ đỉnh bằng ma trận kề tốn $O(n^2)$.

Phương trình đệ quy thời gian:

$$T(n) = 2 \cdot T\left(\left\lceil \frac{n}{\sqrt{2}} \right\rceil\right) + O(n^2)$$

Theo định lý thợ (Master Theorem) trường hợp 1: Vì hệ số nhánh là $2$ và tỷ lệ giảm kích thước là $\sqrt{2}$, ta có $\log_{\sqrt{2}} 2 = 2$. Do đó:

$$T(n) = O(n^2 \log n)$$

Phân tích xác suất thành công

Gọi $P(n)$ là xác suất thuật toán Karger-Stein tìm được lát cắt cực tiểu trên đồ thị $n$ đỉnh. Hệ thức truy hồi xác suất:

$$P(n) \ge 1 - \left( 1 - \frac{1}{2} P\left(\frac{n}{\sqrt{2}}\right) \right)^2$$

Giải hệ thức truy hồi này cho ta:

$$P(n) = \Omega\left(\frac{1}{\log n}\right)$$

Xác suất thành công đã tăng từ $\Theta(1/n^2)$ lên $\Theta(1/\log n)$!

Để đạt xác suất thành công cao $1 - 1/n$, ta chỉ cần lặp lại thuật toán Karger-Stein $O(\log^2 n)$ lần độc lập. Tổng thời gian chạy là:

$$O(n^2 \log n) \times O(\log^2 n) = O(n^2 \log^3 n)$$

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

Chương trình dưới đây cài đặt hoàn chỉnh cấu trúc đa đồ thị, hàm co cạnh ngẫu nhiên có trọng số/đa cạnh, và thuật toán đệ quy Karger-Stein:

Go

package main

import (
	"fmt"
	"math"
	"math/rand"
	"time"
)

// Graph biểu diễn đa đồ thị bằng ma trận kề
type Graph struct {
	n     int     // Số lượng đỉnh ban đầu
	nodes []int   // Danh sách các đỉnh còn hoạt động
	adj   [][]int // adj[u][v] = số cạnh nối giữa u và v
}

func NewGraph(n int) *Graph {
	adj := make([][]int, n)
	nodes := make([]int, n)
	for i := 0; i < n; i++ {
		adj[i] = make([]int, n)
		nodes[i] = i
	}
	return &Graph{
		n:     n,
		nodes: nodes,
		adj:   adj,
	}
}

func (g *Graph) AddEdge(u, v int) {
	if u != v {
		g.adj[u][v]++
		g.adj[v][u]++
	}
}

// Sao chép sâu đồ thị
func (g *Graph) Clone() *Graph {
	cloneNodes := make([]int, len(g.nodes))
	copy(cloneNodes, g.nodes)

	cloneAdj := make([][]int, g.n)
	for i := 0; i < g.n; i++ {
		cloneAdj[i] = make([]int, g.n)
		copy(cloneAdj[i], g.adj[i])
	}

	return &Graph{
		n:     g.n,
		nodes: cloneNodes,
		adj:   cloneAdj,
	}
}

// Co đồ thị ngẫu nhiên cho đến khi số đỉnh còn lại đúng bằng targetNodes
func (g *Graph) ContractUntil(targetNodes int, rng *rand.Rand) {
	for len(g.nodes) > targetNodes {
		// 1. Đếm tổng số cạnh hiện có
		totalEdges := 0
		for i := 0; i < len(g.nodes); i++ {
			u := g.nodes[i]
			for j := i + 1; j < len(g.nodes); j++ {
				v := g.nodes[j]
				totalEdges += g.adj[u][v]
			}
		}

		if totalEdges == 0 {
			return // Đồ thị không liên thông, lát cắt = 0
		}

		// 2. Chọn ngẫu nhiên đều một cạnh
		r := rng.Intn(totalEdges)
		var u, v int
		accum := 0
		found := false

		for i := 0; i < len(g.nodes) && !found; i++ {
			currU := g.nodes[i]
			for j := i + 1; j < len(g.nodes); j++ {
				currV := g.nodes[j]
				accum += g.adj[currU][currV]
				if accum > r {
					u = currU
					v = currV
					found = true
					break
				}
			}
		}

		// 3. Co đỉnh v vào đỉnh u (gộp hàng/cột của v vào u)
		for _, w := range g.nodes {
			if w != u && w != v {
				g.adj[u][w] += g.adj[v][w]
				g.adj[w][u] += g.adj[w][v]
			}
			g.adj[v][w] = 0
			g.adj[w][v] = 0
		}
		g.adj[u][u] = 0 // Xóa self-loops
		g.adj[v][v] = 0

		// Xóa v khỏi danh sách nodes
		newNodes := make([]int, 0, len(g.nodes)-1)
		for _, node := range g.nodes {
			if node != v {
				newNodes = append(newNodes, node)
			}
		}
		g.nodes = newNodes
	}
}

// Thuật toán Karger cơ bản giải bài toán khi số đỉnh nhỏ (<= 6)
func kargerBase(g *Graph, rng *rand.Rand) int {
	work := g.Clone()
	work.ContractUntil(2, rng)
	u := work.nodes[0]
	v := work.nodes[1]
	return work.adj[u][v]
}

// Thuật toán đệ quy Karger-Stein
func kargerStein(g *Graph, rng *rand.Rand) int {
	k := len(g.nodes)
	if k <= 6 {
		return kargerBase(g, rng)
	}

	t := int(math.Ceil(1.0 + float64(k)/math.Sqrt2))

	// Nhánh 1
	g1 := g.Clone()
	g1.ContractUntil(t, rng)
	cut1 := kargerStein(g1, rng)

	// Nhánh 2
	g2 := g.Clone()
	g2.ContractUntil(t, rng)
	cut2 := kargerStein(g2, rng)

	if cut1 < cut2 {
		return cut1
	}
	return cut2
}

// Tìm Global Min-Cut bằng cách lặp Karger-Stein nhiều lần
func FindGlobalMinCut(g *Graph, iterations int) int {
	rng := rand.New(rand.NewSource(time.Now().UnixNano()))
	minCut := math.MaxInt32

	for i := 0; i < iterations; i++ {
		res := kargerStein(g, rng)
		if res < minCut {
			minCut = res
		}
	}
	return minCut
}

func main() {
	// Khởi tạo đồ thị gồm 8 đỉnh: hai cụm K4 nối với nhau bởi 2 cầu (Min-Cut kỳ vọng = 2)
	// Cụm 1: {0, 1, 2, 3} tạo thành đồ thị đầy đủ
	// Cụm 2: {4, 5, 6, 7} tạo thành đồ thị đầy đủ
	// Các cạnh cầu nối: (0, 4) và (1, 5)
	n := 8
	g := NewGraph(n)

	// Cụm 1 (K4)
	for i := 0; i < 4; i++ {
		for j := i + 1; j < 4; j++ {
			g.AddEdge(i, j)
		}
	}

	// Cụm 2 (K4)
	for i := 4; i < 8; i++ {
		for j := i + 1; j < 8; j++ {
			g.AddEdge(i, j)
		}
	}

	// Cạnh nối giữa hai cụm (Min-Cut = 2)
	g.AddEdge(0, 4)
	g.AddEdge(1, 5)

	fmt.Printf("Đồ thị gồm %d đỉnh chia thành 2 cụm K4 nối bởi 2 cạnh.\n", n)

	// Chạy Karger-Stein với số lần lặp nhỏ (khoảng 10 lần đã cho xác suất thành công cực cao)
	iterations := 15
	minCut := FindGlobalMinCut(g, iterations)

	fmt.Printf("Kết quả Global Min-Cut tìm được qua %d lần chạy Karger-Stein: %d cạnh\n",
		iterations, minCut)
}

5. Phân tích độ phức tạp & So sánh kiến trúc

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

• Phân cụm đồ thị & Khai phá dữ liệu (Graph Clustering / Community Detection): Global Min-Cut được sử dụng để phát hiện các phân ranh tự nhiên trong mạng xã hội hoặc mạng sinh học, phân tách các cộng đồng liên kết chặt chẽ ra khỏi nhau bằng cách cắt đứt số lượng ít nhất các mối liên kết yếu giữa các nhóm.

• Đánh giá Độ bền vững mạng lưới (Network Vulnerability Analysis): Tìm điểm yếu cốt tử nhất của một hệ thống hạ tầng (lưới điện, mạng cáp viễn thông) — xác định tập hợp cáp tối thiểu mà nếu bị đứt đồng thời sẽ chia cắt hệ thống thành hai nửa độc lập.

• Phân đoạn hình ảnh (Image Segmentation): Mô hình hóa các pixel ảnh thành một lưới đồ thị (Grid Graph), nơi trọng số cạnh biểu diễn độ tương đồng màu sắc. Lát cắt nhỏ nhất phân chia đối tượng trọng tâm (Foreground) ra khỏi phông nền (Background).