最小生成樹 - 包教包會

對於一個連通無向圖 G = (V,E)，且給定一個權重函數 w ( e ) ， 希望找到一個 邊的無環子集 T， 使得 T的 總權重最小。則T被稱為 圖G的最小生成樹。

- 如何形成最小生成樹？

- GENERIC-MST （G，W）

- A = ?

- while A does not form a spanning tree

- find an edge ( u, v) that is safe for A

- A=A∪{ (u,v) }

- return A

- 以上為摘自 演算法導論 P363 的 求解最小生成樹的 大體思路 的偽代碼。

- A為某一棵最小生成樹的子集。在循環的過程中，A從空集，一步一步添加新邊，最終生成T。

- 首先要明確，圖G的最小生成樹可能不止一個。雖然形式上A是在循環中一步一步的向某個T前進，最終A會形成一個確定的最小生成樹 T，在循環過程中我們 不知道A是哪棵最小生成樹的子集，換句話說我們找新的邊(u,v)時不可能是有意識得從 T 搜尋。我們只是不斷地保證 A是某一棵最小生成樹的子集（可能也是其他最小生成樹的子集）。到最後也就形成了某一棵最小生成樹——T.

- 從以上，我們可以看到在循環中所要保持的 循環不變式 是：

- 在每遍循環前，A是某一棵最小生成樹的子集

- 疑問：

- 如何保證循環不變式？（怎樣找到安全邊( u, v) ）

- 為什麼最終能夠得到一棵生成樹？

- 為什麼這棵生成樹是權重最小的？

- 顯然解決掉以上3個問題那就完成了對 GENERIC-MST （G，W）的證明。

- 關鍵代碼在第三行。找到一條對於 A 是安全的一條邊 { (u,v) }。即，A∪{ (u,v)} ? T。那麼(u,v)存不存在呢？存在的話又如何去找呢？為了解決這個問題我們引入如下概念。

- 無向圖G（V,E）的一個 切割 （S,V-S）是集合V的一個劃分。

- 就是把圖 G（V,E） 里的所有點分成兩堆 一堆叫 S，一堆叫 V-S

- 如果有一條邊 （x , y），該邊的兩個端點 x，y 分別屬於 S，V-S （或V-S，S），那麼 邊（x , y）橫跨 切割 （S,V-S）

- 就是吧，本來有一對點被一條邊好好地連著呢，但 切割 （S,V-S）沒把這對點放在同一堆裡面，生生得拆散了它們。

- 給定一個邊集 A 如果 A 的任一條 （x , y） 邊都沒 橫跨 切割 （S,V-S），那麼 切割 （S,V-S）就是 尊重 邊集A的。

- 換句話說，我們把邊集A中，相互聯通的點，給分成一堆一堆的，而 切割 （S,V-S）不會把任一堆點給分開。

- 所有 橫跨 切割 （S,V-S）的邊 中權重最小的邊叫做 輕量級邊

- 下面我們先給出一個通過以上定義來描述的一個找安全邊 { (u,v) } 的一個定理：

- 設 G=（V,E）是一個在邊E上定義了實數值權重函數 ω 的連通無向圖。

- 設1 集合A為E的一個子集，且A包括在圖G的某棵最小生成樹中 T 中。

- 設2 切割 （S,V-S）是圖G中 尊重 邊集A的任意一個 切割

- 設3 邊（u，v）是橫跨 切割 （S,V-S）的一條 輕量級邊

- 那麼邊（u，v）對於集合A是安全的。（A∪{ (u,v)} ? 某棵最小生成樹 ）

- 證明：

- 如果邊（u，v）∈ T，那麼定理顯然成立。

- 如果變邊（u，v）? T，那麼 A∪( u,v ) 就應該包含於另一顆最小生成樹 T，找到這條邊和這棵樹我們就勝利了。

- 對於 設1 在循環開始時 設1 成立，在循環過程中通過加入安全的邊保持成立（尋找該邊就是我們正在證明的）

- 記 圖 （V , A） 為 GA

- 對於 設2 這樣的切割 （S,V-S）也是能找到的，因為由 設1 我們知道 「A包括在圖G的某棵最小生成樹中 T 中」那麼顯然A是由兩個及以上的連通分量所組成的。不把每個連通分量給分開的切割 （S,V-S）都滿足條件。由於我們每次往A中都是添加的一條邊，那麼每一個連通分量都至少包含兩個點。在GA 中，對於切割 （S,V-S），如果我們把每個連通分量看成是一個小組，那麼S(或V-S) 中包含的點就是幾個小組（連通分量）加上一些孤零零的點（也視為連通分量，但並不直觀地產生自A）

- 同時我們能夠知道對於任何一個切割 ，在最小生成樹 T 中都有一條邊（x，y）橫跨 該 切割。

- 記所有 橫跨 切割（S,V-S）的邊，為邊集 D，那麼（x，y）肯定屬於邊集 D，如果沒有其他邊，那麼（u，v）=（x，y），即邊（u，v）∈ T，這就回到了證明的第一步。如果（u，v）≠（x，y），那麼設 T = T - { ( x , y ) } ∪（u，v），T 顯然是一棵不同於 T 的一棵最小生成樹，那麼A ∪ { ( u ,v ) } ? T，那麼( u ,v )就是安全的。【 如何保證循環不變式？（怎樣找到安全邊( u, v) ）—— 疑問一 完畢】

- 再來看看 ( u ,v ) ， ( u ,v ) 由 設3 可知我們找到是輕量級邊，那麼 ω ->（u，v）≤ ω -> （x，y） ，即( u ,v )的權重是 小於等於（x，y）的權重的，那麼由T = T - { ( x , y ) } ∪（u，v） 我們可以推出ω （T）≤ ω （T）。而T也是一棵最小生成樹，那麼 ω （T） ≤ ω （T），即 ω （T） = ω （T） 。那麼 T 也是最小生成樹 【為什麼這棵生成樹是權重最小的？—— 疑問三 完畢】

- 證畢

- 再回頭看看我們所找的那一條邊 ( u ,v ) ，它 橫跨 切割 （S,V-S）， In other words，對於圖 GA 邊 ( u ,v ) a有兩種情況：

- 連接了分屬楚河兩岸的（切割 （S,V-S） ） : 倆小組

- 連接了分屬楚河兩岸的（切割 （S,V-S） ）：一小組，一單身點

- 顯然這兩種情況下，集合A 都是保持著無環的狀態，（最小生成樹的子集）。【為什麼最終能夠得到一棵生成樹？ —— 疑問二 直觀看法】

- 至此，相信大家都能接受這個找最小生成樹的大體方法了

- Kruscal 演算法 就是對這個的具體應用。
推薦閱讀：