give an algorithm constructing a spanning tree T in which, for each u, v V, the bottleneck rate of the u-v path in T is equal to the best achievable bottleneck rate for the pair u, v in G.

A group of network designers at the communications company CluNet find themselves facing the following problem. They have a connected graph G = (V, E), in which the nodes represent sites that want to communicate. Each edge e is a communication link, with a given available bandwidth be. For each pair of nodes u, v V, they want to select a single u-v path P on which this pair will communicate. The bottleneck rate b(P) of this path P is the minimum bandwidth of any edge it contains; that is, b(P) = mineP be. The best achievable bottleneck rate for the pair u, v in G is simply the maximum, over all u-v paths P in G, of the value b(P). Its getting to be very complicated to keep track of a path for each pair of nodes, and so one of the network designers makes a bold suggestion: Maybe one can find a spanning tree T of G so that for every pair of nodes u, v, the unique u-v path in the tree actually attains the best achievable bottleneck rate for u, v in G. (In other words, even if you could choose any u-v path in the whole graph, you couldnt do better than the u-v path in T.) This idea is roundly heckled in the offices of CluNet for a few days, and theres a natural reason for the skepticism: each pair of nodes might want a very different-looking path to maximize its bottleneck rate; why should there be a single tree that simultaneously makes everybody happy? But after some failed attempts to rule out the idea, people begin to suspect it could be possible. Exercises 199 Show that such a tree exists, and give an efficient algorithm to find one. That is, give an algorithm constructing a spanning tree T in which, for each u, v V, the bottleneck rate of the u-v path in T is equal to the best achievable bottleneck rate for the pair u, v in G.