使用者:Ivyxjc/Sandbox4
一個連通圖可能有多個生成樹。當圖中的邊具有權值時，總會有一個生成樹的邊的權值之和小於或者等於其它生成樹的邊的權值之和。廣義上而言，對於非連通無向圖來說，它的每一連通分量同樣有最小生成樹。
相關性質
存在個數
最小生成樹在一些情況下可能會有多個。例如，當圖的每一條邊的權值都相同是，該圖的所有生成樹都是最小生成樹。
如果圖的每一條邊的權值都互不相同，那麼最小生成樹將只有一個。這一定理同樣適用於最小生成樹森林。
如果圖有具有相同權值的邊，那麼最小生成樹的邊的權值組成的權值集合是唯一的[1]。
證明（圖的每一條邊的權值皆不相同）：
- 假設有兩個最小生成樹 和 。
- 由於 和 是兩個不同的最小生成樹，那麼 中總會有一個或者多個邊並不在 中，設這些邊中權值最低的那一條邊為 。
- 由於 是一個最小生成樹，由樹的一些定理可知 必然包含一個環 。
- 因為環 中存在一條邊 它的權值比 要大。
- 因此用 替代 ， 成為了一個擁有更小權值的生成樹。這和 是最小生成樹相矛盾，所以不可能存在兩個最小生成樹。
邊的權值之和最低的子圖
如果圖的邊的權值都為正數，那麼最小生成樹就是該圖的所有包含所有頂點的子圖中權值最低的子圖。
環定理
對於連通圖中的任意一個環 ：如果 中有邊 的權值大於該環中任意一個其它的邊的權值，那麼這個邊不會是最小生成樹中的邊
證明：
假設 屬於最小生成樹 ，那麼將 刪去將會使得 變為兩個樹。因為環 必然還存在另一橫切邊ｆ可以連接兩個子樹形成生成樹 ，且由於 ＜ ，生成樹 權值更小，與 是最小生成樹矛盾。
切分定理
在一幅連通加權無向圖中，給定任意的切分，它的橫切邊中權值最小的邊必然屬於圖的最小生成樹。
證明：
令 為權重最小的橫切邊， 為圖的最小生成樹。假設 不包含 ，那麼如果將 加入 ，得到的圖必然含有一條經過 的環，且這個環只是含有一條橫切邊--設為 ， 的權重必然大於 ，那麼用 替換 可以形成一個權值小於Ｔ的生成樹，與 為最小生成樹矛盾。所以假設不成立[2]。
最小權值邊
如果圖的具有最小權值的邊只有一條，那麼這條邊包含在任意一個最小生成樹中。
證明：
假設該邊 沒有在最小生成樹 中，那麼將 加入 中會形成環，用 替換環的另一對應的橫切邊，將會形成權值更小的生成樹，與題設矛盾。
相關算法
歷史簡介
計算稠密圖的最小生成樹最早是由羅伯特·普里姆在1957年發明的[3]，即Prim算法。之後艾茲赫爾·戴克斯特拉也獨自發明了它[4]。但該算法的基本思想是由沃伊捷赫·亞爾尼克於1930年發明的[5]。所以該算法有時候也被稱為Jarník算法或者Prim-Jarník算法。20世紀70年代，優先隊列發明之後很快被用在了尋找稀疏圖中的最小生成樹上。1984年，邁克爾·弗里德曼和羅伯特·塔揚發明了斐波那契堆，Prim算法所需要的運行時間在理論上由 提升到了 。約瑟夫·克魯斯卡爾在1956年發表了他的算法，在他的論文中提到了Prim算法的一個變種，而奧塔卡爾·布盧瓦卡在20世紀20年代的論文中就已經提到了該變種。M.Sollin在1961年重新發現了該算法，該算法後成為實現較好漸進性能的最小生成樹算法和並行最小生成樹算法的基礎[6]。
以下各算法介紹中， 表示圖的邊數， 表示圖的頂點數。
Borůvka算法
第一個用於尋找最小生成樹的算法由捷克科學家奧塔卡爾·布盧瓦卡提出，即Borůvka算法。
Prim算法
Prim算法的每一步都會為一棵生長中的樹添加一條邊，該樹最開始只有一個頂點，然後會添加 個邊。每次總是添加生長中的樹和樹中除該生長的樹以外的部分形成的切分的具有最小權值的橫切邊。
Prim算法的時間複雜度為 。
Kruskal算法
按照邊的權重順序（從小到大）將邊加入生成樹中，但是若加入該邊會與生成樹形成環則不加入該邊。直到樹中含有 條邊為止。這些邊組成的就是該圖的最小生成樹。
Kruskal算法的時間複雜度為 。
更快的算法
一些研究者希望可以找出更為高效的算法，在這方面也有了一定的成果。 Karger, Klein & Tarjan (1995)針對邊的權值可以成對比較的特殊模型提出了一個基於Borůvka算法和翻轉刪除算法的可以在線性時間內解決最小生成樹的算法[7][8]。
最快的非隨機比較算法是由伯納德·沙澤勒提出的。該算法依賴於soft heap這樣一個類似於優先級隊列的數據結構[9][10] 。該算法的時間複雜度為 。 就是阿克曼函數反函數， 的增長速度非常慢，對於一般的數值來說，其值很難超過5，所以該算法的複雜度可以近似看成是線性時間。
線性時間的最小生成樹算法
目前，既不能證明不存在能在線性時間內得到任意圖的最小生成樹的算法，也未能發明能夠在線性時間內計算稀疏圖的最小生成樹的算法。
相關問題
k-最小生成樹：圖中包含k個頂點的所有子圖的所有最小生成樹中權值最小的生成樹。
k-最小生成樹的集合問題，在此集合外的生成樹不具有比 A set of k-smallest spanning trees is a subset of k spanning trees (out of all possible spanning trees) such that no spanning tree outside the subset has smaller weight.[11][12][13] (Note that this problem is unrelated to the k-minimum spanning tree.)
歐幾里得最小生成樹是一個用歐幾里得距離來表示權值的連通加權圖的最小生成樹。
方格線最小生成樹是一個用曼哈頓距離來表示權值的連通加權圖的最小生成樹。
容量最小生成樹是一棵樹且其每個節點的子樹的容量都不大於 。解決該問題是NP困難的[14]。但是伊薩·威廉姆斯和夏爾馬以及提出了可以在接近多項式時間內解決該問題的啟發式。
度受限最小生成樹是一棵樹，其每一個頂點連接的頂點數都不超過d。對一些特定的d值，該問題類似於旅行推銷員問題。該問題也是NP困難的。
對有向圖來說，其與最小生成樹類似的圖處理問題叫做最小樹形問題。
最大生成樹是一棵比其它所有生成樹都要大或者相等的生成樹。其解決方法類似於最小生成樹算法。求解最大生成樹的算法在自然語言處理以及條件隨機場這些問題上起到很大的作用[15]。 動態最小生成樹 是在已經計算完一個圖的最小生成樹後動態改變一些邊的取值或刪除/添加一些點或者邊，求解新圖的最小生成樹[16][17][18]。
注釋
^1 ：用一條邊鏈接樹中的任意兩個頂點都會產生一個新的環。
^2 ：設最小生成樹 的邊的權值集合按從小到大順序排列為 ， 的為 。因為 為在 但是不在 的邊中權值最小的邊，所以 中權值小於 的邊也在 中。所以子圖 == 。因為 沒有環，所以 且 的子圖都沒有環，那麼組成環 的邊中必有邊來自 之中。
參考
- ^ Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?
- ^ Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民郵電出版社. 2012年10月. ISBN 978-7-115-29380-0. ，p391--p392
- ^ Prim, R. C., Shortest connection networks And some generalizations, Bell System Technical Journal, November 1957, 36 (6): 1389–1401, doi:10.1002/j.1538-7305.1957.tb01515.x.
- ^ Dijkstra, E. W., A note on two problems in connexion with graphs (PDF), Numerische Mathematik, 1959, 1: 269–271, doi:10.1007/BF01386390.
- ^ Jarník, V., O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 1930, 6: 57–63 （Czech）.
- ^ Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民郵電出版社. 2012年10月. ISBN 978-7-115-29380-0. ，p407--p408
- ^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E., A randomized linear-time algorithm to find minimum spanning trees, Journal of the Association for Computing Machinery, 1995, 42 (2): 321–328, MR 1409738, doi:10.1145/201019.201022
- ^ Pettie, Seth; Ramachandran, Vijaya, Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms, Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02), San Francisco, California: 713–722, 2002.
- ^ Chazelle, Bernard, A minimum spanning tree algorithm with inverse-Ackermann type complexity, Journal of the Association for Computing Machinery, 2000, 47 (6): 1028–1047, MR 1866456, doi:10.1145/355541.355562.
- ^ Chazelle, Bernard, The soft heap: an approximate priority queue with optimal error rate, Journal of the Association for Computing Machinery, 2000, 47 (6): 1012–1027, MR 1866455, doi:10.1145/355541.355554.
- ^ Gabow, Harold N., Two algorithms for generating weighted spanning trees in order, SIAM Journal on Computing, 1977, 6 (1): 139–150, MR 0441784, doi:10.1137/0206011.
- ^ Eppstein, David, Finding the k smallest spanning trees, BIT, 1992, 32 (2): 237–248, MR 1172188, doi:10.1007/BF01994879.
- ^ Frederickson, Greg N., Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees, SIAM Journal on Computing, 1997, 26 (2): 484–538, MR 1438526, doi:10.1137/S0097539792226825.
- ^ Jothi, Raja; Raghavachari, Balaji, Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design, ACM Trans. Algorithms, 2005, 1 (2): 265–282, doi:10.1145/1103963.1103967
- ^ McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan. Non-projective dependency parsing using spanning tree algorithms (PDF). Proc. HLT/EMNLP. 2005.
- ^ Spira, P. M.; Pan, A., On finding and updating spanning trees and shortest paths, SIAM Journal on Computing, 1975, 4 (3): 375–380, MR 0378466, doi:10.1137/0204032.
- ^ Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel, Poly-logarithmic deterministic fully dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the Association for Computing Machinery, 2001, 48 (4): 723–760, MR 2144928, doi:10.1145/502090.502095.
- ^ Chin, F.; Houck, D., Algorithms for updating minimal spanning trees, Journal of Computer and System Sciences, 1978, 16 (3): 333–344, doi:10.1016/0022-0000(78)90022-3.
Additional reading
- Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) Jaroslav Nešetřil, Eva Milková, Helena Nesetrilová. (Section 7 gives his algorithm, which looks like a cross between Prim's and Kruskal's.)
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 23: Minimum Spanning Trees, pp. 561–579.
- Eisner, Jason (1997). State-of-the-art algorithms for minimum spanning trees: A tutorial discussion. Manuscript, University of Pennsylvania, April. 78 pp.
- Kromkowski, John David. "Still Unmelted after All These Years", in Annual Editions, Race and Ethnic Relations, 17/e (2009 McGraw Hill) (Using minimum spanning tree as method of demographic analysis of ethnic diversity across the United States).