動機
最小割把無向圖分成兩個非空部分,並使橫跨兩部分的邊數最少。一種隨機算法可以透過反覆均勻隨機地選取一條邊並收縮它來找到最小割。收縮某個特定最小割每一側內部的邊會保持該割不變;收縮其中一條橫跨邊則會破壞該割。
算法並不知道哪些邊橫跨最小割。它的分析轉而估計:在每個階段都避開某個固定最小割的概率。對於大圖,所得的成功概率很小,但獨立重複運行可以將其放大。算法的輸出始終是一個合法的割;隨機性只影響該割是否為最小割。
定義
定義 6.2.1
(割與最小割的大小)
設 是具有 個頂點的連通無向多重圖。平行邊是互不相同的邊副本;自環不橫跨任何割,可以捨棄。割是原圖頂點集的一個劃分,分成兩個非空集合。割的大小是兩個端點分別位於兩側的邊副本的個數。設 為最小割的大小;由連通性得 。
定義 6.2.2
(收縮與隨機收縮算法)
收縮一條邊,是指把它的兩個端點合併為一個超頂點。保留平行邊作為互不相同的副本,並捨棄合併時產生的自環。每個超頂點代表原圖頂點的一個非空集合。隨機收縮算法反覆在當前所有邊副本中均勻隨機地選取一條,並收縮所選的邊,直到恰好剩下兩個超頂點為止。算法返回這兩個超頂點所代表的原圖頂點劃分。
在分析中,從任意數量的邊副本中均勻選取被視為理想的隨機選擇操作。基於有限隨機位元的實現必須另行說明如何做到均勻抽樣,以及如何處理拒絕抽樣。
定理
定理 6.2.3
(單次運行的成功概率)
對於每個 的連通無向多重圖,一次隨機收縮運行返回最小割的概率至少為 。
定理 6.2.4
(獨立重複)
進行 次獨立運行,返回所找到的最小的割,未能返回最小割的概率至多為
證明
證明:保護一個最小割
證明
(固定最小割的存活)
固定一個特定的最小割 ,其大小為 。只要沒有橫跨該割的邊被收縮,就稱該割存活。若該割存活,則當前每個超頂點都完全位於某一側。在算法停止之前,兩側仍然非空,並且仍有同樣的 條邊副本橫跨兩側:橫跨該固定割的邊尚未被收縮,而且只要該割存活,它就不可能變成自環。
假設當前有 個超頂點且該割已存活。每個超頂點都代表原圖頂點的一個非空真子集,因此由最小割的定義,從它出發的邊數至少為 。對當前無自環的多重圖計算度數,總度數至少為 ,因而邊副本至少有 條。平行副本在度數之和與隨機選取中都分別計數。
恰有 條當前邊副本橫跨該固定割。在此前一直存活的條件下,下一條被均勻選取的邊橫跨該割的概率至多為
因此在下一次收縮中保持該割的條件概率至少為 。把 的這些條件下界相乘:
當 時,乘積為空,等於 1,唯一的割已經被返回。如果該固定割一直存活到只剩兩個超頂點,則每一側至少含有一個超頂點,所以每一側恰由一個超頂點代表。返回的割恰好就是該固定最小割。算法也可能因返回另一個最小割而成功,因此這給出的是總成功概率的下界。
證明透視
最小割的極小性用在哪裏
證明只有一步不顯然:它保護的是一個固定的最小割,而不是去問最終輸出是不是最小割。 的極小性恰好用一次,即把每個度數的下界定為 。離開某個超頂點的邊副本構成原圖的一個割,而沒有任何割小於 。由於保留了平行副本,無論已形成多少副本,這個度數計算都成立。連通性給出 ,所以比值 有定義。
同一步也說明為甚麼被保護的割必須是最小割:對大小為 的割,橫跨概率只能被界定為 ,它可能超過一。乘積隨後裂項相消, 只剩下 。論證得以收束,是因為存活的割在剩下兩個超頂點時,恰好就是那個固定的割。
證明:重複運行
證明
(獨立重複)
每次運行都從原圖的全新副本出發,使用獨立的隨機選擇,並在原圖中評估返回的劃分。每次運行成功的概率至少為 。由獨立性,失敗概率至多為 。初等不等式 給出指數界。
如果至少有一次運行返回最小割,那麼所有返回的割中最小的那個大小為 :任何合法的割都不可能小於最小值。因此,只要有任何一次運行成功,返回所觀察到的最小割就會成功。要使失敗概率至多為 (),只需取
並向上取整為整數。該保證針對的是錯過所有最小割的概率,而不是輸出非法劃分的概率。
為甚麼邊收縮能保持一個割
當前的超頂點代表合併進它的所有原圖頂點之聯集。收縮一條當前的邊,就是把它兩端所代表的集合合併。如果兩個集合位於固定割的同一側,它們的聯集仍在該側,所以當前每個超頂點仍完全落在某一側之內。端點位於不同側的原圖邊,其端點仍然屬於不同的超頂點,因而仍是橫跨的邊副本。內部的邊可能變成自環並消失,但不改變橫跨邊的數目。
反之,收縮一條橫跨該固定割的邊,會產生含有兩側頂點的超頂點。之後對整個超頂點所做的任何劃分都無法再把這些原圖頂點分開,所以這個特定的割就丟失了。這兩個陳述解釋了存活事件,而無需假設收縮能同時保持所有的割。
條件概率的乘積並不要求各階段的收縮選擇互相獨立。它使用的是相繼存活事件概率的鏈式法則,以及一個對每個存活歷史都成立的下界。獨立性在之後單獨的重複運行保證中才需要,那時每次完整運行都使用全新的隨機選擇。
例題詳解
例題 6.2.5
(兩個頂點)
兩個頂點由三條平行邊副本相連,它們已經是最終的兩個超頂點。算法不進行任何收縮,以概率 1 返回唯一的割,其大小為三。公式給出 。
例題 6.2.6
(三角形)
在三角形中,每個把一個頂點分離出來的割大小都是二。算法收縮一條均勻隨機選取的邊,留下由兩條平行邊相連的兩個超頂點。因此每一種可能的選擇都返回最小割。定理的下界只有 ,所以它不一定是緊的。
例題 6.2.7
(平行邊分別被抽樣)
假設當前的圖中邊 有兩個副本,邊 有一個副本。在邊副本中均勻選取,選中 的某個副本的概率是 ,而不是 。若把每一對不同的端點平等對待,就會定義出另一種算法,並使所述的概率計算失效。
例題 6.2.8
(選取運行次數)
當 時,一次運行的成功概率保證至少為 。要使所給出的指數失敗界至多為 ,可選取 次獨立運行。它們的實際成功概率可以高於該保證。
四邊形圈的計算
取圈 ,每條邊各有一個副本,並固定把 與其餘三個頂點分開的割。它的大小為二。第一次收縮恰好在選中 或 時避開該割,每條的概率為 ,所以固定割在第一步存活的概率為 。
如果收縮的是 ,當前的圖有三個超頂點:、 和 。其餘的邊由原來的圈決定:–、– 以及 –,其中 – 來自 ,– 來自 ;被收縮的 邊變成了自環並被捨棄。於是當前的圖是一個有三個邊副本的三角形。恰有一條邊 – 位於非 的一側之內,所以第二步的條件存活概率為 。收縮的是 的情形是對稱的。因此固定割存活的概率為 ,等於 。
這個計算只追蹤一個固定的割。即使隔離 的割被破壞,四邊形圈的其他最小割仍可能被返回。事實上,第一次收縮之後圖就成為三角形,再收縮任何一條邊,都會剩下由兩條邊副本連接的兩個超頂點。因此這個圖上的每次運行都返回最小割,固定割的存活概率 只是成功概率的下界。
常見錯誤
反例模式
一次收縮可能破壞某個特定的最小割
在三角形中,固定隔離頂點 的割。收縮與 關聯的任一條邊,都會把該固定割的兩側合併,所以它不再存活。算法仍然可以返回另一個最小割。證明追蹤一個固定的割以得到下界,這並不是所有可能的成功的必要條件。
常見錯誤
(捨棄平行邊並不安全)
捨棄自環是安全的,因為自環不橫跨當前超頂點的任何劃分。捨棄平行邊則不安全:每個副本都計入割的大小,並且必須體現在均勻抽樣的概率中。帶權的變體需要另行建立抽樣與成本模型。
常見錯誤
(重複運行需要全新的隨機性)
單次運行的下界並不會自動使各次重複互相獨立。指數形式的失敗概率計算假定每次運行都使用全新的獨立選擇。重複使用相關的隨機選擇可能使失敗事件相關,需要另做分析。
運行時間與概率模型
一種直接的實現可以保存當前邊副本的顯式列表,每次收縮之後掃描該列表來更新端點並移除自環。這是多項式時間,儘管不一定是最快的實現。把運行重複 次,成本乘以 ,而 的對數決定了所述充分界所需的重複次數。
證明把均勻選取邊副本視為精確成立。如果有限位元的實現使用拒絕抽樣,它應當說明自己的停止與誤差保證,而不是預設每個邊數都是 2 的冪。理想選擇下的概率定理獨立於這些實現細節而保持有效。
連通性保證:當剩餘超頂點多於一個時,至少有一條邊連接兩個超頂點,因此算法可以繼續進行。對於不連通的輸入,最小割為零,可取一個連通分量與其餘部分構成的割得到;盲目套用連通圖的收縮證明,會出現除以 的情形。
評估返回的劃分
最後剩下的兩個超頂點編碼了原圖頂點的兩個非空集合。直接的實現可以統計橫跨這兩個集合的原圖邊副本個數來評估該割,即使其收縮所用的數據結構已經改變或捨棄了內部的邊。輸出始終是合法的劃分,所以它的成本不可能低於真正的最小值。正是這一單側性質,使得重複運行可以選取最小的結果而不引入虛假的最小值。
算法在某些運行中可能返回非最小的割。成功概率定理是對每個連通輸入成立的下界,而不是某個觀察到的割為最優的證明。若要不依賴概率保證而驗證單次運行的最優性,需要確定性的證書或獨立的精確最小割方法。
存活論證迫使最小割至多有 n(n-1)/2 個,而圈圖可以達到這個數目。
自然延伸的下一個問題
一個圖最多可以有多少個最小割?
存活論證迫使最小割至多有 n(n-1)/2 個,而圈圖可以達到這個數目。
存活的證明適用於每一個最小割,所以每個最小割被輸出的概率都至少是 。對不同的割,「輸出恰為割 」這些事件互不相交,概率之和至多為一。因此含 個頂點的連通圖至多有 個最小割。這個數目可以達到:在 個頂點的圈圖中,刪去任意兩條邊都剩下兩條路徑,得到 個大小為二的最小割。上面的四邊形圈例子正是這種情形,而且每次運行都成功。
總結
固定的最小割有 條橫跨邊,而仍存活的 個超頂點的圖至少有 條邊。各條件存活概率的乘積至少為 。獨立運行放大了這一單側的成功保證。
練習
快速檢查
(當 時,單次運行的保證成功概率是多少?)
把 代入 。
解答 · 答案
該界為 。
快速檢查
(為甚麼收縮之後要捨棄自環?)
想一想自環能否橫跨超頂點的任何劃分。
解答 · 答案
自環的兩個端點在同一個超頂點內,所以它不橫跨超頂點的任何劃分,也就不可能對返回的割有所貢獻。它不應被選作收縮的邊。
快速檢查
(對於 ,給出 次獨立運行全部失敗的概率的一個上界。)
使用單次運行的下界 及獨立性。
解答 · 答案
單次運行的成功概率至少為 ,所以六次全部失敗的概率至多為 。指數界 是另一個有效但稍弱的上界。
快速檢查
(解釋:只要有任意一次運行成功,各次運行中返回的最小割就是正確的。)
分別從兩個方向比較所觀察到的最小大小與 。
解答 · 答案
每次運行都返回合法的割,其大小至少為 。如果有一次運行返回大小 ,則所觀察到的最小大小既至多為 又至少為 ,因此它是最小割。