algorithm - 最小瓶颈生成树与最小生成树有何不同？

加权图G的最小瓶颈生成树是G的生成树，以使生成树中任何边的最大权重最小。 MBST不一定是MST(最小生成树)。

请举例说明这些陈述是否合理。

最佳答案

查看MST example on Wikipedia以供引用:

生成树中的瓶颈是该树中最大权重的边缘。生成树中可能存在多个瓶颈(当然，它们的权重都相同)。在Wikipedia MST中，存在两个权重为8的瓶颈。

现在，获取给定图的最小生成树(可能有几个MST，当然它们都具有相同的总边缘权重)，并称最大边缘权重B。在我们的示例中B = 8。

任何瓶颈也为B = 8的生成树都是MBST。但这可能不是MST(因为边缘总重量大于最佳边缘重量)。

因此，请使用Wikipedia MST并对其进行修改(添加/删除一些边缘)，以便

它仍然是一棵生成树，而

它仍然不使用任何大于8的权重，但是

您增加总边缘权重

例如，仅将Wikipedia MST“在左侧”的子树(由权重{2，2，3}组成)更改为{2，3，6}，从而将总边缘权重增加4，而不会改变瓶颈8. Bingo，您已经创建了一个不是MST的MBST。

关于algorithm - 最小瓶颈生成树与最小生成树有何不同？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14297409/