最小割- 維基百科，自由的百科全書

與最小割相關的問題稱最小割問題（英語：minimum cut problem或min-cut problem），其變體包括帶邊權、有向圖、包含源點與匯點（簡稱有源匯），以及將原網路分為多於兩 ... 最小割 維基百科，自由的百科全書 跳至導覽 跳至搜尋 圖片上是一張圖及其兩個割：紅色點線標出了一個包含三條邊的割，綠色劃線則表示了這張圖的一個最小割（包含兩條邊）[1] 在圖論中，去掉其中所有邊能使一張網路流圖不再連通（即分成兩個子圖）的邊集稱為圖的割（英語：cut(graphtheory)）（英語：cut），一張圖上最小的割稱為最小割（英語：minimumcut或min-cut）。

與最小割相關的問題稱最小割問題（英語：minimumcutproblem或min-cutproblem），其變體包括帶邊權、有向圖、包含源點與匯點（簡稱有源匯），以及將原網路分為多於兩個子圖等問題。

其中，帶邊權的最小割問題允許有負權邊，可通過對所有邊權取相反數簡單地轉化為最大流問題求解。

目次 1無源匯的最小割問題 2有源匯的最小割問題 3應用 4計數 5參見 6參考文獻 無源匯的最小割問題[編輯] 對於帶有邊權的無向圖，其最小割問題可以在多項式時間內通過Stoer-Wagner演算法（英語：Stoer-Wagneralgorithm）求解。

在無邊權的特殊情況下，一種高效的隨機化演算法Karger演算法（英語：Karger'salgorithm）可用於求解最小割。

在這種情況下，最小割等於圖的邊連通度（英語：k-edge-connectedgraph）。

對無源匯最小割問題加以推廣，可以得到最小k割問題（英語：minimumk-cut），即將圖分為至少k個子圖的最小割問題。

對於一個確定的k，這個問題可以在多項式時間內完成，雖然演算法在k較大時並不理想。

[2] 有源匯的最小割問題[編輯] 在網路圖中，流產生的起點（入度為0）稱作源點（英語：source，用 s {\displaystyles} 表示），接受流的終點（出度為0）稱作匯點（英語：sink，用 t {\displaystylet} 表示）。

在帶有邊權的有向網路流中，最小割被定義為切斷所有邊後能使源匯不連通且邊權和最小的邊集。

根據最大流最小割定理，此時的最小割邊權和等於網路上能從源點流到匯點的最大流量，或簡稱「最小割等於最大流」。

在帶有邊權的無向網路流中，任意點對的最小割則被定義為切斷所有邊後能使這兩個點不連通且邊權和最小的邊集，且可用最小割樹（英語：Gomory–Hutree）求出。

該資料結構以一棵帶邊權的樹表示了所有源-匯點對（或 s {\displaystyles} - t {\displaystylet} 對），可以以 ( | V | − 1 ) {\displaystyle(|V|-1)} 次最大流計算求解。

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

[3] 應用[編輯] 圖的拆分（英語：graphpartition）是統稱，指將圖帶條件（如平衡割（英語：cut(graphtheory)）兩側子圖大小）拆成多個子圖的一系列最佳化問題。

基於分塊的物件分類（英語：Segmentation-basedobject）可以看作歸一化的最小割譜聚類演算法（英語：spectralclustering）應用於圖像分割的具體案例。

根據最大流最小割定理，雙節點的最小割等於最大流，故求解最小割時也會使用最大流演算法求解。

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

參見[編輯] 最大割（英語：Maximumcut） 點割集（英語：Vertexseparator） 參考文獻[編輯] ^4Min-CutAlgorithms.（原始內容存檔於2016-08-05）.  ^APolynomialAlgorithmforthek-cutProblemforFixedk.  ^TheComplexityofMultiterminalCuts(PDF).[2020-11-24].（原始內容存檔(PDF)於2018-12-25）.  閱論編演算法排序比較排序 泡沫排序 選擇排序 插入排序 希爾排序 快速排序 合併排序 堆積排序 雞尾酒排序 梳排序 侏儒排序 圖書館排序 內省排序 奇偶排序 線性時間排序 鴿巢排序 基數排序 計數排序 桶排序 並列排序 排序網路（英語：Sortingnetwork） Batcher合併網路 不實用的 Bogo排序 臭皮匠排序 圖 拓撲排序 搜尋列表 線性搜尋 二分搜尋 插值搜尋 樹・圖 廣度優先搜尋 最良優先搜尋（英語：Best-firstsearch） 均一開銷搜尋 A* 深度優先搜尋 迭代深化深度優先搜尋 深度限制搜尋（日語：深さ制限探索） 雙向搜尋 分枝限定法（英語：Branchandbound） 字串 KMP演算法 博耶-穆爾字串搜尋演算法 AC自動機演算法 拉賓-卡普演算法 bitap演算法 最短路問題 戴克斯特拉演算法 貝爾曼-福特演算法 A*搜尋演算法 Floyd-Warshall演算法 最小生成樹 普林姆演算法 克魯斯克爾演算法 最大流最小割 福特-富爾克森演算法 埃德蒙茲-卡普演算法 迪尼茨演算法 線性規劃 單純形法 卡馬卡爾演算法（英語：Karmarkar'salgorithm） 順序統計量 選擇演算法 中位數的中位數（英語：Medianofmedians） 種類 近似演算法 隨機化演算法 其他 分治法 動態規劃 貪婪演算法 Category:演算法 取自「https://zh.wikipedia.org/w/index.php?title=最小割&oldid=69280883」 分類：​網絡流隱藏分類：​含有英語的條目 導覽選單 個人工具 沒有登入討論貢獻建立帳號登入 命名空間 條目討論 臺灣正體 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 查看 閱讀編輯檢視歷史 更多 搜尋 導航 首頁分類索引特色內容新聞動態近期變更隨機條目資助維基百科 說明 說明維基社群方針與指引互助客棧知識問答字詞轉換IRC即時聊天聯絡我們關於維基百科 工具 連結至此的頁面相關變更上傳檔案特殊頁面靜態連結頁面資訊引用此頁面維基數據項目 列印/匯出 下載為PDF可列印版 其他語言 العربيةEnglishفارسیFrançaisРусскийไทย 編輯連結