1. (25) [Maximum bottleneck rate spanning treel] Textbook Exercise 19 in Chapter 4. Given a connected graph, the problem is to find a spanning tree in which every pair of nodes has a maximum bottleneck rate path between the pair. (Note that the bottleneck rate of a path is defined as the minimum bandwidth of any edge on the path.) First give the algorithm (a sketch of the idea would be sufficient), and then prove the optimality of the algorithm. Without loss of generality, assume that the bandwidths of all edges are distinct. Suggested proof technique: proof by contradiction. Hint: use the cycle property. A group of network designers at the communications company CluNet find themselves facing thee 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 e 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) - mineeP 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) It's 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 couldn't do better than the u-v path in T.) This idea is roundly heckled in the offices of CluNet for a few days, and there's 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. 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 1. (25) [Maximum bottleneck rate spanning treel] Textbook Exercise 19 in Chapter 4. Given a connected graph, the problem is to find a spanning tree in which every pair of nodes has a maximum bottleneck rate path between the pair. (Note that the bottleneck rate of a path is defined as the minimum bandwidth of any edge on the path.) First give the algorithm (a sketch of the idea would be sufficient), and then prove the optimality of the algorithm. Without loss of generality, assume that the bandwidths of all edges are distinct. Suggested proof technique: proof by contradiction. Hint: use the cycle property. A group of network designers at the communications company CluNet find themselves facing thee 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 e 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) - mineeP 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) It's 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 couldn't do better than the u-v path in T.) This idea is roundly heckled in the offices of CluNet for a few days, and there's 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. 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