软考
APP下载

最小生成树唯一吗

最小生成树是图论中的一个经典问题,它的解法有很多。我们可以使用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.结论

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

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

备考资料 免费领取:系统分析师报考指南+考情分析+思维导图等 立即下载
真题演练 精准解析历年真题,助你高效备考! 立即做题
相关阅读
系统分析师题库