本页使用了标题或全文手工转换

最小生成树

维基百科,自由的百科全书
跳转至: 导航搜索
一个平面图和它的最小生成树。在该图中,边的长度正比于权值A。

最小生成树是一副连通加权无向图中一棵权值最小的生成树英语Spanning tree

在一給定的無向圖 G = (V, E) 中,(u, v) 代表連接頂點 u 與頂點 v 的邊(即 ),而 w(u, v) 代表此的權重,若存在 T 為 E 的子集(即 )且為無循環圖,使得

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

最小生成樹其實是最小權重生成樹的簡稱。

一个连通图可能有多个生成树。当图中的边具有权值时,总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言,对于非连通无向图来说,它的每一连通分量同样有最小生成树。

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

简单点说有几个城市你要设计一个路线,这个路线能走完所有的这几个城市,而且路程最短,这个路线就是最小生成树的含义。

相关性质[编辑]

存在个数[编辑]

这张图表明一个图中可能有多个最小生成树

最小生成树在一些情况下可能会有多个。例如,当图的每一条边的权值都相同是,该图的所有生成树都是最小生成树。

如果图的每一条边的权值都互不相同,那么最小生成树将只有一个[1]。这一定理同样适用于最小生成树森林。

证明(图的每一条边的权值皆不相同):

  1. 假设有两个最小生成树
  2. 由于是两个不同的最小生成树,那么中总会有一个或者多个边并不在中,设这些边中权值最低的那一条边为
  3. 由于是一个最小生成树,由树的一些定理1可知必然包含一个环
  4. 因为环中存在一条边它的权值比要大证明见注释
  5. 因此用替代成为了一个拥有更小权值的生成树。这和是最小生成树相矛盾,所以不可能存在两个最小生成树。

边的权值之和最低的子图[编辑]

如果图的边的权值都为正数,那么最小生成树就是该图的所有包含所有顶点的子图中权值最低的子图。

环定理[编辑]

对于连通图中的任意一个环:如果中有边的权值大于该环中任意一个其它的边的权值,那么这个边不会是最小生成树中的边

证明:
假设属于最小生成树,那么将删去将会使得变为两个树。因为环必然还存在另一横切边f可以连接两个子树形成生成树,且由于,生成树权值更小,与是最小生成树矛盾。

切分定理[编辑]

此图展示了最小生成树的切分定理。是该图唯一的最小生成树,如果,那么,然后有3条横切边BC,EC,EF可以将这两个切分相连。其中边是其中权值最小的边,所以是最小生成树的一部分。

在一幅连通加权无向图中,给定任意的切分英语Cut (graph theory),它的横切边中权值最小的边必然属于图的最小生成树。

证明:
为权重最小的横切边,为图的最小生成树。假设不包含,那么如果将加入,得到的图必然含有一条经过的环,且这个环只是含有一条横切边--设为的权重必然大于,那么用替换可以形成一个权值小于T的生成树,与为最小生成树矛盾。所以假设不成立[2]

最小权值边[编辑]

如果图的具有最小权值的边只有一条,那么这条边包含在任意一个最小生成树中。

证明:
假设该边没有在最小生成树中,那么将加入中会形成环,用替换环的另一对应的横切边,将会形成权值更小的生成树,与题设矛盾。

相关算法[编辑]

历史简介[编辑]

计算稠密图的最小生成树最早是由罗伯特·普里姆英语Robert C. Prim在1957年发明的[3],即Prim算法。之后艾兹赫尔·戴克斯特拉也独自发明了它[4]。但该算法的基本思想是由沃伊捷赫·亚尔尼克英语Vojtěch Jarník于1930年发明的[5]。所以该算法有时候也被称为Jarník算法或者Prim-Jarník算法。20世纪70年代,优先队列发明之后很快被用在了寻找稀疏图中的最小生成树上。1984年,迈克尔·弗里德曼罗伯特·塔扬发明了斐波那契堆,Prim算法所需要的运行时间在理论上由提升到了约瑟夫·克鲁斯卡尔英语Joseph Kruskal在1956年发表了他的算法,在他的论文中提到了Prim算法的一个变种,而奥塔卡尔·布卢瓦卡英语Otakar Borůvka在20世纪20年代的论文中就已经提到了该变种。M.Sollin在1961年重新发现了该算法,该算法后成为实现较好渐进性能的最小生成树算法和并行最小生成树算法的基础[6]

