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

Question

赋权图G的最小瓶颈生成树是G的生成树，使得生成树中任何边的最大权值最小。MBST不一定是MST（最小生成树）。

请举例说明这些说法有意义的地方。

Answer 1

看看维基百科上的MST示例可供参考：

生成树中的瓶颈是该树中的最大权重边。在一个生成树中可能有几个瓶颈（当然都是相同的权重）。在维基百科MST中，有两个重量为8的瓶颈。

现在，取一个给定图的最小生成树（可能有几个MST，当然都具有相同的总边权重），并调用最大边权重B。

任何也有B=8瓶颈的生成树都是MBST。但它可能不是MST（因为总的边缘权重大于可能的最佳权重）。

因此，使用维基百科MST并修改它（添加/删除一些边），以便

1. 它仍然是生成树，并且
2. 它仍然不使用任何重量>8，然而
3. 增加总边缘权重

例如，只需将Wikipedia MST的“左侧”子树（由权重{2,2,3}组成）改为{2,3,6}，从而将总边权重增加4而不改变瓶颈8。答对了，您创建了一个不是MST的MBST。