最小割
在圖論中,去掉其中所有邊能使一張網絡流圖不再連通(即分成兩個子圖)的邊集稱為圖的割(英語:cut),一張圖上最小的割稱為最小割(英語:minimum cut或min-cut)。與最小割相關的問題稱最小割問題(英語:minimum cut problem或min-cut problem),其變體包括帶邊權、有向圖、包含源點與匯點(簡稱有源匯),以及將原網絡分為多於兩個子圖等問題。其中,帶邊權的最小割問題允許有負權邊,可通過對所有邊權取相反數簡單地轉化為最大流問題求解。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c0/Min_cut_example.svg/220px-Min_cut_example.svg.png)
無源匯的最小割問題
編輯對於帶有邊權的無向圖,其最小割問題可以在多項式時間內通過Stoer-Wagner算法求解。在無邊權的特殊情況下,一種高效的隨機化算法Karger算法可用於求解最小割。在這種情況下,最小割等於圖的邊連通度。
對無源匯最小割問題加以推廣,可以得到最小k割問題,即將圖分為至少k個子圖的最小割問題。對於一個確定的k,這個問題可以在多項式時間內完成,雖然算法在k較大時並不理想。[2]
有源匯的最小割問題
編輯在網絡圖中,流產生的起點(入度為0)稱作源點(英語:source,用 表示),接受流的終點(出度為0)稱作匯點(英語:sink,用 表示)。
在帶有邊權的有向網絡流中,最小割被定義為切斷所有邊後能使源匯不連通且邊權和最小的邊集。根據最大流最小割定理,此時的最小割邊權和等於網絡上能從源點流到匯點的最大流量,或簡稱「最小割等於最大流」。
在帶有邊權的無向網絡流中,任意點對的最小割則被定義為切斷所有邊後能使這兩個點不連通且邊權和最小的邊集,且可用最小割樹求出。該數據結構以一棵帶邊權的樹表示了所有源-匯點對(或 - 對),可以以 次最大流計算求解。
將有源匯最小割問題加以推廣可得到k端點最小割問題(英語:k-terminal cut或multiterminal cut),該問題即使在 時也是NP困難的。[3]
應用
編輯計數
編輯若一張圖帶有 個節點,則它上面最小割數有 的嚴格上限,因為有 個節點的簡單環上有着恰好 個不同的最小割(每兩條邊組成的邊集恰好出現一次)。
參見
編輯參考文獻
編輯- ^ 4 Min-Cut Algorithms. (原始內容存檔於2016-08-05).
- ^ A Polynomial Algorithm for the k-cut Problem for Fixed k.
- ^ The Complexity of Multiterminal Cuts (PDF). [2020-11-24]. (原始內容存檔 (PDF)於2018-12-25).