用户: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