最優樹問題(optimal spanning tree problem)是一類組合最佳化問題，設G=(V，E)是一個圖，V為節點集，E為邊集，對任何e∈E，它的權w(e)為已知，在G上，求一個支撐樹T使得W(T)=∑e∈Tw(e)為最優(即最大或最小)，這就是最優樹問題，或具體地，最大樹問題或最小樹問題。求G上的最小支撐樹有克魯斯卡爾算法，其要旨是：首先，選取權最小的一條邊;然後，對於所有未被選取的邊，在那些與已選取的邊不產生圈的邊中取一個權最小的；如此下去，一直到不能進行為止，從而，這樣選出來的所有邊構成G的一個支撐樹，並且其上邊的權之總和為最小，它是一種典型的貪婪算法，若將最優樹問題中的支撐樹改為G的連通的支撐子圖，則這時被稱為最優連結問題，最小連結問題與最小樹問題是等價的。
基本介紹
- 中文名：最優樹問題
- 外文名：optimal spanning tree problem
- 所屬學科：數學
- 所屬問題：組合學(圖與超圖)
- 簡介：一類組合最佳化問題
基本介紹,最優樹問題的解法,
基本介紹
假設要在n個城市
之間建一個公路網，使得這n個城市互通公路，已知連線城市
和
的公路造價為
，要求設計一個總造價最小的公路網，這就是所謂連線問題。
從圖論角度看，連線問題可敘述為：在一個賦權連通圖G中，找出一個具有最小權的連通子圖，顯然，它必是G的一個生成樹T，且權最小．我們稱這種樹為最優樹。
最優樹問題的解法
對於有限賦權圖，由於它的生成樹數目有限，因此，總可以通過逐個比較最終找到一個最優樹(可能不唯一)，這說明最優樹是存在的，但當頂點和邊的數目較大時，這種方法顯然是不切實際的。Kruskal於1956年提出了求最優樹的有效算法，其步驟如下(設G的各邊權非負且無環)：
(1)選擇
，使權
最小；
(2)假設已選好
，則從
中選取
滿足：
①
無迴路；
②
是滿足①的儘可能小的權；
(3)重複(2)直到不存在滿足①的邊。
例如，圖1給出了利用上述算法求最優樹的過程，其中，粗邊就是算法所選定的邊。
定理1 設
是一個圖，於是，下列說法相互等價：
(1)G是樹；
(2)G連通且
；
(3)G無迴路且；
(4)G無迴路，但對任意
，若
，則
中恰有一條迴路；
(5)G是連通，但對任意
不連通。
定理2 對賦權G(P，q)，用Kruskal算法得到G的子圖T*必是最優樹。
證明：首先，由Kruskal算法容易證明T*是G的生成樹。
設
