Similar to the DUCK tour problem in Example. Model each map by a graph and then Eulerize i...

Similar to the DUCK tour problem in Example. Model each map by a graph and then Eulerize it to design a route that uses a minimal number of streets more than once

Designing a DUCK Tour

The Boston DUCK tour company wants to design a DUCK route in a historic area of Boston shown in the map in Figure. We want to begin and end the tour at the same location and minimize traveling over any street more than once. Find such a route.

SOLUTION:

We can model this map with the graph shown in Figure. We represent each intersection by a vertex and each section of street joining two intersections by an edge.

We labeled the odd vertices in this graph A, B, and so on. To Eulerize this graph, we duplicate some edges so that the new graph has only even vertices. We show this in Figure.

If we begin our route at the upper right corner of the graph and follow the edges as they are numbered, we will traverse all the edges of the graph and return to our starting point. Notice that the five pairs of duplicate edges—AB, CG, and so on—represent streets that must be traveled twice. Although we will not prove it, there is not a better way to Eulerize the original graph to reduce the number of streets that are traveled twice.

Graph representing Boston historic area.

Route for DUCK tour.