What is a minimal bottleneck spanning tree?
My Algorithms professor gave us an exercise and the solution to that exercise, where I'm absolutely confused about the definition of a bottle neck spanning tree.
Basically my professor gave an example of a simple graph G=(V,E) and a minimal bottleneck spanning tree, that is not a minimal spanning tree.
G=(V,E), V={a,b,c}, E={{a,b},{b,c},{c,a}} (a triangle) and a weight function of w({a,b}) = 3, w({b,c}) = 1, w({c,a}) = 3.
A minimal spanning tree in this example would be obviously any spanning tree, that contains the edge {b,c}, because it has the weight of 1. But my professor says that an example for a minimal bottleneck spanning tree in this example would be T'=(V,E'), with E'={{a,b},{c,a}} with both w(e)=3 edges. How can this be a minimal bottleneck spanning tree, if it does not contain the minimal edge with w(e)=1?
$\endgroup$ 31 Answer
$\begingroup$For bottleneck problems, you minimize the maximum rather than the sum. In particular, the MBST minimizes the maximum edge weight.
$\endgroup$ 3
