最小的瓶颈是如何生成树从最小生成树有什么不同？ [英] How is a minimum bottleneck spanning tree different from a minimum spanning tree?

问题描述

加权图的最小瓶颈生成树的的是的生成树，从而最大限度地减少了生成树的任何边的最大重量。一个MBST不一定是MST（最小生成树）。

A minimum bottleneck spanning tree of a weighted graph G is a spanning tree of G such that minimizes the maximum weight of any edge in the spanning tree. A MBST is not necessarily a MST (minimum spanning tree).

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

Please give an example where these statements make sense.

推荐答案

看 MST例如维基百科中，以供参考：

在一个生成树的瓶颈是在树中的最大权重的边缘。可能有几个瓶颈（所有课程的同等重量的）的生成树。在维基百科的MST有重8的两大瓶颈。

A bottleneck in a spanning tree is a maximum-weight edge in that tree. There may be several bottlenecks (all of the same weight of course) in a spanning tree. In the Wikipedia MST there are two bottlenecks of weight 8.

现在，取一给定图形的最小生成树（可能有几个MSTS，所有与当前相同的总边加权值），并调用最大边缘重量B.在我们的实施例B = 8

Now, take a minimum spanning tree of a given graph (there may be several MSTs, all with the same total edge weight of course) and call the maximum edge weight B. In our example B = 8.

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

Any spanning tree that also has a bottleneck of B = 8 is an MBST. But it may not be an MST (because the total edge weight is bigger than the best possible).

所以，走维基百科MST并进行修改（添加/删除一些边），这样

So, take the Wikipedia MST and modify it (add / remove some edges) so that

1. 它仍然是一个生成树和
2. 在它仍然没有使用任何重量> 8，但
3. 您增加总的边权

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

For example change just the sub-tree "on the left" of the Wikipedia MST (consisting of weights {2, 2, 3}) to {2, 3, 6}, thus increasing total edge weight by 4 without changing the bottleneck of 8. Bingo, you've created an MBST which is not an MST.

这篇关于最小的瓶颈是如何生成树从最小生成树有什么不同？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！