Every September, somewhere in a far-away mountainous part of the world, the coun

Question

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 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 graph G = (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 problem, we claimed that there is a unique minimum spanning tree when the edge weights are distinct. Thus, thanks to the assumption 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 minimum 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. So here’s the question.

(a) Is the first conjecture true, for all choices of G and distinct altitudes ae? Give a proof or a counterexample with explanation.

(b) Is the second conjecture true, for all choices of G and distinct altitudes ae? Give a proof or a counterexample with explanation.

Explanation / Answer

We try to prove the following claim,
For any cut $(S, V-S)$ of V, the edge with the minimum altitude value across the cut must be an edge in all minimum-altitude connected subgraphs.
Suppose edge $e=(u,v)$ is the edge with the minimum altitude value across cut $(S, V-S)$, and one minimum-altitude connected subgraph $(V,E')$ does not contain $e$.
Suppose the winter-optimal path between $u$ and $v$ in $E'$ is $P$.

begin figure
begin center
includegraphics[width=0.7 extwidth]
4.20.eps
caption{Path $P$ in $(V, E')$ has a greater altitude than edge $e$}
end
center
vspace{-2ex}
end{figure}

Then $P$ must contain at least one edge $e'$ that is across the cut. Since $e$ is the minimum-altitude edge across the cut,we have $a_{e'}>a_e$, and the height of $P$ is larger than or equal to $a_{e'}$, therefore larger than $a_e$, but the height of winter-optimal path in the full graph $(V,E)$ is less than or equal to $a_e$ because edge $e$ makes one path between $u$ and $v$.This means the height of winter-optimal path in $(V,E')$ is greater than it is in the full graph, which contradicts the definition of minimum-altitude connected subgraph.

Since the minimum spanning tree is composed of edges with minimum altitude values across cuts,
directly yields the result.Every minimum-altitude connected subgraph contains all the edges in the minimum spanning tree and because adding edges to a minimum-altitude connected subgraph always yields another minimum-altitude connected subgraph, so we also have the result.Every supergraph of the minimum spanning tree is a minimum-altitude connected subgraph. Both conjectures in the problem are true. That is,

(a) the minimum spanning tree of $G$, with respect to the edge weights $a_e$, is a minimum-altitude connected subgraph, and
(b) a subgraph $(V, E')$ is a minimum-altitude connected subgraph if and only if it contains the edges of the minimum spanning tree.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.