问题:给出一个无向加权图的示例,该图具有两个权重相等的边,为此,它们仍然具有唯一的最小生成树。这种图有很多例子。举一个简单的例子,任何无向加权图实际上是一棵树,并具有两个相等权重的边,都具有唯一的最小生成树–整个图本身是唯一可能的生成树,因为图本身是一棵树。
我不确定我是否理解答案:
答案:有很多这样的图的例子。举一个简单的例子,任何无向加权图实际上是一棵树,并具有两个相等权重的边,都具有唯一的最小生成树–整个图本身是唯一可能的生成树,因为图本身是一棵树。
假设您有一个已经是树的图形。也就是说,它已连接并且没有周期。由于该图是树,因此该图已经是其自己的MST。这意味着您可以根据需要将权重分配给边缘,如果使用任何MST算法计算MST,您将始终获得相同的图形-即,您将获得图形本身。因此,您可以通过举例说明一棵具有两个权重相同的边的树来解决此问题。
作为示例,请考虑以下图表:
* *
| |
*--*--*--*
| |
* *
此图是一棵树,所以不管您如何加权边缘,它都是它自己的MST。如果您使每条边的权重为137,则该图仍然只有一个MST,即图本身。