最小生成樹

最小生成樹的簡稱，是一副連通加權無向圖中一棵權值最小的生成樹。在一給定的無向圖 formula_1 中，formula_2 代表連線頂點 u 與頂點 v 的邊且 (V, T) 為樹，使得：formula_6的 w(T) 最小，則此 T 為 G 的最小生成樹。一個連通圖可能有多個生成樹。當圖中的邊具有權值時，總會有一個生成樹的邊的權值之和小於或者等於其它生成樹的邊的權值之和。廣義上而言，對於非連通無向圖來說，它的每一連通分量同樣有最小生成樹，它們的並被稱為最小生成森林。以有線電視電纜的架設為例，若只能沿著街道佈線，則以街道為邊，而路口為頂點，其中必然有一最小生成樹能使佈線成本最低。相關性質.存在個數.最小生成樹在一些情況下可能會有多個。例如，當圖的每一條邊的權值都相同時，該圖的所有生成樹都是最小生成樹。唯一性.如果圖的每一條邊的權值都互不相同，那麼最小生成樹將只有一個。這一定理同樣適用於最小生成森林。證明：假設圖formula_7為每條邊權值互不相同的連通圖，且有兩個不同的最小生成樹formula_8和formula_9。則formula_8中必然存在一些在formula_9中並不存在的邊，取其中一條這樣的邊formula_12。因為formula_9是最小生成樹，所以若往formula_9中新增邊formula_12，則將會出現環路。同時可知，如果從formula_8中刪除邊formula_12，則formula_8將分為互不連通的兩個連通分量。因為formula_21，所以formula_9中必然有其他的邊連線這兩個連通分量。且將formula_12加入formula_9後形成的環路中，除了formula_12外至少有另一條連線formula_8中刪除formula_12後的這兩個連通分量的邊。取其中一條這樣的邊，記作formula_28。此時若將formula_28加入formula_8，則可連線從formula_8中刪除formula_12後得到的兩個連通分量，並形成一棵不同的生成樹。因為formula_7中所有邊的權值互不相同，所以關於formula_12和formula_28的權重大小關係，可能有以下兩種情況之一：綜上，若formula_7各邊權重互不相等，則不可能存在兩棵互不相同的最小生成樹。即formula_7的最小生成樹是唯一的。邊的權值之和最低的子圖.如果圖的邊的權值都為正數，那麼最小生成樹就是該圖的所有包含所有頂點的子圖中權值最低的連通子圖。環定理.對於連通圖中的任意一個環formula_48：如果formula_48中有邊formula_50的權值大於該環中任意一個其它的邊的權值，那麼這個邊不會是最小生成樹中的邊證明：假設formula_50屬於最小生成樹formula_52，那麼將formula_50刪去將會使得formula_52變為兩個樹。因為環formula_48必然還存在另一橫切邊ｆ可以連線兩個子樹形成生成樹formula_56，且由於formula_57＜formula_50，生成樹formula_56權值更小，與formula_52是最小生成樹矛盾。割定理.在一幅連通加權無向圖中，給定任意的，如有一條割邊的權值嚴格小於所有其他割邊，則這條邊必然屬於圖的最小生成樹。證明：令formula_50為權重最小的割邊，假設formula_8為圖的最小生成樹，且formula_8不包含formula_50。那麼如果將formula_50加入formula_8，得到的圖必然含有一條經過formula_50的環，且這個環也含有另一條割邊--設為formula_68，formula_68的權重必然大於formula_50，那麼用formula_50替換formula_68可以形成一個權值小於formula_8的生成樹，與formula_8為最小生成樹矛盾。所以假設不成立，因此formula_8必然包含formula_50。。最小權值邊.如果圖的具有最小權值的邊只有一條，那麼這條邊包含在任意一個最小生成樹中。證明：假設該邊formula_50沒有在最小生成樹formula_8中，那麼將formula_50加入formula_8中會形成環，用formula_50替換環中的任意一條權值更大的邊，將會形成權值更小的生成樹，與題設矛盾。相關演算法.歷史簡介.計算稠密圖的最小生成樹最早是由羅伯特·C·普里姆在1957年發明的，即普里姆演算法。之後艾茲赫爾·戴克斯特拉也獨自發明瞭它。但該演算法的基本思想是由於1930年發明的。所以該演算法有時候也被稱為亞爾尼克演算法或者普里姆-亞爾尼克演算法。20世紀70年代，優先佇列發明之後很快被用在了尋找稀疏圖中的最小生成樹上。1984年，邁克爾·弗裡德曼和羅伯特·塔揚發明了斐波那契堆，普里姆演算法所需要的執行時間在理論上由formula_82提升到了formula_83。約瑟夫·克魯斯卡爾在1956年發表了他的演算法，在他的論文中提到了普里姆演算法的一個變種，而在20世紀20年代的論文中就已經提到了該變種。M.Sollin在1961年重新發現了該演算法，該演算法後成為實現較好漸進效能的最小生成樹演算法和並行最小生成樹演算法的基礎。以下各演算法介紹中，formula_84表示圖的邊數，formula_85表示圖的頂點數。布盧瓦卡演算法.第一個用於尋找最小生成樹的演算法由捷克科學家提出，即。普里姆演算法.普里姆演算法的每一步都會為一棵生長中的樹新增一條邊，該樹最開始只有一個頂點，然後會新增formula_86個邊。每次總是新增生長中的樹和樹中除該生長的樹以外的部分形成的切分的具有最小權值的橫切邊。普里姆演算法的時間複雜度為formula_87。克魯斯克爾演算法.按照邊的權重順序將邊加入生成樹中，但是若加入該邊會與生成樹形成環則不加入該邊。直到樹中含有formula_88條邊為止。這些邊組成的就是該圖的最小生成樹。克魯斯克爾演算法的時間複雜度為formula_82。更快的演算法.一些研究者希望可以找出更為高效的演算法，在這方面也有了一定的成果。最快的非隨機比較演算法是由提出的。該演算法依賴於這樣一個類似於優先順序佇列的資料結構 。該演算法的時間複雜度為formula_90。formula_91就是阿克曼函式反函式，formula_91的增長速度非常慢，對於一般的數值來說，其值很難超過5，所以該演算法的複雜度可以近似看成是線性時間。線性時間的最小生成樹演算法.目前，既不能證明不存在能線上性時間內得到任意圖的最小生成樹的演算法，也未能發明能夠線上性時間內計算稀疏圖的最小生成樹的演算法。相關問題.：圖中包含k個頂點的所有子圖的所有最小生成樹中權值最小的生成樹。是一個用歐幾里得距離來表示權值的連通加權圖的最小生成樹。是一個用曼哈頓距離來表示權值的連通加權圖的最小生成樹。是一棵樹且其每個節點的子樹的容量都不大於formula_48。解決該問題是NP困難的。但是伊薩·威廉姆斯和夏爾馬以及提出了可以在接近多項式時間內解決該問題的啟發式。是一棵樹，其每一個頂點連線的頂點數都不超過d。對一些特定的d值，該問題類似於旅行推銷員問題。該問題也是NP困難的。對有向圖來說，其與最小生成樹類似的圖處理問題叫做最小樹形圖問題。最大生成樹是一棵比其它所有生成樹都要大或者相等的生成樹。其解決方法類似於最小生成樹演算法。求解最大生成樹的演算法在自然語言處理以及條件隨機場這些問題上起到很大的作用。動態最小生成樹是在已經計算完一個圖的最小生成樹後動態改變一些邊的取值或刪除/新增一些點或者邊，求解新圖的最小生成樹。註釋.^1 ：用一條邊連結樹中的任意兩個頂點都會產生一個新的環。