最小的瓶颈如何生成树从最小生成树不同？(How is a minimum bottleneck sp

加权图G的一个瓶颈最小生成树为G这样的生成树，在生成树任何边的最大重量最小化。一个MBST不一定是MST（最小生成树）。

请举一个例子，其中这些语句是有意义的。

Answer 1:

看看维基百科上MST例子以供参考：

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

现在，来给定的图形的最小生成树（可能有多个MSTS，所有课程的相同的总边加权），并调用最大边权重B.在我们的例子B = 8。

任何生成树还具有B的瓶颈= 8是MBST。但它可能不是一个MST（因为总边缘重量比最好尽可能大）。

因此，采取维基百科MST和修改（添加/删除一些边缘），这样

例如，“左侧的”维基百科MST（由权重{2，2,3}）到的变化只是该子树{2，3，6}，从而增加总的边缘由4重量而不改变的瓶颈8.宾果游戏，你已经创建了一个MBST这不是一个MST。

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

1）生成树：跨越给定图的树是覆盖在该曲线图的所有顶点的树。

2）最小生成树（MST）：一个给定的图形的MST是一个生成树的长度是所有图的可能的生成树中间的最小值。更明确地说，对于一个给定图，列出所有可能的生成树（这是非常大），其挑边权的总和最小的一个。

3）最低瓶颈生成树（MBST）：一个给定的图形的MBST是生成树其最大边权重是所有可能的生成树中间的最小值。更明确地说，对于一个给定图，列出所有可能的生成树以及每个生成树的最大边的权重。在这些挑生成树其最大边的权重最小。

现在，让我们看看有四个节点图下面的图片...

图的A是给定的原始曲线图。如果我列出这个图形可能生成树，并挑选其边缘的权重之和是最小的一个，那么我会得到图-B。所以格拉夫-B是最小生成树（MST）。需要注意的是它的总重量为1 + 2 + 3 = 6。

现在，如果我挑选一个生成树其最大边权重最小（即MBST），那么我最终可能会拿起以图表-B（或）图形-C。请注意，这两个生成树有最大的优势权重为3，这是所有可能的生成树中最小的。

从图形-B和图表-C，很显然，即使图-C是MBST，这不是MST。因为它的总重量为1 + 3 + 3 = 7，这比MST的格拉夫-B绘制的总重量较大的（即，6）。

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

文章来源: How is a minimum bottleneck spanning tree different from a minimum spanning tree?