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

Question

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

请举一个这些陈述有意义的例子。

Answer 1

查看Wikipedia 上的 MST 示例以供参考：

生成树中的瓶颈是该树中的最大权重边。生成树中可能存在多个瓶颈（当然，所有瓶颈都具有相同的权重）。在 Wikipedia MST 中有两个权重为 8 的瓶颈。

现在，取给定图的最小生成树（可能有多个 MST，当然，它们的总边权重相同）并调用最大边权重 B。在我们的示例中，B = 8。

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

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

1. 它仍然是一棵生成树，并且
2. 它仍然不使用任何大于 8 的权重，但是
3. 你增加了总边缘权重

例如，仅将 Wikipedia MST 的“左侧”子树（由权重 {2,2,3} 组成）更改为 {2,3,6}，从而在不改变瓶颈的情况下将总边权重增加 4 8. Bingo，你创建了一个不是 MST 的 MBST。

Answer 2

在回答您的问题之前，让我定义一些此处使用的术语...

1）生成树：给定图的生成树是覆盖该图中所有顶点的树。

2）最小生成树（MST）：给定图的MST是该图的所有可能生成树中长度最小的生成树。更清楚地，对于给定的图，列出所有可能的生成树（可能非常大）并选择边缘权重之和最小的一棵。

3）最小瓶颈生成树（MBST）：给定图的MBST是所有可能生成树中最大边权重最小的生成树。更清楚地，对于给定的图，列出所有可能的生成树和每个生成树的最大边权重。其中选择最大边权重最小的生成树。

现在让我们用一个四节点图来看看下图……

Graph-A 是给定的原始图。如果我列出该图的所有可能生成树并选择边权重之和最小的那棵，那么我将得到 Graph-B。所以图B是最小生成树（MST）。注意它的总权重是1+2+3=6。

现在，如果我选择最大边权重最小的生成树（即 MBST），那么我最终可能会选择 Graph-B（或）Graph-C。请注意，这两个生成树的最大边权重为 3，这是所有可能的生成树中最小的。

从 Graph-B 和 Graph-C 可以清楚地看出，即使 Graph-C 是 MBST，它也不是 MST。因为它的总权重是1+3+3=7，大于Graph-B中绘制的MST的总权重（即6）。

所以 MBST 不一定是给定图的 MST。但是 MST 必须是 MBST。