How is a minimum bottleneck spanning tree different from a minimum spanning tree?

Question

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.

Answer 1

Look at the MST example on Wikipedia for reference:

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.

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.

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).

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

1. it remains a spanning tree, and
2. it still doesn't use any weight > 8, yet
3. you increase the total edge weight

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.

Answer 2

Before answering your question, let me define some of the terms that are used here...

1) Spanning Tree : Spanning tree of a given graph is a tree which covers all the vertices in that graph.

2) Minimum spanning tree (MST) : MST of a given graph is a spanning tree whose length is minimum among all the possible spanning trees of that graph. More clearly, for a given graph, list all the possible spanning trees (which can be very large) and pick the one whose sum of edge weights is minimum.

3) Minimum Bottleneck spanning tree (MBST) : MBST of a given graph is a spanning tree whose maximum edge weight is minimum among all the possible spanning trees. More clearly, for a given graph, list all the possible spanning trees and the maximum edge weight for each of the spanning trees. Among these pick the spanning tree whose maximum edge weight is minimum.

Now let us look at the following picture with a four node graph...

Graph-A is the given original graph. If I list all the possible spanning trees for this graph and pick the one whose sum of edge weights is minimum, then I will get the Graph-B. So Graph-B is the Minimum Spanning Tree(MST). Note that its total weight is 1+2+3=6.

Now, if I pick a spanning tree whose maximum edge weight is minimum (i.e MBST), then I may end up picking up either Graph-B (or) Graph-C. Note that both of these spanning trees have maximum edge weight 3, which is minimum among all the possible spanning trees.

From the Graph-B and Graph-C, it is clear that even though the Graph-C is a MBST, it is not MST. Because its total weight is 1+3+3=7, which is greater than the total weight of MST drawn in Graph-B (i.e 6).

So MBST not necessarily be a MST of a given graph. But the MST must be MBST.