Cut

Cut

「割」有兩種定義方式:

一、「割」是點集合:圖上所有點分成第一群和第二群。

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

「割」還有另一種觀點:

一、「割」是點集合:從圖上挑出一群點。

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

點分成兩群,一種分法就是一個Cut。所有點可以集中在同一群,此時另一群就是空的。

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

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

Minimum Cut

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

求最小割是NP-hard問題。當圖上沒有負邊,才是P問題。

Maximum Cut

最大割和小割很類似。最大割問題當中,每一條邊的權重添上負號,就變成最小割問題。反過來也是。

求最大割是NP-hard問題。當圖上沒有正邊,才是P問題。

一群點收縮為一個點

同群的點收縮成單獨的點,Cut的權重依舊相同。

多重的邊變成單獨的邊

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

s-t Cut

s-t Cut

「源匯割」。s點位在第一群、t點位在第二群。

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

Minimum s-t Cut

「最小源匯割」。指定兩個點(源點和匯點),這兩個點在不同側的最小割,可能有許多個。

數學性質:叛離

以下介紹幾個Minimum s-t Cut的數學性質。針對無向圖、無負邊。性質名稱是我隨興取的。歡迎各位讀者提供建議。

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))

Minimum s-t Cut: Max-Flow Min-Cut Theorem

用途

無向圖或有向圖,指定源點與匯點,求出其中一個最小源匯割。

限制:無負邊。

Max-Flow Min-Cut Theorem

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

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

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

演算法

一個最大源匯流,通常可以找到多個最小源匯割。

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

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

UVa 10480 ICPC 5099

Minimum Cut

圖上每種點對作為源點和匯點,分別尋找源匯最小割。其中最小者就是最小割。

Minimum s-t Cut: Hao–Orlin Algorithm

用途

無向圖或有向圖,指定源點,窮舉匯點,求出權重最小的最小源匯割。通常有許多個,找到其中一個。

限制:無負邊。

想法:窮舉法

固定源點,窮舉匯點,分別計算V-1次最小源匯割,其中最小者就是正解。

想法:遞歸法

圖上隨意取一條邊,要嘛在割上,要嘛不在割上。

圖上隨意取兩個點,要嘛在割異側,要嘛在割同側。

考慮正解。圖上隨意取兩個點,s點與t點。

一、s和t在正解的異側:最小st割就是正解。

二、s和t在正解的同側:收縮st兩點,不影響正解。

收縮之後,圖上減少了一點,得以實施遞歸法!

匯點收縮至源點,任選一個新匯點,總共計算V-1次最小源匯割,其中最小者就是正解。

圖上逐次減少了一點,計算速度變快了一點。

想法:多個源點

「匯點收縮至源點」重新解讀為「新增源點」。

舊匯點變成新源點,任選一個新匯點,總共計算V-1次最小多源單匯割,其中最小者就是正解。

演算法

Push–Relabel Algorithm輕輕鬆鬆將舊匯點變成新源點。

一、指定源點。
  源點以外隨意取一個點,作為匯點。
二、實施Push–Relabel Algorithm,尋找最大多源單匯流。
 甲、沿用上次計算結果。
 乙、舊匯點變成新源點。
   新源點實施Preflow:高度固定為V-1、積水量無限大、強制送水到所有鄰點。
 丙、任選一個最低點變成新匯點。
   高度固定為當前高度。
 丁、繼續實施Push和Relabel,找到新的最大多源單匯流。
 戊、由源點開始遍歷,找到新的最小多源單匯割。
三、重複上述步驟V-1次,得到V-1個最小多源單匯割,其中最小者就是正解。

時間複雜度

因為圖上各點高度上限仍然相同,所以時間複雜度仍然相同。

時間複雜度等同一次Push–Relabel Algorithm的時間O(V²E)。

改用FIFO Push–Relabel Algorithm降為O(V³)。改用Highest-Label Push–Relabel Algorithm降為O(V²sqrtE)。

加速技巧:Blocking Flow

圖上各點不斷抬高。任何一種高度,一旦出現又消失,表示更高點到更低點不連通,形成阻塞流。更高點作為源點側,更低點作為匯點側,形成源匯割。

每當任何一種高度出現又消失,更高點納入源點側,其餘點作為匯點側,最後得到最小源匯割。

