卡格最小割演算法（Karger's min-cut algorithm）
/ KAR-ger /
一個網路的全域最小割，是透過移除邊把它分成兩塊的最便宜方式——把一座城市切成兩半所需剪斷的最少纜線。要精確找到它聽起來該需要重型機械，然而卡格演算法只用一個出奇簡單的想法就找到它：反覆把兩個隨機選中的相連節點合併成一個，最後存活下來的邊就構成一個候選割。
精確地說：挑一條隨機邊並「收縮」它，把它的兩個端點融成單一超級節點，保留任何平行邊（但丟掉自環）；重複直到只剩兩個超級節點。仍連接那兩個最終超級節點的邊構成一個割，演算法輸出它。為何這可能是最小割？固定任一個有 k 條邊的最小割 C。演算法恰在它從不收縮 C 的某條邊時回傳 C。在 n - 2 次收縮的每一步，由於最小割有 k 條邊、每個節點度數至少為 k（否則存在更小的割），圖至少有 nk/2 條邊，因此這一步碰到 C 的 k 條邊之一的機率很小；把各步的存活機率相乘得到 Pr[C 存活] >= 2 / (n(n-1))，至少約 1/n^2。這雖小但不微不足道——所以把整件事跑 O(n^2 log n) 次並保留看到的最小割，那麼你每一次都錯過真正最小值的機率就變得可忽略。
卡格演算法之所以重要，是因為它是機率方法的實作瑰寶：一段話就寫完的隨機程序，解決了古典確定性方法要用沉重得多的網路流機械才能處理的問題，而且它能推廣（Karger-Stein）到接近 O(n^2) 的時間。它也教導放大的心態——每次成功機率只有 1/n^2 也沒關係，只要獨立重複很便宜。誠實的提醒：它是蒙地卡羅的，所以單次執行通常是錯的；保證只在足夠多次獨立重複之後才浮現，而且你該引用放大之後的成功機率，而非單次的。
在一個形如兩個三角形由單一邊相連的圖上，真正的最小割就是那一條橋邊。卡格收縮隨機邊；只要它從不挑橋來收縮，兩個三角形就塌縮成兩個超級節點，存活的橋被回傳——大小為 1 的正確割。若太早挑到橋，你會得到一個錯誤、較大的割，這正是你要重複的原因。
隨機邊收縮每次以約 1/n^2 的機率回傳最小割；靠重複來放大。
單次執行成功的機率只有約 1/n^2，所以一次幾乎總是錯的；正確性保證完全來自獨立重複。它是蒙地卡羅的，而且沒有快速方法去認證回傳的割確實最小，因此你無法廉價地把它轉成拉斯維加斯。