從局部選擇到整棵樹
網絡可能有許多方法連接全部頂點。這與從單一起點找最短路徑不同:一條選中邊在樹的成本中只計一次,不是每條使用它的路徑都再計一次。
定義 4.1.1
(生成樹、最小生成樹與跨割邊)
假設輸入為有限、連通、無向且沒有自環的多重圖,有 個頂點及 條邊。平行邊彼此不同,也可有相同權重。邊權可以是任意有限實數,包括零和負數。生成樹連接每個頂點且沒有環,所以有 條邊;其權重是所選邊的權重之和。最小生成樹使這個總和最小。對頂點集 (),若一條邊恰有一個端點在 中,就說它跨越割 。以下把權重比較計為常數成本運算。當 ,空邊集是權重為零的生成樹。
算法
把邊按權重非遞減排序;相同權重可按任一固定次序處理。從空集合 開始掃描:若當前邊的兩端位於 的不同連通分量,便加入它;否則跳過。掃描完後輸出 。
命題 4.1.2
(輸出是生成樹)
對連通的輸入,掃描所輸出的 是一棵生成樹。
證明
(沒有環,分量之間也沒有空隙)
所選邊始終沒有環,因為每條新邊都連接兩個不同分量。最後的森林必連接所有頂點:否則,由於輸入連通,原圖中連接兩個最終分量的邊路徑上,必有一條邊從一個最終分量跨到另一個,而該邊被掃描時兩端在不同分量,不可能被跳過。連通森林是樹,因此有 條邊。
引理 4.1.3
(割的交換)
設 包含於某棵最小生成樹 ,並設 是頂點集(),使 中沒有邊跨越 。若 是所有跨越此割的邊中最輕的一條,則 包含於某棵最小生成樹。
證明
(以 e 換走較重的跨割邊)
若 ,保留 。否則把 加入 會產生唯一的環。環跨越一個割的次數是偶數,而 是其中一次,所以環中還有另一條跨割邊 ,且 。 中沒有邊跨越此割,所以 。由於 是跨割邊中最輕的,。從 中移走 會破壞唯一的環,剩下一個有 條邊的連通圖,即生成樹 。它包含 ,權重為 。由於 最小, 也是最小生成樹。
定理 4.1.4
(Kruskal 的貪心保證)
對符合上述假設的每個連通輸入,算法都輸出最小權重生成樹。相同權重和負權重均不影響此保證。
交換不變量
證明
(每條被選的邊都是最輕的跨割邊)
維持不變量:存在一棵最小生成樹包含 中已選的每條邊。起初成立,因為有限連通圖有最小生成樹。假設算法即將加入 ,其兩端位於 的不同分量。令 為含有其中一個端點的分量。 是分量,所以 的邊都不跨越 。
是最輕的跨割邊。若另一條跨割邊 在排序中較早出現,則它被掃描時兩端已在不同分量,因為分量只會合併,且在加入 前仍然分開。算法便會選取它,與 沒有跨割邊矛盾。因此每條跨割邊在排序中都在 之後或就是 ,權重至少為 ,相同權重亦然。由割的交換引理,不變量得以維持。被跳過的邊不改變 。
結束時 本身是生成樹,並包含於某棵最小生成樹。相同頂點集上的兩棵生成樹均有 條邊,所以二者相同。這證明輸出最優,而不只是證明它是一棵樹。
證明透視
為何下一條跨割邊安全
不明顯的一步是交換:不去討論所有生成樹,而是取一棵已包含 的最優樹,再作局部修補。每個假設各有作用。輸入連通,加上 中有邊跨越該割,保證了 所產生的環含有第二條跨割邊 。 是 的分量這一點,使 不屬於 ,所以交換不會破壞已選的邊。排序掃描使 成為跨割邊中最輕的,而不等式 只需要 ,因此相同權重沒有影響。
論證中沒有對權重作加、減或縮放,只作比較,所以負權重也容許。證明得以完結,是因為每一步都保留一棵最優樹,而最終的 恰有 條邊,沒有餘地與那棵樹不同。若 只是某條跨割邊而不是最輕的,交換可能令權重增加,不變量便會失效。
掃描例子
例題 4.1.5
(相同權重與被跳過的邊)
設 權重為 , 和 權重為 , 權重為 , 權重為 。若相同權重中先掃描 ,便選取 ;跳過會閉合三角形的 ;再選取 。所得樹權重為 。若兩條同權邊次序相反,便選 、跳過 ,得到另一棵同權重的最小樹。交換證明涵蓋兩種次序。
例題 4.1.6
(平行邊與負權重)
取頂點 , 與 之間有兩條平行邊,權重分別為 和 ,另有權重 的邊 與權重 的邊 。排序後依次是權重 的邊、、,然後是權重 的邊。選取連接 的權重 的邊;選取 ,把 接到該分量;跳過 ,因為 已連通;也跳過權重 的平行邊。所得樹有兩條邊,權重為 。其餘四棵生成樹的權重為 、、 和 ,都較大。
例題 4.1.7
(不連通的輸入只得到森林)
取四個頂點 ,只有權重 的邊 和權重 的邊 。掃描把兩條都選取,結束時只有 條邊,而生成樹需要 條。輸出是權重為 的最小生成森林,但整個圖不存在生成樹,所以上面的保證並不適用。
反例模式
最便宜的邊可能形成環
考慮 構成的三角形,三邊權重均為 ,另有權重為 的邊 。三條最便宜的邊構成環,並使 沒有連接,儘管四個頂點需要的邊數正是三。生成樹必須選 和兩條三角形邊,權重為 。按權重排序必須配合分量測試:它會跳過三角形的第三條邊,然後選取 。
常見錯誤
(權重相同時以為答案唯一)
在第一個掃描例子中, 與 的兩種次序給出兩棵不同的最小生成樹 與 ,權重同為 。決勝規則決定輸出哪一棵,卻不影響它是否最優。只有當所有權重互不相同時,最小生成樹才是唯一的。
常見錯誤
(先去掉或平移負權重)
由於最短路徑的方法可能需要非負權重,人們容易想到把每條邊加上同一個常數。這裏並不需要:證明只比較權重。對權重為 的三角形,算法直接選取 與 ,無須調整。對生成樹而言,把每條邊都加上同一個常數 ,每棵樹的權重恰好改變 ,所以最優樹不變,但這是關於生成樹的觀察,並不是算法的要求。
實作與邊界
一種簡單實作為每個頂點儲存當前分量標籤。合併兩個標籤時掃描所有頂點,把其中一個標籤改為另一個。測試需 ,合併需 ,故在此比較模型下,排序與掃描共用 次運算。更快的分量數據結構需要另行分析;以上證明不依賴特定實作。
若輸入不連通,同一掃描會得到森林,但整個圖不存在生成樹。在聲稱得到生成樹前,應檢查連通性,或檢查最終森林是否有 條邊: 個頂點上的森林若有 條邊便連通。負邊可以被選中,也不會使目標向下無界,因為有限圖只有有限多棵生成樹。
練習
快速檢查
(在例子中先掃描 再掃描 ,列出所選邊及總權重。)
跳過會閉合環的邊。
解答 · 答案
選取 ,跳過 ,總權重為 。
快速檢查
(一個三角形的邊權為 ,求一棵最小生成樹及其權重。)
三角形的生成樹有兩條邊。
解答 · 答案
選權重為 和 的邊,得到權重 的樹。交換論證對負權重仍然有效。
快速檢查
(為何被選邊與另一條相同權重的跨割邊,都可能分別出現在某棵最優樹中?)
看看交換證明需要哪個不等式。
解答 · 答案
交換證明只需要 ,不要求嚴格不等。交換同權邊可以保持最優總權重;最優樹不一定唯一。
快速檢查
(一個圖有四個頂點,掃描結束時選了兩條邊。它能有生成樹嗎?為甚麼?)
生成樹有多少條邊?連通的輸入上掃描會得到甚麼?
解答 · 答案
不能。所選邊構成森林;若輸入連通,掃描會產生有三條邊的生成樹,因此只有兩條邊證明輸入不連通。