一旦找到最大源匯流,同時得到最小源匯割。不必另行遍歷。

Minimum Cut

圖上各點分別作為源點,分別實施Hao–Orlin Algorithm。其中最小者就是最小割。

Minimum s-t Cut: Nagamochi–Ibaraki Algorithm(Maximum Adjacency Search)

用途

無向圖,無法指定源點與匯點,求出任意一個最小源匯割。

限制:無負邊。

Maximum Adjacency Search

Maximum Cardinality Search」引入權重。每回合找到一個點,連往已拜訪點的權重總和最多。若不只一點,則任選一點。

時間複雜度O(V²)。運用Binary Heap壓至O(V+ElogV)。運用Fibonacci Heap壓至O(E+VlogV)。

當圖上無負邊,
Maximum Adjacency Search最後兩點形成Minimum s-t Cut

令Maximum Adjacency Search的遍歷順序是v1…vn,最後兩點是vn-1與vn

當圖上無負邊,{v1…vn-1}與{vn}是一個最小vn-1vn割。

一、欲證cut(v1⋯n-1, vn)是最小vn-1vn割。
二、觀察vn-2與vn-1與vn這三點,根據共側性質,
  最小vn-2vn-1割、最小vn-2vn割、最小vn-1vn割,
  其中權重比較小的那兩個割,權重相等。
三、嘗試找到最小vn-2vn-1割、最小vn-2vn割,
  並且證明cut(v1⋯n-1, vn)的權重同時小於等於這兩個割,
  那麼根據共側性質,cut(v1⋯n-1, vn)就一定是最小vn-1vn割。
四、以下用數學歸納法證明,但是以反方向講解。

basis step:
圖上只有兩點一邊時,顯然是一個最小st割。

inductive step:
一、從圖上移除邊vn-1vn,
  不影響vn-1vn割的位置,刪除也無妨。
二、最小vn-2vn-1割的部分:
 甲、從圖上移除vn(以及連著的邊)。
   重新實施Maximum Adjacency Search,順序仍舊相同,vn-2與vn-1成為最後兩點。
   遞迴求解,證得cut(v1⋯n-2, vn-1)是一個最小vn-2vn-1割。
 乙、因為vn-1與vn兩點之間沒有邊,
   把vn(以及連著的邊)加回到cut(v1⋯n-2, vn-1)的vn-2側,
   得到cut(v1⋯n-2 + vn, vn-1)是原圖的一個最小vn-2vn-1割。
 丙、由Maximum Adjacency Search倒數第二步的選擇,可知
   cut(v1⋯n-2, vn-1) ≥ cut(v1⋯n-2, vn)
   又因為vn-1與vn兩點之間沒有邊,
   cut(v1⋯n-2 + vn, vn-1) ≥ cut(v1⋯n-2 + vn-1, vn)
   顯然地,
   cut(v1⋯n-2 + vn, vn-1) ≥ cut(v1⋯n-1, vn)
   也就是說,cut(v1⋯n-1, vn)的權重小於等於最小vn-2vn-1割。
三、最小vn-2vn割的部分:
 甲、從圖上移除vn-1(以及連著的邊)。
   重新實施Maximum Adjacency Search,順序仍舊相同,vn-2與vn成為最後兩點。
   遞迴求解,證得cut(v1⋯n-2, vn)是一個最小vn-2vn割。
 乙、因為vn-1與vn兩點之間沒有邊,
   把vn-1(以及連著的邊)加回到cut(v1⋯n-2, vn)的vn-2側,
   得到cut(v1⋯n-2 + vn-1, vn)是原圖的一個最小vn-2vn割。
 丙、顯然地,
   cut(v1⋯n-2 + vn-1, vn) = cut(v1⋯n-1, vn)
   也就是說,cut(v1⋯n-1, vn)的權重小於等於最小vn-2vn割。
四、由二丙、三丙,得證。

Minimum Cut

收縮源點與匯點,重做Maximum Adjacency Search,總共計算V-1次源匯最小割,其中最小者就是最小割。

這個演算法後來被Stoer和Wagner重新提起。也許是因為他們倆的論文內容更加簡單明瞭,於是演算法名稱就變成他們倆了。

Minimum Cut: Stoer–Wagner Algorithm

