跳至內容

最小割

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
圖片上是一張圖及其兩個割:紅色點線標出了一個包含三條邊的割,綠色劃線則表示了這張圖的一個最小割(包含兩條邊)[1]

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

無源匯的最小割問題

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

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

有源匯的最小割問題

在網絡圖中,流產生的起點(入度為0)稱作源點(英語:source,用表示),接受流的終點(出度為0)稱作匯點(英語:sink,用表示)。

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

在帶有邊權的無向網絡流中,任意點對的最小割則被定義為切斷所有邊後能使這兩個點不連通且邊權和最小的邊集,且可用最小割樹英語Gomory–Hu tree求出。該數據結構以一棵帶邊權的樹表示了所有源-匯點對(或-對),可以以最大流計算求解。

將有源匯最小割問題加以推廣可得到k端點最小割問題(英語:k-terminal cutmultiterminal cut),該問題即使在時也是NP困難的。[3]

應用

計數

若一張圖帶有個節點,則它上面最小割數有的嚴格上限,因為有個節點的簡單環上有着恰好個不同的最小割(每兩條邊組成的邊集恰好出現一次)。

參見

參考文獻

  1. ^ 4 Min-Cut Algorithms. (原始內容存檔於2016-08-05). 
  2. ^ A Polynomial Algorithm for the k-cut Problem for Fixed k. 
  3. ^ The Complexity of Multiterminal Cuts (PDF). [2020-11-24]. (原始內容存檔 (PDF)於2018-12-25).