用戶:Ivyxjc/Sandbox4

最小生成樹是一副連通加權無向圖中一棵權值最小的生成樹。

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

相關性質

存在個數

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

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

如果圖有具有相同權值的邊，那麼最小生成樹的邊的權值組成的權值集合是唯一的^[1]。

證明（圖的每一條邊的權值皆不相同）：

假設有兩個最小生成樹 $A$ 和 $B$ 。
由於 $A$ 和 $B$ 是兩個不同的最小生成樹，那麼 $A$ 中總會有一個或者多個邊並不在 $B$ 中，設這些邊中權值最低的那一條邊為 $e_{k}$ 。
由於 $B$ 是一個最小生成樹，由樹的一些定理¹可知 $e_{k}\cup B$ 必然包含一個環 $C$ 。
因為環 $C$ 中存在一條邊 $e_{m}$ 它的權值比 $e_{k}$ 要大^{證明見註釋}。
因此用 $e_{k}$ 替代 $e_{m}$ ， $B$ 成為了一個擁有更小權值的生成樹。這和 $B$ 是最小生成樹相矛盾，所以不可能存在兩個最小生成樹。

邊的權值之和最低的子圖

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

環定理

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

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

切分定理

在一幅連通加權無向圖中，給定任意的切分（英語：Cut (graph theory)），它的橫切邊中權值最小的邊必然屬於圖的最小生成樹。

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

最小權值邊

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

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

註釋

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

^2 ：設最小生成樹 $A$ 的邊的權值集合按從小到大順序排列為 $\left\{e_{1},e_{2},e_{3},\cdots ,e_{n}\right\}$ ， $B$ 的為 $\left\{f_{1},f_{2},f_{3},\cdots ,f_{n}\right\}$ 。因為 $e_{k}$ 為在 $A$ 但是不在 $B$ 的邊中權值最小的邊，所以 $A$ 中權值小於 $e_{k}$ 的邊也在 $B$ 中。所以子圖 $A1$ $\left\{e_{1},e_{2},e_{3},\cdots ,e_{k-1},e_{k}\right\}$ == $B1$ $\left\{f_{1},f_{2},f_{3},\cdots ,f_{k-1},f_{k}\right\}$ 。因為 $A1$ 沒有環，所以 $B1$ 且 $B1$ 的子圖都沒有環，那麼組成環 $C$ 的邊中必有邊來自 $\left\{f_{k+1},f_{k+2},f_{k+3},\cdots ,f_{i}\right\}(i>k)$ 之中。

參考

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

External links

[1] Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

[2] Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民郵電出版社. 2012年10月. 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, doi:10.1007/BF01386390 .

[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 （Czech） .

[6] Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民郵電出版社. 2012年10月. 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] 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 .

[12] Eppstein, David, Finding the k smallest spanning trees, BIT, 1992, 32 (2): 237–248, MR 1172188, doi:10.1007/BF01994879 .

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

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

[15] McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan. Non-projective dependency parsing using spanning tree algorithms (PDF). Proc. HLT/EMNLP. 2005.

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

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

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

[16]

[17]

[18]

用戶:Ivyxjc/Sandbox4

相關性質

存在個數

邊的權值之和最低的子圖

環定理

切分定理

最小權值邊

相關算法

歷史簡介

Borůvka算法

Prim算法

Kruskal算法

更快的算法

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

相關問題

註釋

參考

Additional reading

External links