最小生成樹

最小生成樹是圖論裡頭，經典演算法的其中之一。 由於該題目有著太多適用於貪婪演算法的美好性質，這個問題也時常被拿來當作經典貪婪演算法的例題。 最小生成樹的演算法有三大流派：Dijkstra-Jarník-Prim (1959, 1930, 1957)、Kruskal (1956)、以及 Borůvka (1926) 這三種作法。 在說說這些演算法之前，我們先來好好地定義一下最小生成樹問題，以及描述最小生成樹的一些性質。

最小生成樹問題

給定一個連通無向有權圖 \(G=(V, E)\)、每條邊有權重 \(w:E\to \mathbb{R}\)。找出一個生成樹 \(F\)，使得它上面所有邊權重的總和最小。

要如何找出最小生成樹呢？以下的定義可以讓我們好好地刻畫出關於最小生成樹中，邊的性質。

定義（Safe Edge）

對於一條邊 \(e=(u, v)\)，若存在子集合 \(S\subseteq V\)，使得 \(u\in S, v\notin S\)，並且 \(w(e)\) 是所有從集合 \(S\) 連出去的邊當中，權重最小的一個（即 \(w(e)=\min_{x\in \partial(S)} w(x)\)）， 那麼我們說 \(e\) 是一條安全邊 safe edge。

定理 MST.1

假定圖 \(G\) 上所有邊權重皆不相同，那麼該圖上所有的安全邊，恰好形成一棵最小生成樹。

定理 MST.1 的證明

定義 \(E'\) 為所有安全邊所形成的集合。令 \(T\) 為圖 \(G\) 上任何一棵最小生成樹（事實上我們最終能得出最小生成樹是唯一的結論）。我們要證明的敘述便是 \(E'=E(T)\)。

Part 1: \(E'\subseteq T\)

對於任何一條安全邊 \(e=(u, v)\in E'\)，如果這條邊不在最小生成樹上面 \(e\notin T\)，由於 \(T\) 是連通的，那麼 \(T\) 上面存在一條從 \(u\) 到 \(v\) 的路徑 \(P\)。 此時，根據安全邊的定義，我們令 \(e\) 是從集合 \(S\) 當中外連權重最小的一條邊，並不妨假設 \(u\in S\) 且 \(v\notin S\)。 依此假設我們得知路徑 \(P\) 上面至少有一條邊 \(f\) 跨越了 \(S\)。這條邊的權重根據安全邊的定義，必定有 \(w(f) > w(e)\)。 也就是說，當我們考慮 \(T+e-f\) 的時候，得到一個總權重更小的生成樹，與 \(T\) 之選取矛盾！

Part 2: \(T\subseteq E'\)

接下來我們只要說，所有最小生成樹上的邊都是安全邊就行了。對於一條樹上的邊 \(e\in T\)，它可以將樹分成兩個連通部分，對應到的點集合分別寫作 \(S\) 與 \(V\setminus S\)。 我們宣稱 \(e\) 此時必定是集合 \(S\) (或 \(V\setminus S\)) 外連的邊中權重最小的一個。 若不然，存在另一條權重更小的邊 \(w(f) < w(e)\)，使得 \(T-e+f\) 的總權重更小，與 \(T\) 為最小生成樹的假設矛盾。由此得知 \(e\in E'\)，證畢。

係理 MST.2

假定一張圖上所有邊權重皆不相同，那麼該圖有著唯一的最小生成樹。

參考資料

• https://jeffe.cs.illinois.edu/teaching/algorithms/book/07-mst.pdf