用途

無向圖,求出其中一個最小割。

限制:無負邊。

想法

圖上隨意取一條邊,要嘛在割上,要嘛不在割上。

圖上隨意取兩個點,要嘛在割異側,要嘛在割同側。

藉由此觀察,得以實施Divide-and-Conquer Method。任取st兩點,分別計算這兩種情況下的最小割:

一、假設st在最小割異側:最小割根本就是最小st割。

二、假設st在最小割同側:原圖收縮st兩點,不影響最小割位置。圖上少了一點,就能遞迴求解,得到最小割。

因為沒有限制st是哪兩點,所以可以用Maximum Adjacency Search快速求得st異側的那個最小st割。

注意到,這兩種情況其中一種肯定是假設錯誤的(當最小割只有唯一一個)。假設矛盾的情況下,根據邏輯,計算結果有可能是正版最小割,也有可能是權重亂七八糟的山寨最小割。

因此,還必須證明,假設矛盾的情況下,不管計算結果為何,那些山寨最小割一定比正版最小割來得差:

一、最小割根本不是st同側:正版最小割包含邊st,顯然邊st權重比較小。因為權重較小的邊被收縮了,所以遞迴求得的割通通大於正版最小割(或等於,當有多個最小割)。

二、最小割根本不是st異側:正版最小割不用邊st,顯然邊st權重比較大。因為最小st割一定用到邊st,所以最小st割大於正版最小割(或等於,當有多個最小割)。

如此一來就能保證,兩種情況下分別求得的最小割,權重較小的那一個,一定是正版最小割。

這比一般的Divide-and-Conquer Method還要複雜一點。

演算法

一、用Maximum Adjacency Search隨便求一個Minimum s-t Cut。
二、收縮s點與t點,重複步驟一,直到圖上只剩一點。
三、這V-1個Minimum s-t Cut當中,權重最小者,即是Minimum Cut。

時間複雜度

下列兩項總和,主要取決於第一項:

一、V-1次Maximum Adjacency Search。

二、收縮點,收縮V-1次。圖的資料結構為Adjacency Matrix是O(V²),圖的資料結構為Adjacency Lists是O(V)。

找出一個最小割

實作時要小心圖不連通的情況,圖不連通的地方就是最小割,權重為零。

UVa 10989

Minimum Cut: Karger's Algorithm

用途

無向圖,求出其中一個最小割。

Monte Carlo Algorithm,不保證答案百分之百正確。

演算法

圖上隨意取一條邊,要嘛在最小割上,要嘛不在最小割上。

圖上隨意取兩個點,要嘛在最小割異側,要嘛在最小割同側。

通通當作不在最小割上、都在同側,事情不就簡單多了?

重複下述步驟V-1次,直到圖上剩下兩個點,得到一個割,推定為最小割:
甲、隨機取圖上一條邊。
乙、推定這條邊不在最小割上,
  也就是推定這條邊的兩個端點在最小割同側。
  收縮這條邊的兩個端點,不影響最小割權重。

Kruskal's Algorithm也是每次選擇一條邊、連結兩端點。兩者的差異,在於Karger's Algorithm是隨機選擇一條邊,而Kruskal's Algorithm是選擇權重最小的邊。

時間複雜度不知如何計算,可能很接近O(V+E)吧。

正確率

既然是隨機化演算法,就得計算一下正確率了!

令一張圖的最小割有c條邊。

補充零邊,令圖上每一個點連著c條邊。如此一來,圖上每一個割都有c條邊、每一個割都可能成為最小割,利於分析。

現在圖上總共c⋅V/2條邊。V是點數。

隨機從圖上選擇一條邊,這條邊在最小割上的機率是c / (c⋅V/2) = 2/V,不在最小割上的機率是1 - 2/V。

Karger's Algorithm每個步驟選擇的邊,都必須不是最小割的邊,最後才能得到正確的最小割。選對的機率是1 - 2/V。

每個步驟都會減少一個點,推得正確率是[1-2/V] ⋅ [1-2/(V-1)] ⋅ … ⋅ [1-2/4] ⋅ [1-2/3] = 1/C(V,2) = Ω(1/V²) = Ω(V⁻²)。

根據這個正確率,只要實施V²次以上的Karger's Algorithm,結果就相當準確了!