以下各算法介绍中,表示图的边数,表示图的顶点数。 

Borůvka算法[编辑]

第一个用于寻找最小生成树的算法由捷克科学家奥塔卡尔·布卢瓦卡英语Otakar Borůvka提出,即Borůvka算法英语Borůvka's algorithm

Prim算法[编辑]

Prim算法的每一步都会为一棵生长中的树添加一条边,该树最开始只有一个顶点,然后会添加个边。每次总是添加生长中的树和树中除该生长的树以外的部分形成的切分的具有最小权值的横切边。

Prim算法的时间复杂度为

Kruskal算法[编辑]

按照边的权重顺序(从小到大)将边加入生成树中,但是若加入该边会与生成树形成环则不加入该边。直到树中含有条边为止。这些边组成的就是该图的最小生成树。

Kruskal算法的时间复杂度为

更快的算法[编辑]

一些研究者希望可以找出更为高效的算法,在这方面也有了一定的成果。 Karger, Klein & Tarjan (1995)针对边的权值可以成对比较的特殊模型提出了一个基于Borůvka算法和翻转删除算法的可以在线性时间内解决最小生成树的算法[7][8]

最快的非随机比较算法是由伯纳德·沙泽勒英语Bernard Chazelle提出的。该算法依赖于soft heap英语soft heap这样一个类似于优先级队列数据结构[9][10] 。该算法的时间复杂度为就是阿克曼函数反函数的增长速度非常慢,对于一般的数值来说,其值很难超过5,所以该算法的复杂度可以近似看成是线性时间。

线性时间的最小生成树算法[编辑]

目前,既不能证明不存在能在线性时间内得到任意图的最小生成树的算法,也未能发明能够在线性时间内计算稀疏图的最小生成树的算法。

相关问题[编辑]

k-最小生成树英语k-minimum spanning tree:图中包含k个顶点的所有子图的所有最小生成树中权值最小的生成树。

欧几里得最小生成树英语Euclidean minimum spanning tree是一个用欧几里得距离来表示权值的连通加权图的最小生成树。

方格线最小生成树英语rectilinear minimum spanning tree是一个用曼哈顿距离来表示权值的连通加权图的最小生成树。

容量最小生成树英语capacitated minimum spanning tree是一棵树且其每个节点的子树的容量都不大于。解决该问题是NP困难[11]。但是伊萨·威廉姆斯夏尔马以及提出了可以在接近多项式时间内解决该问题的启发式

度受限最小生成树英语degree-constrained spanning tree是一棵树,其每一个顶点连接的顶点数都不超过d。对一些特定的d值,该问题类似于旅行推销员问题。该问题也是NP困难的。

对有向图来说,其与最小生成树类似的图处理问题叫做最小树形问题

最大生成树是一棵比其它所有生成树都要大或者相等的生成树。其解决方法类似于最小生成树算法。求解最大生成树的算法在自然语言处理以及条件随机场这些问题上起到很大的作用[12]

动态最小生成树是在已经计算完一个图的最小生成树后动态改变一些边的取值或删除/添加一些点或者边,求解新图的最小生成树[13][14][15]

注释[编辑]

^1 :用一条边链接树中的任意两个顶点都会产生一个新的环。

^2 :设最小生成树的边的权值集合按从小到大顺序排列为的为。因为为在但是不在的边中权值最小的边,所以中权值小于的边也在中。所以子图==。因为没有环,所以的子图都没有环,那么组成环的边中必有边来自之中。

参考[编辑]

  1. ^ Minimum Spanning Trees. princeton.edu. 2015-09-13 [2016-02-08] (英文). 
  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, doi:10.1145/201019.201022, MR 1409738 
  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 .
  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, doi:10.1145/355541.355562, MR 1866456 .
  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, doi:10.1145/355541.355554, MR 1866455 .
  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. 
  13. ^ Spira, P. M.; Pan, A., On finding and updating spanning trees and shortest paths, SIAM Journal on Computing, 1975, 4 (3): 375–380, doi:10.1137/0204032, MR 0378466 .
  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, doi:10.1145/502090.502095, MR 2144928 .
  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 .

参考文献[编辑]

外部链接[编辑]