Cut

Cut

中譯「割」。一個Cut把一張圖上的點分成兩群。也就是說,每一個點都必須選邊站(也可以全部都站在同側,另一側就是空的)。以數學術語來描述:一個Cut把一張圖上所有點所構成的集合,重新劃分成兩個集合。

如果圖上的邊擁有權重,一個Cut也可以有權重。無向圖:由第一群點橫跨到第二群點的所有邊的權重總和。有向圖:由第一群點橫跨到第二群點的所有邊的權重總和,減去由第二群點橫跨到第一群點的所有邊的權重總和。

Cut切斷了點與點之間的連結,將一張圖一分為二。各位可以想一想Cut可以應用在哪些地方。

【註:一般大家在談Cut的時候,經常是使用另外一種定義:Cut的其中一側至少要有一點,而且圖上的邊的權重均非負值。我想這應該是因為Cut的演算法,一開始是從Flow的演算法推演來的。】

Minimum Cut(Min-Cut)

「最小割」。給定一張圖,權重最小的Cut就是Min-Cut。一張圖上可能會有許多個Min-Cut。

Maximum Cut(Max-Cut)

「最大割」。給定一張圖,權重最大的Cut就是Max-Cut。一張圖上可能會有許多個Max-Cut。

Contraction

「收縮」。在一個Cut之中,把Cut的其中一側的任兩點作合併,不會影響此Cut的權重。合併圖上的點、卻不影響一個Cut的權重,這個行為就叫做Contraction。

進行Contraction之後,甚至可以把兩點之間多重的邊的權重相加合併,也不會改變Cut的權重。

Maximum Adjacency Search

Maximum Adjacency Search

在講述Min-Cut的演算法之前,這裡先介紹一個與Min-Cut極有關係的Maximum Adjacency Search:

1. 建立一個空的A集合。
2. 首先隨便在圖上找一個點,加入到A集合當中。
3. 令w(A, x)是「目前的A集合的各個點」與「x點」之間所有的邊的權重總和。
   逐次加入一個尚未加入A當中、且w(A, x)最大的x點到A集合中。
4. 圖上所有點都加入到A集合之後,各個點加入的順序即為所求。

Maximum Adjacency Search(adjacency matrix)

利用Dynamic Programming來實做程式碼,時間複雜度是O(V^2)。如同Dijkstra's Algorithm一樣,可以另外再配合Priority Queue,成為O(V+ElogE)。

Maximum Adjacency Search v.s. Min-Cut

在一張無向圖當中,邊的權重皆非負值,令這張圖經過Maximum Adjacency Search所得到的順序是x1-x2-…-xV。在這張圖中,{x1 … xV-1}與{xV}這一個Cut,必會是這張圖「限制xV-1和xV在Cut不同側」的Min-Cut 。

筆者曾努力想過證明,但能力不足,無法證得這個性質。如果有人懂得證明,歡迎告知。

Min-Cut: Stoer-Wagner Algorithm

Stoer-Wagner Algorithm

用來求出一張無向圖的其中一個Min-Cut。此處提及的Cut其中一側至少要有一點,而且圖上的邊的權重均非負值。

分割問題的方法

任取圖上兩點,這兩點要嘛就是在Min-Cut同側,要嘛就是在Min-Cut不同側。

如果這兩點將在Min-Cut同側,那麼我們可以進行Contraction,合併這兩點為一點,製作出一張比原圖還要少一點的圖,縮小問題範疇。這麼做不會影響此兩點在同側的Cut們的權重,當然也就不會影響Min-Cut的權重。

如果這兩點會在Min-Cut不同側,則需要想辦法找出這兩點在不同側的Min-Cut。

演算法

Stoer-Wagner Algorithm巧妙地運用了Maximum Adjacency Search的性質,求出一個限制某兩點在不同側的Min-Cut。

令map[a][b]是a點到b點的距離(即是邊的權重)。

1. 重複下面這件事V-1次,以求出其中一側至少要有一點的Min-Cut:
 甲、Maximum Adjacency Search:對圖上所有點使用Maximum Adjacency Search,
   最後兩點依序為s點和t點,求出s點和t點在不同側的Min-Cut。
 乙、Contraction:合併s點和t點,繼續求出s點和t點在同側的Min-Cut。
   對於圖上每一點x,map[s][x]=map[x][s]=map[s][x]+map[t][x](把t點併至s點)。

時間複雜度

約是V次的Maximum Adjacency Search,總共是O((V^2) * V) = O(V^3)。

計算Min-Cut的權重(adjacency matrix)

實做方式可參考「Shortest Path: Dijkstra's Algorithm」。

找出一個Min-Cut(adjacency matrix)

紀錄最小值是出現在哪裡。【待補文字】

找出所有的Min-Cut

歡迎提供想法。【待補文字】

這裡提供兩題練習題。

Uva 10480 10989

Min-Cut: Karger's Algorithm

Karger's Algorithm

用來求出一張圖的其中一個Min-Cut(或Max-Cut)。特別的是,這是個隨機演算法,屬於Monte Carlo Algorithm,也就是不保證答案百分之百正確。

演算法

任取圖上兩點,這兩點要嘛就是在Min-Cut同側,要嘛就是在Min-Cut不同側。如果這兩點在Min-Cut同側,可以使用contraction來減少一個點,縮小問題範疇,不致影響Min-Cut的權重。

1. 重複下面這件事V-1次,直到圖上剩下兩個點,剛好可以作出一個Cut:
 甲、隨機取圖上一條邊:猜測這條邊不在Min-Cut上、這條邊的兩個端點在Min-Cut同側。
 乙、Contraction:合併這條邊的兩個端點。

這個演算法近似於「Minimum Spanning Tree: Kruskal's Algorithm」:每次都選擇一條邊,讓這條邊的兩個端點相連在一起。唯一的差異是Karger's Algorithm是隨機地選擇一條邊,而Kruskal's Algorithm是選擇權重最小(或最大)的邊。

正確率

既然是隨機演算法,就得計算一下正確率了!下面這段正確率的證明,是我從論文中讀到的。我覺得這個證明非常弔詭,不知道我是否有理解錯誤:

假設一張圖的Min-Cut至少有c條邊。然後,令圖上每一個點至少都連著c條邊,才能使這張圖的任一個Cut至少都有c條邊、任一個Cut都可能成為Min-Cut。

根據此設定,可推導出這張圖上至少共有c*V/2條邊。V是點的總數。

基於方才的假設,隨機從圖上選擇一條邊,這條邊在Min-Cut上的機率至多是c / (c*V/2) = 2/V,不在Min-Cut上的機率至少是1-2/V。

Karger's Algorithm每個步驟所選到的邊,都必須不是Min-Cut上的邊,結果才會正確。每個步驟都會減少圖上的一個點,推得Karger's Algorithm的正確率至少是[1-2/V] * [1-2/(V-1)] * … * [1-2/4] * [1-2/3] = 1/C{V,2} = Ω(1/V^2) = Ω(V^-2)。

根據這個正確率,只要進行V^2次以上的Karger's Algorithm,結果就會相當準確了!

Min-Cut: Karger-Stein Algorithm

Karger-Stein Algorithm

Karger-Stein Algorithm是Karger's Algorithm的加強版。

筆者尚未讀懂,歡迎提供想法【待補文字】。