最小割

在圖論中，去掉其中所有邊能使一張網絡流圖不再連通（即分成兩個子圖）的邊集稱為圖的割（英語：cut），一張圖上最小的割稱為最小割（英語：minimum cut或min-cut）。與最小割相關的問題稱最小割問題（英語：minimum cut problem或min-cut problem），其變體包括帶邊權、有向圖、包含源點與匯點（簡稱有源匯），以及將原網絡分為多於兩個子圖等問題。其中，帶邊權的最小割問題允許有負權邊，可通過對所有邊權取相反數簡單地轉化為最大流問題求解。

圖片上是一張圖及其兩個割：紅色點線標出了一個包含三條邊的割，綠色劃線則表示了這張圖的一個最小割（包含兩條邊）

無源匯的最小割問題

對於帶有邊權的無向圖，其最小割問題可以在多項式時間內通過Stoer-Wagner算法求解。在無邊權的特殊情況下，一種高效的隨機化算法Karger算法可用於求解最小割。在這種情況下，最小割等於圖的邊連通度。

對無源匯最小割問題加以推廣，可以得到最小k割問題，即將圖分為至少k個子圖的最小割問題。對於一個確定的k，這個問題可以在多項式時間內完成，雖然算法在k較大時並不理想。

有源匯的最小割問題

在網絡圖中，流產生的起點（入度為0）稱作源點（英語：source，用$s$表示），接受流的終點（出度為0）稱作匯點（英語：sink，用$t$表示）。

在帶有邊權的有向網絡流中，最小割被定義為切斷所有邊後能使源匯不連通且邊權和最小的邊集。根據最大流最小割定理，此時的最小割邊權和等於網絡上能從源點流到匯點的最大流量，或簡稱「最小割等於最大流」。

在帶有邊權的無向網絡流中，任意點對的最小割則被定義為切斷所有邊後能使這兩個點不連通且邊權和最小的邊集，且可用最小割樹求出。該數據結構以一棵帶邊權的樹表示了所有源-匯點對（或$s$-$t$對），可以以$(|V|-1)$次最大流計算求解。

將有源匯最小割問題加以推廣可得到k端點最小割問題（英語：k-terminal cut或multiterminal cut），該問題即使在$k=3$時也是NP困難的。

應用

• 圖的拆分是統稱，指將圖帶條件（如平衡割兩側子圖大小）拆成多個子圖的一系列最優化問題。
• 基於分塊的對象分類可以看作歸一化的最小割譜聚類算法應用於圖像分割的具體案例。
• 根據最大流最小割定理，雙節點的最小割等於最大流，故求解最小割時也會使用最大流算法求解。

計數

若一張圖帶有$n$個節點，則它上面最小割數有${\frac {n(n-1)}{2}}$的嚴格上限，因為有$n$個節點的簡單環上有着恰好${\binom {n}{2}}={\frac {n(n-1)}{2}}$個不同的最小割（每兩條邊組成的邊集恰好出現一次）。

參見

• 最大割問題
• 最大流最小割定理
• 點割集