假設一個城鎮要用電纜連接多個地點:每條電纜都有安裝成本,而任意兩點都要能夠直接或經其他地點互通。若安裝成本非負,刪去環上的邊仍保持連通且不增加成本,故可在最便宜的連通網絡中選一棵生成樹。目標是整個網絡的總成本最小,這與只找兩點之間的最短路不同。
模型與交換原理
令 為有限、連通、無向圖,至少有一個頂點;每條邊 有實數權重 。生成樹是包含所有頂點且連通、無環的子圖。它有 條邊,任意兩點之間恰有一條路。權重總和最小的生成樹稱為最小生成樹(MST)。有限連通圖至少有一棵生成樹,邊集的選擇又只有有限個,因此最小值存在。權重不必互異,也不必為正。
對非空真子集 ,割 是一端在 、另一端在外的所有邊。若森林 沒有邊橫跨此割,稱此割尊重 。割的輕邊是橫跨該割、權重最小的邊;可以有多條並列輕邊。
定理 25.1.1
(安全邊定理)
若森林 包含於某棵 MST 內,而割尊重 ,則任取該割的一條輕邊 ,都存在一棵 MST 包含 。
證明。 取包含 的 MST 。若 已在 ,結論成立。否則把 加到 ,便與 中連接其兩端的唯一路徑組成一個環。該路徑必定橫跨此割;取其中一條跨割邊 。由於割尊重 ,故 。從環移去 得到生成樹 ,它包含 。輕邊性質給出 ,所以 。由 的最小性,必為等號, 也是 MST。
證明透視
交換步究竟保證甚麼?
移去的邊橫跨尊重 的割,所以不會破壞已選的邊。結論是存在「某棵」包含新邊的最優樹;權重並列時,它並不斷言每棵最優樹都包含新邊。若 是割上唯一最輕邊,任何不含 的生成樹經同樣交換都會嚴格減低成本,因此每棵 MST 必含 。
環規則方向相反:若一條邊比同一環上的其他每條邊都嚴格重,則它不屬於任何 MST。理由是從含它的樹移去該邊後,環上另一條邊必能重新連接兩部分,而且成本較低。若只是並列最重,便不能排除它出現在所有 MST:三角形三邊權重均為 1 時,每條邊都出現在其中兩棵 MST。
Kruskal 算法
把所有邊按權重非遞減排列。由空森林開始,依次檢查每條邊:若兩端處於目前森林的不同連通分量,就加入;否則跳過。選滿 條邊即可停止,也可以掃描完整個清單。只有一個頂點時,空樹就是答案。
為甚麼每次加入都安全?加入前取其中一端所在的分量為 。目前選中的邊不橫跨此割,而新邊橫跨它。若有較輕的跨割邊,它早已被檢查;它當時不可能因兩端已連通而被跳過,因為分量只會合併,這會令它現在也不跨割。因此新邊是輕邊。安全邊定理保持「已選森林包含於某棵 MST」的不變量。掃描結束時不可能仍有兩個分量:原圖連通,必有一條邊橫跨兩個現存分量,而它被檢查時兩端亦不可能已連通。故結果是生成樹,並由不變量知它是 MST。權重相同的邊可任意排序。
反例模式
任意割上的輕邊未必安全
錯誤說法:任何割上的輕邊都可加入一個包含於 MST 的森林。取三角形 ,各邊權重均為 ,並取 MST 森林 。割 不尊重 ,因為 橫跨它。其中 是輕邊,但 是整個三角形,即一個環,所以沒有生成樹包含它。修補就是定理的假設:割必須尊重 ;Kruskal 算法取 為目前的一個分量,正好保證這一點。
實作可用不相交集合數據結構檢查及合併分量;通常排序需要 次比較,其餘集合操作接近線性。正確性不依賴特定實作,也不依賴平手時的處理規則。
例題 25.1.2
(四個地點的選邊與證明)
設邊為 、、、、、。算法先選 ,跳過兩端已由 連接的 ,再選 ,得到總權重 。
依次用 、、 證明三次選擇:各割尊重之前的邊,而所選邊分別是割上輕邊。 是環 上唯一最重的邊,故不屬於任何 MST; 和 也分別由環 和 排除。
易混淆之處
從指定根出發的最短路樹使每個根到頂點的路長最短;MST 最小化的是已安裝邊的總權重。兩者可以不同: 時,從 出發的最短路樹選 ,總重 4;選 加其中一條權重 2 的邊,總重只有 3。反過來,MST 也未必保留從根出發的最短路。負權重不影響上述樹問題的比較與證明;但若允許任意連通子圖,額外的負權邊可降低總成本,例如全為負權的三角形,三條邊一起使用比任何生成樹便宜。若圖不連通,則不存在覆蓋全圖的生成樹;Kruskal 得到各連通分量的最小生成森林。
練習
快速檢查
(邊為 。依 的次序檢查三角形邊,執行算法,另找一棵 MST,並解釋 為何不在任何 MST。)
解答 · 答案
選 ,跳過 ,再選 ,總重 4。用 替換 得到另一棵同重生成樹。 在環 上嚴格最重,故被環規則排除。
快速檢查
(證明所有邊權互異時 MST 唯一,指出何處需要嚴格不等式。)
解答 · 答案
假設不同的 MST 存在,取兩者對稱差中最輕的邊 。刪除 把 分為兩部分; 中連接 兩端的路徑必有跨這兩部分的邊 。因權重互異及 的選法,。在 用 換走 得到嚴格更便宜的生成樹,矛盾。
快速檢查
(舉例反駁「割上每條輕邊都屬於每棵 MST」,再給出正確陳述。)
解答 · 答案
三邊權重均為 1 的三角形,每條邊都是某個割的輕邊,但也有一棵 MST 不包含該邊。正確說法:輕邊屬於某棵 MST;若它是割上唯一輕邊,則屬於每棵 MST。
快速檢查
(圖有兩個分量: 的邊為 , 的邊為 。執行算法並說明結果。)
解答 · 答案
選 ,跳過 ,總重 。這是最小生成森林:每個分量內的樹分別最優。兩分量之間沒有邊,因此整個圖沒有生成樹。