Introduction To Algorithm上的问题：

Problems 23-3: Bottleneck spanning tree


A bottleneck spanning tree T of an undirected graph G is a spanning tree of G whose largest edge weight is minimum over all spanning trees of G. We say that the value of the bottleneck spanning tree is the weight of the maximum-weight edge in T.

a. Argue that a minimum spanning tree is a bottleneck spanning tree.

Part shows that finding a bottleneck spanning tree is no harder than finding a minimum spanning tree. In the remaining parts, we will show that one can be found in linear time.

b. Give a linear-time algorithm that given a graph G and an integer b, determines whether the value of the bottleneck spanning tree is at most b.

c. Use your algorithm for part as a subroutine in a linear-time algorithm for the bottleneck-spanning-tree problem. (Hint: You may want to use a subroutine that contracts sets of edges, as in the MST-REDUCE procedure described in Problem 23-2.)

问题a和b很好解决，主要是问题c
Solution:
a. 假设有MST为Tm,任意的Spanning Tree为Ts, 它们对应的最大边为em-max和es-max，可能出项两种情况：
1. em-max属于Ts, 显然此时weight(em-max) <= weight(es-max)
2. em-max不属于Ts,那么Ts加上em-max会形成一个环，而em-max不可能比这个环上其他的边都大（否则，这个环上必定存在某条边e，在Tm中断开em-max再加上e，形成一个新的Spanning Tree Tm'，由于weight < weight(em-max)，Tm'的权重比MST Tm还要小，矛盾），因此，环上存在某条边ex，使得weight(em-max) <= weight(ex) <= weight(es-max)
根据1，2可知，em-max的权重小于等于任意Spanning Tree，因此是个Bottleneck Spanning Tree

b.在图G中，删掉所有权重大于b的边形成新图Gb。在这个图中进行Breadth first search，如果能找出包括所有顶点的Spanning Tree，那么Bottleneck Spanning Tree的值不超过b。删边时间复杂度为O(V)，BFS为O(V+E)，总时间线型。下面证明BSF能在Gb中搜出Spanning Tree和Bottleneck Spanning Tree（下面简称BST)的值不超过b这两个命题是等价的：
1.Gb中如果能BFS出Spanning Tree Tb，那么Tb的最大权重边eb-max的权重肯定是小于等于b的，而根据定义G的BST的值小于等于weight(eb-max)，即不超过b。
2.如果G的BST值不超过b，那么这个BST的所有边的权值都不超过b，因此这个BST属于Gb，也就是说Gb是联通的，BFS自然能在Gb中搜出Spanning Tree。

问题C是最棘手的地方，我一开始是想如果所有的权重是整数的话，可以从1到max-weight(G)依次调用b中的过程，找到第一个BFS不能搜出来的Gb，那么BST的值就是(b+1)，时间复杂度是O(max-weight(G)*(V+E))，这种方法太无耻了，而且完全没用到提示的Hint（这个Hint和前面的一个题有关），各位看看有什么方法解决。

你这个无耻方法显然不作数呀 ……
十分钟没想出来，得空看一下那个提示之后再说吧。