无向加权图具有唯一的最小生成树。举个例子。包括答案

问题描述 投票:-1回答:1

问题:给出一个无向加权图的示例,该图具有两个权重相等的边,为此,它们仍然具有唯一的最小生成树。这种图有很多例子。举一个简单的例子,任何无向加权图实际上是一棵树,并具有两个相等权重的边,都具有唯一的最小生成树–整个图本身是唯一可能的生成树,因为图本身是一棵树。

我不确定我是否理解答案:

答案:有很多这样的图的例子。举一个简单的例子,任何无向加权图实际上是一棵树,并具有两个相等权重的边,都具有唯一的最小生成树–整个图本身是唯一可能的生成树,因为图本身是一棵树。

algorithm data-structures minimum-spanning-tree
1个回答
0
投票

假设您有一个已经是树的图形。也就是说,它已连接并且没有周期。由于该图是树,因此该图已经是其自己的MST。这意味着您可以根据需要将权重分配给边缘,如果使用任何MST算法计算MST,您将始终获得相同的图形-即,您将获得图形本身。因此,您可以通过举例说明一棵具有两个权重相同的边的树来解决此问题。

作为示例,请考虑以下图表:

     *  *
     |  |
  *--*--*--*
     |  |
     *  *

此图是一棵树,所以不管您如何加权边缘,它都是它自己的MST。如果您使每条边的权重为137,则该图仍然只有一个MST,即图本身。

© www.soinside.com 2019 - 2024. All rights reserved.