salesman problem. Once again it can be solved using trial and error by tracing all
possible paths and keeping track of the weights of those paths that are Hamiltonian circuits, but, again, this is not an efficient algorithm. (Incidentally, the traveling salesman problem for visiting all 48 capitals of the contiguous United States
has been solved—a total of 10,628 miles is required!)
ExErcisEs 7.2
1. Rework Example 3 of Chapter 2 using the theorem on Euler paths. Here is the graph, where the nodes
have been numbered.
1
2
5
4
3
2. a. Add a single arc to the graph of Exercise 1 so that there is an Euler path.
b. List the nodes in such a path.
For Exercises 3–12, determine whether the given graph has an Euler path by using the theorem on Euler paths.
If so, list the nodes in such a path.
3.
5
4
3
1
6
2
4. 1
2
4
3
5
6
Section 7.2 Euler Path and Hamiltonian Circuit
577
s E c t i o n 7 . 2 Review
tEchniquE
• Using algorithm EulerPath, determine whether an
Euler path exists in a graph.
Main idEas
• There is a simple criterion for determining whether
Euler paths exist in a graph but no such criterion
for whether Hamiltonian circuits exist.
• An algorithm that is Θ(n
2
) in the worst case can
determine the existence of an Euler path in a connected graph with n nodes.
W