Question 2.81

51. The accompanying figure represents a town where there is a sewer located at each corner (where two or more streets meet). After every thunderstorm, the department of public works wishes to have a truck start at its headquarters (at vertex H) and make an inspection of sewer drains to be sure that leaves are not clogging them. Can a route start and end at H that visits each corner exactly once? (Assume that all the streets are two-way streets.) Does this problem involve finding an Euler circuit or a Hamiltonian circuit?

image

Assume that at equally spaced intervals along the blocks in this graph, there are storm sewers that must be inspected after each thunderstorm to see if they are clogged. Is this a Hamiltonian circuit problem, an Euler circuit problem, or a Chinese postman problem? Find an optimal tour to do this inspection.

51.

Yes; Hamiltonian circuit; Chinese postman problem; answers will vary and require at least 9 reuses of edges.