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