最小生成樹

最小生成樹（英語：Minimum spanning tree，簡稱MST）是最小權重生成樹（英語：Minimum weight spanning tree）的簡稱，是一個連通加權無向圖中一棵權值最小的生成樹。

在一給定的無向圖 $G=(V,E)$ 中， $(u,v)$ 代表連接頂點 u 與頂點 v 的邊（即 $(u,v)\in E$ ），而 $w(u,v)$ 代表此邊的權重，若存在 T 為 E 的子集（即 $T\subseteq E$ ）且 (V, T) 為樹，使得：

w(T)=\sum _{(u,v)\in T}w(u,v)

的 w(T) 最小，則此 T 為 G 的最小生成樹。

一個連通圖可能有多個生成樹。當圖中的邊具有權值時，總會有一個生成樹的邊的權值之和小於或者等於其它生成樹的邊的權值之和。廣義上而言，對於非連通無向圖來說，它的每一連通分量同樣有最小生成樹，它們的並被稱為最小生成森林。

以有線電視電纜的架設為例，若只能沿着街道佈線，則以街道為邊，而路口為頂點，其中必然有一最小生成樹能使佈線成本最低。

相關性質

存在個數

這張圖表明一個圖中可能有多個最小生成樹

最小生成樹在一些情況下可能會有多個。例如，當圖的每一條邊的權值都相同時，該圖的所有生成樹都是最小生成樹。

唯一性

如果圖的每一條邊的權值都互不相同，那麼最小生成樹將只有一個^[1]。這一定理同樣適用於最小生成森林。

證明：

假設圖 $G$ 為每條邊權值互不相同的連通圖，且有兩個不同的最小生成樹 $T$ 和 $T'$ 。
則 $T$ 中必然存在一些在 $T'$ 中並不存在的邊，取其中一條這樣的邊 $e_{0}$ 。
因為 $T'$ 是最小生成樹，所以若往 $T'$ 中添加邊 $e_{0}$ ，則將會出現環路。（因為有 $m$ 個頂點的樹有且僅有 $m-1$ 條邊）
同時可知，如果從 $T$ 中刪除邊 $e_{0}$ ，則 $T$ 將分為互不連通的兩個連通分量。因為 $e_{0}\notin T'$ ，所以 $T'$ 中必然有其他的邊連接這兩個連通分量。且將 $e_{0}$ 加入 $T'$ 後形成的環路中，除了 $e_{0}$ 外至少有另一條連接 $T$ 中刪除 $e_{0}$ 後的這兩個連通分量的邊。取其中一條這樣的邊，記作 ${e_{0}}'$ 。此時若將 ${e_{0}}'$ 加入 $T$ ，則可連接從 $T$ 中刪除 $e_{0}$ 後得到的兩個連通分量，並形成一棵不同的生成樹。
因為 $G$ 中所有邊的權值互不相同，所以關於 $e_{0}$ 和 ${e_{0}}'$ 的權重大小關係，可能有以下兩種情況之一：

若 $e_{0}<{e_{0}}'$ ，則可從 $T'$ 中刪除 ${e_{0}}'$ 並加入 $e_{0}$ ，從而得到一棵總權值更小的生成樹。這和 $T'$ 是最小生成樹相矛盾。

若 $e_{0}>{e_{0}}'$ ，則可從 $T$ 中刪除 $e_{0}$ 並加入 ${e_{0}}'$ ，從而得到一棵總權值更小的生成樹。同樣，這和 $T$ 是最小生成樹相矛盾。

綜上，若 $G$ 各邊權重互不相等，則不可能存在兩棵互不相同的最小生成樹。即 $G$ 的最小生成樹是唯一的。

邊的權值之和最低的子圖

如果圖的邊的權值都為正數，那麼最小生成樹就是該圖的所有包含所有頂點的子圖中權值最低的連通子圖。

環定理

對於連通圖中的任意一個環 $C$ ：如果 $C$ 中有邊 $e$ 的權值大於該環中任意一個其它的邊的權值，那麼這個邊不會是最小生成樹中的邊

