最小生成树

本页使用了标题或全文手工转换
维基百科,自由的百科全书
一个平面图和它的最小生成树。在该图中,边的长度正比于权值A。

最小生成树(英语:Minimum spanning tree,简称MST)是最小权重生成树(英语:Minimum weight spanning tree)的简称,是一副连通加权无向图中一棵权值最小的生成树

在一给定的无向图 中, 代表连接顶点 u 与顶点 v 的边(即 ),而 代表此的权重,若存在 T 为 E 的子集(即 )且 (V, T) 为,使得:

的 w(T) 最小,则此 T 为 G 的最小生成树。

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

以有线电视电缆的架设为例,若只能沿著街道布线,则以街道为边,而路口为顶点,其中必然有一最小生成树能使布线成本最低。

相关性质[编辑]

存在个数[编辑]

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

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

唯一性[编辑]

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

证明:

假设图为每条边权值互不相同的连通图,且有两个不同的最小生成树

中必然存在一些在中并不存在的边,取其中一条这样的边

因为是最小生成树,所以若往中添加边,则将会出现环路。(因为有个顶点的树有且仅有条边)

同时可知,如果从中删除边,则将分为互不连通的两个连通分量。因为,所以中必然有其他的边连接这两个连通分量。且将加入后形成的环路中,除了外至少有另一条连接中删除后的这两个连通分量的边。取其中一条这样的边,记作。此时若将加入,则可连接从中删除后得到的两个连通分量,并形成一棵不同的生成树。

因为中所有边的权值互不相同,所以关于的权重大小关系,可能有以下两种情况之一:

  1. ,则可从中删除并加入,从而得到一棵总权值更小的生成树。这和是最小生成树相矛盾。
  2. ,则可从中删除并加入,从而得到一棵总权值更小的生成树。同样,这和是最小生成树相矛盾。

综上,若各边权重互不相等,则不可能存在两棵互不相同的最小生成树。即的最小生成树是唯一的。

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

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

环定理[编辑]

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

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

割定理[编辑]

此图展示了最小生成树的割定理。是该图唯一的最小生成树,令,则,这样就形成了一个割,其割集包含3条割边,即BC,EC,EF,如果去除它们就可以将这两个子图完全断开。在割集中,是权值最小的边,所以是最小生成树的一部分。

在一幅连通加权无向图中,给定任意的,如有一条割边的权值严格小于所有其他割边,则这条边必然属于图的最小生成树。

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

最小权值边[编辑]

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

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

相关算法[编辑]

历史简介[编辑]

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

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

布卢瓦卡算法[编辑]

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

普里姆算法[编辑]

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

普里姆算法的时间复杂度为

克鲁斯克尔算法[编辑]

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

克鲁斯克尔算法的时间复杂度为

更快的算法[编辑]

一些研究者希望可以找出更为高效的算法,在这方面也有了一定的成果。 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 :用一条边链接树中的任意两个顶点都会产生一个新的环。

参考[编辑]

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

参考文献[编辑]

外部链接[编辑]