(9 pts) Problem 20 in Chapter 4 (Greedy Algorithms). The input is a (undirected) graph where the nodes are towns and the edges represent the roads between them. Each edge is labeled with the maximum altitude along that road, and assume that all these altitudes are different. The height of a path is the maximum of the edge-altitudes over the edges in the path. For each pair of nodes, a winter-optimal path between them is a path from one to the other such that the path height is as small as possible (i.e. no other path between the two nodes has a lower path height). Since there may be many paths, there may be multiple paths with the same path height even though the edge altitudes are all different. Prove that the Minimum Cost Spanning Tree with edge costs equal to the edge altitudes provides winter-optimal paths between the vertices. You may use the fact that if a sequence of edges is a path between two vertices, then there is a simple path between the vertices using a subsequence of the edges. (If the path is already a simple path, the subsequence is the original path). Every September, somewhere in a far-away mountainous part of the world, the county highway crews get together and decide which roads to keep clear through the coming winter. There are n towns in this county, and the road system can be viewed as a (connected) graph G= (V, E) on this set of towns, each edge representing a road joining two of them. In the winter, people are high enough up in the mountains that they stop worrying about the length of roads and start worrying about their altitude-this is really what determines how difficult the trip will be. So each road-each edge e in the graph-is annotated with a number ae that gives the altitude of the highest point on the road. We'll assume that no two edges have exactly the same altitude value ae. The height of a path P in the graph is then the maximum of ae over all edges e on P. Finally, a path between towns i and j is declared to be winter-optimal if it achieves the minimum possible height over all paths from i to j The highway crews are going to select a set E' C E of the roads to keep clear through the winter; the rest will be left unmaintained and kept off limits to travelers. They all agree that whichever subset of roads E' they decide to keep clear, it should have the property that (V, E') is a connected subgraph; and more strongly, for every pair of towns i and j, the height of the winter-optimal path in (V, E') should be no greater than it is in the full graphG-(V,E). We'll say that (V, E) is a minimum-altitude connected subgraph if it has this property Given that they're going to maintain this key property, however, they otherwise want to keep as few roads clear as possible. One year, they hit upon the following conjecture: The minimum spanning tree of G, with respect to the edge weights ae, is a minimum-altitude connected subgraph. In an earlier problen, we claimed that there is a unique minimum span ning tree when the edge weights are distinct. Thus, thanks to the assump- tion that all ae are distinct, it is okay for us to speak of the minimum spanning tree.) Initially, this conjecture is somewhat counterintuitive, since the min- imum spanning tree is trying to minimize the sum of the values ae, while the goal of minimizing altitude seems to be asking for a fairly different thing. But lacking an argument to the contrary, they begin considering an even bolder second conjecture: A subgraph (V, E) is a minimum-altitude connected subgraph if and only if it contains the edges of the minimum spanning tree. Note that this second conjecture would immediately imply the first one, since a minimum spanning tree contains its own edges. (9 pts) Problem 20 in Chapter 4 (Greedy Algorithms). The input is a (undirected) graph where the nodes are towns and the edges represent the roads between them. Each edge is labeled with the maximum altitude along that road, and assume that all these altitudes are different. The height of a path is the maximum of the edge-altitudes over the edges in the path. For each pair of nodes, a winter-optimal path between them is a path from one to the other such that the path height is as small as possible (i.e. no other path between the two nodes has a lower path height). Since there may be many paths, there may be multiple paths with the same path height even though the edge altitudes are all different. Prove that the Minimum Cost Spanning Tree with edge costs equal to the edge altitudes provides winter-optimal paths between the vertices. You may use the fact that if a sequence of edges is a path between two vertices, then there is a simple path between the vertices using a subsequence of the edges. (If the path is already a simple path, the subsequence is the original path). Every September, somewhere in a far-away mountainous part of the world, the county highway crews get together and decide which roads to keep clear through the coming winter. There are n towns in this county, and the road system can be viewed as a (connected) graph G= (V, E) on this set of towns, each edge representing a road joining two of them. In the winter, people are high enough up in the mountains that they stop worrying about the length of roads and start worrying about their altitude-this is really what determines how difficult the trip will be. So each road-each edge e in the graph-is annotated with a number ae that gives the altitude of the highest point on the road. We'll assume that no two edges have exactly the same altitude value ae. The height of a path P in the graph is then the maximum of ae over all edges e on P. Finally, a path between towns i and j is declared to be winter-optimal if it achieves the minimum possible height over all paths from i to j The highway crews are going to select a set E' C E of the roads to keep clear through the winter; the rest will be left unmaintained and kept off limits to travelers. They all agree that whichever subset of roads E' they decide to keep clear, it should have the property that (V, E') is a connected subgraph; and more strongly, for every pair of towns i and j, the height of the winter-optimal path in (V, E') should be no greater than it is in the full graphG-(V,E). We'll say that (V, E) is a minimum-altitude connected subgraph if it has this property Given that they're going to maintain this key property, however, they otherwise want to keep as few roads clear as possible. One year, they hit upon the following conjecture: The minimum spanning tree of G, with respect to the edge weights ae, is a minimum-altitude connected subgraph. In an earlier problen, we claimed that there is a unique minimum span ning tree when the edge weights are distinct. Thus, thanks to the assump- tion that all ae are distinct, it is okay for us to speak of the minimum spanning tree.) Initially, this conjecture is somewhat counterintuitive, since the min- imum spanning tree is trying to minimize the sum of the values ae, while the goal of minimizing altitude seems to be asking for a fairly different thing. But lacking an argument to the contrary, they begin considering an even bolder second conjecture: A subgraph (V, E) is a minimum-altitude connected subgraph if and only if it contains the edges of the minimum spanning tree. Note that this second conjecture would immediately imply the first one, since a minimum spanning tree contains its own edges