Cut - 演算法筆記

以下介紹幾個Minimum s-t Cut 的數學性質。

... Max-Flow Min-Cut Theorem ... 無法觸及的點集合（瓶頸之後），就是其中一個最小源匯割，而且源點側的點數最少。

Cut Cut 「割」有兩種定義方式： 一、「割」是點集合：圖上所有點分成第一群和第二群。

二、「割」是邊集合：第一群點連向第二群點的邊。

「割」還有另一種觀點： 一、「割」是點集合：從圖上挑出一群點。

二、「割」是邊集合：一群點連向其他點的邊。

點分成兩群，一種分法就是一個Cut。

所有點可以集中在同一群，此時另一群就是空的。

V個點的有向圖，一共有2ⱽ種Cut。

V個點的無向圖，第一群和第二群的順序沒有差別，一共有2ⱽ/2種Cut。

一個Cut的權重，是所有邊的權重總和。

MinimumCut 「最小割」。

一張圖權重最小的割，可能有許多個。

求最小割是NP-hard問題。

當圖上沒有負邊，才是P問題。

MaximumCut 最大割和小割很類似。

最大割問題當中，每一條邊的權重添上負號，就變成最小割問題。

反過來也是。

求最大割是NP-hard問題。

當圖上沒有正邊，才是P問題。

一群點收縮為一個點 同群的點收縮成單獨的點，Cut的權重依舊相同。

多重的邊變成單獨的邊 多重的邊合併成單獨的邊，權重加總，Cut的權重依舊相同。

s-tCut s-tCut 「源匯割」。

s點位在第一群、t點位在第二群。

s點、t點所屬的點集合，以下稱作s側、t側。

Minimums-tCut 「最小源匯割」。

指定兩個點（源點和匯點），這兩個點在不同側的最小割，可能有許多個。

數學性質：叛離 以下介紹幾個Minimums-tCut的數學性質。

針對無向圖、無負邊。

性質名稱是我隨興取的。

歡迎各位讀者提供建議。

s側或t側分離出一群點（s點與t點不移動），得到不等式： 一側分離出一群點到另一側（s點與t點不移動），權重變大，或者權重不變（遇到另一個最小st割）。

數學性質：基準 x點在s側，y點在t側，最小xy割的權重小於等於最小st割的權重。

最小xy割的背後有著最小st割撐腰，青出於藍更勝於藍。

數學性質：共側 圖上任取三點ijk，求出最小ij割、最小jk割、最小ki割。

權重較小的那兩個割，權重相等（甚至是同一個割）。

一、不失一般性，權重最小的那一個割，暫定是最小ij割。

二、要嘛k點在i側，要嘛k點在j側。

　甲、暫定k點在j側。

　　　由基準性質可知：最小kj割的權重小於等於最小ij割的權重。

　　　又因為最小ij割已經是權重最小的， 　　　所以，最小kj割的權重被迫等於最小ij割的權重。

　乙、暫定k點在j側。

　　　同理，最小ki割的權重被迫等於最小ij割的權重。

數學性質：Minimality 基準性質、共側性質，改寫成min函數。

但是性質變弱失真。

圖上任意三點ijk mincut(i,k)≥min(mincut(i,j),mincut(j,k)) 推廣至任意序列 mincut(a,z)≥min(mincut(a,b),mincut(b,c),...,mincut(y,z)) Minimums-tCut:Max-FlowMin-CutTheorem 用途 無向圖或有向圖，指定源點與匯點，求出其中一個最小源匯割。

限制：無負邊。

Max-FlowMin-CutTheorem 有向圖當中，根據「最大流最小割定理」，「有向圖的最大源匯流」同時形成了「有向圖的最小源匯割」。

無向圖當中，預先把一條無向邊換成兩條有向邊，「有向圖的最大源匯流」同時形成了「無向圖的最小源匯割」。

最大源匯流，部分管線滿溢，達到容量上限，形成瓶頸，其中包含了最小源匯割。

演算法 一個最大源匯流，通常可以找到多個最小源匯割。

由源點開始遍歷，只通過管線尚未滿溢的邊，得以觸及的點集合（瓶頸之前）、無法觸及的點集合（瓶頸之後），就是其中一個最小源匯割，而且源點側的點數最少。

由匯點開始反向遍歷，亦有類似結果。

typedefintGraph[9][9]; //adjacencymatrix GraphC,F,R; //容量、流量、剩餘容量 boolvisit[9]; voidDFS(inti) { visit[i]=true; for(intj=0;j<9;++j) if(!visit[j]&&F[i][j]0) //要確定有邊 cout<max) max=w[j],x=j; visit[x]=true; //加入x點到A集合 cout<