最小生成树唯一吗
最小生成树是图论中的一个经典问题,它的解法有很多。我们可以使用Prim算法、Kruskal算法等来求解。但最小生成树是否唯一却一直是个争议点。本文将会从不同的角度介绍最小生成树是否唯一。
1.最小生成树的定义
最小生成树主要解决的问题是给定一个连通无向图,选出一些边使它们连通并且权值之和最小。 在任意连通子图中,若任意两个顶点间的边都包含在这些选出的边中,称这些边为该连通图的生成树,其中权值最小的为最小生成树。
2.最小生成树是否唯一
首先需要明确的是,最小生成树是否唯一是由图决定的,并不是算法本身导致的。因此,最小生成树是否唯一与算法选择是没有关系的。
比如以下这个图,我们可以依次去掉边(a,d)、(d,e)、(e,c)、(e,b),得到的三种方案中,b、c、d构成的三角形中的最长边的权值都是3,因此这个图有3个最小生成树。
![image1](https://i.imgur.com/mHB9g7L.png)
但是,如果一个图上的所有边的权值都相等,那么它就只有一个最小生成树。
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 中),我们必须换掉其中一条边。
![image2](https://i.imgur.com/mGRFJnN.png)
如果我们从环中的其他边来看,我们想要找到一些边来换掉。对于任何一条在环里面的边,如果它的两端都在不同的代表中,那么换掉它和另一张边树会更小。
![image3](https://i.imgur.com/dL4x3hW.png)
于是乎,我们就证明了如果两张最小生成树不一样,那么就会出现环,这时候,我们可以通过「在环上换一条边」来得到另一张最小生成树,那么这样,在环上换各边,最终得到的两张最小生成树,实际上是「路线相同,但是边权不同」的两张树,这与最小生成树“权值相等”的定义相违背。
方法二:
对于一个图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.结论
因此,从两个不同的角度来看,最小生成树的唯一性都能得到证明:当权值均等时,最小生成树唯一;当权值不均等时,最小生成树只有一个。但需要注意的是,证明过程基于图没有环的情况下,当存在环的时候,最小生成树并不唯一。
整体来说,最小生成树是具有一定唯一性的,但在某些情况下,最小生成树并不一定是唯一的,因此在使用最小生成树求解时需要根据具体问题情况进行分析。