隨機化最小割

Vibe Prompt

「實作 Karger's Contraction 演算法，找到圖形的最小割。跑 100 次取最佳結果。」

import random, copy

def karger_min_cut(graph):
    """
    graph: {node: [neighbors]}
    """
    while len(graph) > 2:
        # 隨機選一條邊
        u = random.choice(list(graph.keys()))
        v = random.choice(graph[u])
        
        # 合併 v 到 u
        graph[u].extend(graph[v])
        for w in graph[v]:
            graph[w] = [u if x == v else x for x in graph[w]]
        graph[u] = [x for x in graph[u] if x != u]
        del graph[v]
    
    # 剩餘兩節點之間的邊數 = 最小割
    nodes = list(graph.keys())
    return len([x for x in graph[nodes[0]] if x == nodes[1]])

def find_min_cut(graph, trials=100):
    best = float('inf')
    for i in range(trials):
        g = copy.deepcopy(graph)
        cut = karger_min_cut(g)
        if cut < best:
            best = cut
            print(f"第 {i+1} 次: 找到更小割 {best}")
    return best

# 測試
graph = {
    0: [1, 2, 3],
    1: [0, 2, 3],
    2: [0, 1, 3, 4],
    3: [0, 1, 2, 4],
    4: [2, 3, 5, 6],
    5: [4, 6],
    6: [4, 5],
}

min_cut = find_min_cut(graph, trials=50)
print(f"最小割: {min_cut}")

# 理論值：這個圖的最小割是 2（切開 {4,5,6}）

深入理解：Karger 演算法的成功機率

為什麼要重複執行？

Karger 演算法是隨機化演算法，單次執行找到最小割的機率不高。但重複執行 $t$ 次後，至少一次成功的機率大幅提升。

成功機率分析

對於 $n$ 個節點的圖：

單次成功機率 $P \geq \frac{2}{n(n-1)} = \Theta(1/n^2)$
執行 $t$ 次後失敗機率 $\leq (1 - \frac{2}{n(n-1)})^t$
執行 $t = n^2 \ln n$ 次後，失敗機率 $\leq 1/n$

import math

def success_probability(n, trials):
    """計算至少成功一次的機率"""
    p_single = 2 / (n * (n-1))
    p_fail_all = (1 - p_single) ** trials
    return 1 - p_fail_all

for n in [10, 50, 100, 500]:
    t = n * n * int(math.log(n))
    p = success_probability(n, t)
    print(f"n={n:3d}, trials={t:8d}, 成功機率={p:.4f}")

Karger-Stein 改良版

原始 Karger 跑 $O(n^2 \log n)$ 次，改良版（重複收縮到 $n/\sqrt{2}$ 再遞迴）只需 $O(n^2 \log^2 n)$ 時間。

關鍵要點

✅ Karger 演算法用隨機收縮找到最小割
✅ 單次成功機率低，但重複執行可大幅提升
✅ 跑 $O(n^2 \log n)$ 次後失敗機率 $\leq 1/n$
✅ Karger-Stein 改良版將時間降到 $O(n^2 \log^2 n)$
✅ 隨機化 Contraction 圖示：節點合併後邊數 = 最小割

基礎範例

常見錯誤

程式碼範例

最小割：為什麼隨機化會有效？

Karger's Contraction 演算法非常反直覺：隨機挑一條邊，把兩端點合併，重複直到剩下兩個點——這樣就能找到圖的最小割？

為什麼會 work？

關鍵在於：最小割的邊數通常遠小於總邊數。隨機選邊時，選到最小割的邊的機率很低。每一次 Contraction 把兩個端點合併，就消除了所有連接它們的邊，剩下的邊越來越少，但最小割的邊一直沒被選到的機率其實不低。

執行 $n^2 \ln n$ 次獨立實驗後，失敗率可以降到 $1/n$ 以下。

這告訴我們什麼？

有時候一個簡單的隨機化演算法 + 多次重複執行，就能達到跟複雜確定性演算法一樣好的效果。這在 system design 中很有啟發——當你面臨一個複雜問題時，先問自己：一個簡單的隨機化方案 + 多跑幾次，夠不夠好？

真實應用

社群網路分析：找出社團之間最脆弱的連結
電路分割：最小化晶片佈局中的跨區連線
影像分割：將圖片分割成不同的區域
雲端網路：找出網路的瓶頸頻寬

下一章預告：機率分析與集中不等式

這是最後一章理論課。我們會深入分析隨機化演算法的數學工具——Markov 不等式、Chebyshev 不等式、Chernoff Bound——理解為什麼隨機化演算法「幾乎總是 work」。