Question 1.84

1. Find the cheapest route in the accompanying graph, where one starts at vertex A, finishes at vertex A, and traverses each edge at least once. The cost of a route is computed by summing the numbers along the edges that one uses.
2. How many edges are repeated in the minimal-cost route?
3. Discuss the implications of this example for the relation between finding good eulerizations of graphs and the problem of finding cheap routes that start and end at the same vertex and traverse each edge at least once.
4. The physical edge with cost 20 in the diagram is not physically longer than other edges with lower costs attached to them. Explain why in an urban setting it might make sense to assign two stretches of street of similar length very different “costs” for traversing them.
5. What are some different meanings that “weights” (for example, traffic volume) potentially assigned to edges in a graph might have in an urban setting?