證明：
假設 $e$ 屬於最小生成樹 $T1$ ，那麼將 $e$ 刪去將會使得 $T1$ 變為兩個樹。因為環 $C$ 必然還存在另一橫切邊ｆ可以連接兩個子樹形成生成樹 $T2$ ，且由於 $f$ ＜ $e$ ，生成樹 $T2$ 權值更小，與 $T1$ 是最小生成樹矛盾。

割定理

此圖展示了最小生成樹的割定理。

T

是該圖唯一的最小生成樹，令

S=\left\{A,B,D,E\right\}

，則

V-S=\left\{C,F\right\}

，這樣就形成了一個割，其割集包含3條割邊，即BC，EC，EF，如果去除它們就可以將這兩個子圖完全斷開。在割集中，

e

是權值最小的邊，所以

S\cup \left\{e\right\}

是最小生成樹

T

的一部分。

在一幅連通加權無向圖中，給定任意的割，如有一條割邊的權值嚴格小於所有其他割邊，則這條邊必然屬於圖的最小生成樹。

證明：
令 $e$ 為權重最小的割邊，假設 $T$ 為圖的最小生成樹，且 $T$ 不包含 $e$ 。那麼如果將 $e$ 加入 $T$ ，得到的圖必然含有一條經過 $e$ 的環，且這個環也含有另一條割邊--設為 $e'$ ， $e'$ 的權重必然大於 $e$ ，那麼用 $e$ 替換 $e'$ 可以形成一個權值小於 $T$ 的生成樹，與 $T$ 為最小生成樹矛盾。所以假設不成立，因此 $T$ 必然包含 $e$ 。^[2]。

最小權值邊

如果圖的具有最小權值的邊只有一條，那麼這條邊包含在任意一個最小生成樹中。

證明：
假設該邊 $e$ 沒有在最小生成樹 $T$ 中，那麼將 $e$ 加入 $T$ 中會形成環，用 $e$ 替換環中的任意一條權值更大的邊，將會形成權值更小的生成樹，與題設矛盾。

註釋

^1 ：用一條邊連結樹中的任意兩個頂點都會產生一個新的環。

參考

^ Minimum Spanning Trees. princeton.edu. 2015-09-13 [2016-02-08]. （原始內容存檔於2020-09-27）（英語）.
^ Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民郵電出版社. 2012年10月 [2016-02-03]. 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 [2016-02-06], doi:10.1007/BF01386390, （原始內容存檔 (PDF)於2020-01-23） .
^ 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 [2016-02-06], （原始內容存檔於2017-06-17）（捷克語） .
^ Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民郵電出版社. 2012年10月 [2016-02-03]. 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 .
^ 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 [2016-02-06]. （原始內容存檔 (PDF)於2020-10-01）.
^ 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 .

參考文獻

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).

外部連結

[1] Minimum Spanning Trees. princeton.edu. 2015-09-13 [2016-02-08]. （原始內容存檔於2020-09-27）（英語）.

[2] Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民郵電出版社. 2012年10月 [2016-02-03]. ISBN 978-7-115-29380-0. ，p391--p392

[3] 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 .

[4] Dijkstra, E. W., A note on two problems in connexion with graphs (PDF), Numerische Mathematik, 1959, 1: 269–271 [2016-02-06], doi:10.1007/BF01386390, （原始內容存檔 (PDF)於2020-01-23） .

[5] 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 [2016-02-06], （原始內容存檔於2017-06-17）（捷克語） .

[6] Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民郵電出版社. 2012年10月 [2016-02-03]. ISBN 978-7-115-29380-0. ，p407--p408

[7] 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

[8] 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 .

[Chazelle2000-9] 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 .

[10] 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 .

[11] 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

[12] McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan. Non-projective dependency parsing using spanning tree algorithms (PDF). Proc. HLT/EMNLP. 2005 [2016-02-06]. （原始內容存檔 (PDF)於2020-10-01）.

[13] 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 .

[14] 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 .

[15] 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 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

最小生成樹

目次

相關性質

存在個數

唯一性

邊的權值之和最低的子圖

環定理

割定理

最小權值邊

相關演算法

歷史簡介

布盧瓦卡演算法

普里姆演算法

克魯斯克爾演算法

更快的演算法

線性時間的最小生成樹演算法

相關問題

註釋

參考

參考文獻

外部連結