最小生成树

最小生成树（英语：Minimum spanning tree，简称MST）是最小权重生成树（英语：Minimum weight spanning tree）的简称，是一个连通加权无向图中一棵权值最小的生成树。

在一给定的无向图 $G=(V,E)$ 中， $(u,v)$ 代表连接顶点 u 与顶点 v 的边（即 $(u,v)\in E$ ），而 $w(u,v)$ 代表此边的权重，若存在 T 为 E 的子集（即 $T\subseteq E$ ）且 (V, T) 为树，使得：

w(T)=\sum _{(u,v)\in T}w(u,v)

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

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

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

相关性质

存在个数

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

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

唯一性

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

证明：

假设图 $G$ 为每条边权值互不相同的连通图，且有两个不同的最小生成树 $T$ 和 $T'$ 。
则 $T$ 中必然存在一些在 $T'$ 中并不存在的边，取其中一条这样的边 $e_{0}$ 。
因为 $T'$ 是最小生成树，所以若往 $T'$ 中添加边 $e_{0}$ ，则将会出现环路。（因为有 $m$ 个顶点的树有且仅有 $m-1$ 条边）
同时可知，如果从 $T$ 中删除边 $e_{0}$ ，则 $T$ 将分为互不连通的两个连通分量。因为 $e_{0}\notin T'$ ，所以 $T'$ 中必然有其他的边连接这两个连通分量。且将 $e_{0}$ 加入 $T'$ 后形成的环路中，除了 $e_{0}$ 外至少有另一条连接 $T$ 中删除 $e_{0}$ 后的这两个连通分量的边。取其中一条这样的边，记作 ${e_{0}}'$ 。此时若将 ${e_{0}}'$ 加入 $T$ ，则可连接从 $T$ 中删除 $e_{0}$ 后得到的两个连通分量，并形成一棵不同的生成树。
因为 $G$ 中所有边的权值互不相同，所以关于 $e_{0}$ 和 ${e_{0}}'$ 的权重大小关系，可能有以下两种情况之一：

若 $e_{0}<{e_{0}}'$ ，则可从 $T'$ 中删除 ${e_{0}}'$ 并加入 $e_{0}$ ，从而得到一棵总权值更小的生成树。这和 $T'$ 是最小生成树相矛盾。

若 $e_{0}>{e_{0}}'$ ，则可从 $T$ 中删除 $e_{0}$ 并加入 ${e_{0}}'$ ，从而得到一棵总权值更小的生成树。同样，这和 $T$ 是最小生成树相矛盾。

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

边的权值之和最低的子图

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

环定理

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

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

割定理

此图展示了最小生成树的割定理。

T

是该图唯一的最小生成树，令

S=\left\{A,B,D,E\right\}

，则

V-S=\left\{C,F\right\}

，这样就形成了一个割，其割集包含3条割边，即BC，EC，EF，如果去除它们就可以将这两个子图完全断开。在割集中，

e

是权值最小的边，所以

S\cup \left\{e\right\}

是最小生成树

T

的一部分。

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

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

最小权值边

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

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

注释

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

参考

^ Minimum Spanning Trees. princeton.edu. 2015-09-13 [2016-02-08]. （原始内容存档于2020-09-27）（英语）.
^ Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民邮电出版社. 2012年10月 [2016-02-03]. 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 [2016-02-06], doi:10.1007/BF01386390, （原始内容存档 (PDF)于2020-01-23） .
^ 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）（捷克语） .
^ Robert Sedgewick, Kevin Wayne. 算法. 北京: 人民邮电出版社. 2012年10月 [2016-02-03]. 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 .
^ 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 [2016-02-06]. （原始内容存档 (PDF)于2020-10-01）.
^ 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 .

参考文献

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

外部链接

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

最小生成树

目录

相关性质

存在个数

唯一性

边的权值之和最低的子图

环定理

割定理

最小权值边

相关算法

历史简介

布卢瓦卡算法

普里姆算法

克鲁斯克尔算法

更快的算法

线性时间的最小生成树算法

相关问题

注释

参考

参考文献

外部链接