最優樹問題

最優樹問題(optimal spanning tree problem)是一類組合最佳化問題，設G=(V，E)是一個圖，V為節點集，E為邊集，對任何e∈E，它的權w(e)為已知，在G上，求一個支撐樹T使得W(T)=∑e∈Tw(e)為最優(即最大或最小)，這就是最優樹問題，或具體地，最大樹問題或最小樹問題。求G上的最小支撐樹有克魯斯卡爾算法，其要旨是：首先，選取權最小的一條邊;然後，對於所有未被選取的邊，在那些與已選取的邊不產生圈的邊中取一個權最小的；如此下去，一直到不能進行為止，從而，這樣選出來的所有邊構成G的一個支撐樹，並且其上邊的權之總和為最小，它是一種典型的貪婪算法，若將最優樹問題中的支撐樹改為G的連通的支撐子圖，則這時被稱為最優連結問題，最小連結問題與最小樹問題是等價的 。

基本介紹

最優樹問題

最優樹問題

最優樹問題

最優樹問題

假設要在n個城市 之間建一個公路網，使得這n個城市互通公路，已知連線城市 和 的公路造價為 ，要求設計一個總造價最小的公路網，這就是所謂連線問題。

從圖論角度看， 連線問題可敘述為：在一個賦權連通圖G中，找出一個具有最小權的連通子圖，顯然，它必是G的一個生成樹T，且權最小．我們稱這種樹為 最優樹 。

最優樹問題的解法

對於有限賦權圖，由於它的生成樹數目有限，因此，總可以通過逐個比較最終找到一個最優樹(可能不唯一)，這說明最優樹是存在的，但當頂點和邊的數目較大時，這種方法顯然是不切實際的。Kruskal於1956年提出了求最優樹的有效算法，其步驟如下(設G的各邊權非負且無環)：

最優樹問題

最優樹問題

(1)選擇 ，使權 最小；

最優樹問題

最優樹問題

最優樹問題

(2)假設已選好 ，則從 中選取 滿足：

最優樹問題

① 無迴路；

最優樹問題

② 是滿足①的儘可能小的權；

(3)重複(2)直到不存在滿足①的邊。

例如，圖1給出了利用上述算法求最優樹的過程，其中，粗邊就是算法所選定的邊 。

圖1（a）	圖1（b）	圖1（c）
圖1（d）	圖1（e）	圖1（f）

最優樹問題

定理1 設是一個圖，於是，下列說法相互等價：

(1)G是樹；

最優樹問題

(2)G連通且；

最優樹問題

(3)G無迴路且；

最優樹問題

最優樹問題

最優樹問題

(4)G無迴路，但對任意，若，則中恰有一條迴路；

最優樹問題

(5)G是連通，但對任意不連通。

最優樹問題

定理2 對賦權G(P，q)，用Kruskal算法得到G的子圖T*必是最優樹。

證明：首先，由Kruskal算法容易證明T*是G的生成樹。

設

最優樹問題

對G的每個不同於T*的生成樹T，令

最優樹問題

最優樹問題

最優樹問題

最優樹問題

最優樹問題

最優樹問題

最優樹問題

最優樹問題

最優樹問題

最優樹問題

最優樹問題

最優樹問題

假設T*不是最優樹，令T是使取最大值的最優樹，設，於是，，但。由定理1(4)知，中含唯一的迴路C。令是C中滿足的邊，作，於是是一個有條邊的連通圖，由定理1(2)知，是G的生成樹。顯然

最優樹問題

最優樹問題

最優樹問題

最優樹問題

最優樹問題

最優樹問題

而由算法知，，從而，這說明也是G的最優樹，但，，此與T的選取矛盾，故是最優樹。