最小生成树唯一吗

最小生成树是图论中的一个经典问题，它的解法有很多。我们可以使用Prim算法、Kruskal算法等来求解。但最小生成树是否唯一却一直是个争议点。本文将会从不同的角度介绍最小生成树是否唯一。

1.最小生成树的定义

最小生成树主要解决的问题是给定一个连通无向图，选出一些边使它们连通并且权值之和最小。 在任意连通子图中，若任意两个顶点间的边都包含在这些选出的边中，称这些边为该连通图的生成树，其中权值最小的为最小生成树。

2.最小生成树是否唯一

首先需要明确的是，最小生成树是否唯一是由图决定的，并不是算法本身导致的。因此，最小生成树是否唯一与算法选择是没有关系的。

比如以下这个图，我们可以依次去掉边(a,d)、(d,e)、(e,c)、(e,b)，得到的三种方案中，b、c、d构成的三角形中的最长边的权值都是3，因此这个图有3个最小生成树。


但是，如果一个图上的所有边的权值都相等，那么它就只有一个最小生成树。

3.证明最小生成树是否唯一

这里介绍两种证明最小生成树唯一的方法。

方法一：

对于一个无向图，假设它存在两个不同的最小生成树T1和T2。也就是说，它们的权重都相等。

将T1和T2分别按边权从小到大排序，得到的边分别为e1,e2,...,en和f1,f2,...,fn。

然后构造一个新的图G'，其中图的各个顶点与T1和T2中的对应顶点相同，边集为e1,f1,e2,f2,....,en,fn。可以看出，G’有2n个边，但是只有n个顶点。

显然，G'不连通。在边权相等的情况下，权重相同的最小生成树只有一个，因此T1和T2不可能同时为G'的最小生成树。接下来，我们需要证明，任何时候，G'的最小生成树都只有一个。

考虑G'的最小生成树。首先很明显，它至少包括T1和T2中每个顶点的代表。我们将这些代表称为SuperVertices。记G'的最小生成树为S。

现在，假设我们对S进行了两种构造：对于e[i]=ei=(u,v)，我们选择了e[i]，而对于f[i]=(u',v')我们选择了f[i]。这会导致G'中一个环的产生，环中除了e[i]和f[i]，所有的边都为e或f。

接下来，我们证明这种情况是不可能发生的。如果这种情况发生了，那么我们就可以对交换其选择并令S仍为G'的最小生成树。

如果我们从e[i]和f[i]来分析这个环，如果e[i]和f[i]都在树中（在下图中，如果 ei 和 fi 在蓝色的网格线内，表示它们都在 T1 中，并且在 G' 的最小生成树 S 中），我们必须换掉其中一条边。


如果我们从环中的其他边来看，我们想要找到一些边来换掉。对于任何一条在环里面的边，如果它的两端都在不同的代表中，那么换掉它和另一张边树会更小。


于是乎，我们就证明了如果两张最小生成树不一样，那么就会出现环，这时候，我们可以通过「在环上换一条边」来得到另一张最小生成树，那么这样，在环上换各边，最终得到的两张最小生成树，实际上是「路线相同，但是边权不同」的两张树，这与最小生成树“权值相等”的定义相违背。

方法二：

对于一个图G，如果存在两个最小生成树T1和T2，从T1中删去路径P的最重边以及从T2中删去路径P的最轻边后所构造的新图G’仍能存在一棵最小生成树，那么T1和T2并不都是该图的最小生成树。根据这个原理来证明即可。

假设G有两个不同的最小生成树T1和T2，均有边集E1和E2。 将它们按照边权从小到大排序后，对于任意相同编号的边，如果在两棵树中的选择不同，那么将编号相同的边相互连通就会得到一些环。

我们在这个维度上取一个最小的T1上的环，环上两个边分别是e1和e2，假设e2选自T2。我们删去e2会让T2失去连通性（否则这个环会对T1构成一个重复）。我们在T1中加入e1，使其成为一个环，然后跑其它算法（如Prim）来寻找其中的边。我们将找到相同的最小生成树，因为e2不能是任何算法的答案，而e1又必然会是（它是唯一取消T1一个环的边）。因此，T1和T2并不都是该图的最小生成树。

4.结论

因此，从两个不同的角度来看，最小生成树的唯一性都能得到证明：当权值均等时，最小生成树唯一；当权值不均等时，最小生成树只有一个。但需要注意的是，证明过程基于图没有环的情况下，当存在环的时候，最小生成树并不唯一。

整体来说，最小生成树是具有一定唯一性的，但在某些情况下，最小生成树并不一定是唯一的，因此在使用最小生成树求解时需要根据具体问题情况进行分析。