Consider the graph given above. Use the nearest neighbor algorithm to find the H
ID: 3009327 • Letter: C
Question
Consider the graph given above. Use the nearest neighbor algorithm to find the Hamiltonian circuit starting at vertex H.
a. List the vertices in this Hamiltonian circuit in the order they are visited. Do not forget to include the starting vertex at both ends.
b. What is the total weight along this Hamiltonian circuit?
Now use the sorted edges algorithm to find a Hamiltonian circuit.
c. List the weights in this Hamiltonian circuit in the order they are chosen by the algorithm.
d. What is the total weight along this Hamiltonian circuit?
Explanation / Answer
A Hamilton path in a graph is a path that includes each vertex of the graph once and only once. A Hamilton circuit is a circuit that includes each vertex of the graph once and only once. (At the end, of course, the circuit must return to the starting vertex.)
The figure shows a graph that (1)has Euler circuits (the vertices are all even) and (2) has Hamilton circuits. Example 1 Hamilton versus Euler One such Hamilton circuit is A, F, B, C, G, D, E, A – there are plenty more.
Note that if a graph has a Hamilton circuit, then it automatically has a Hamilton path–(the Hamilton circuit can always be truncated into a Hamilton path by dropping the last vertex of the circuit.) For example, the Hamilton circuit A, F, B, C, G, D, E, A can be truncated into the Hamilton path A, F, B, C, G, D, E. Contrast this with the mutually exclusive relationship between Euler circuits and paths: If a graph has an Euler circuit it cannot have an Euler path and vice versa.
This figure shows a graph that (1)has no Euler circuits but does have Euler paths (for example C, D, E, B, A, D) and (2)has no Hamilton circuits (sooner or later you have to go to C, and then you are stuck) but does have Hamilton paths (for example, A, B, E, D, C). Example 1 Hamilton versus Euler This illustrates that a graph can have a Hamilton path but no Hamilton circuit!
This figure shows a graph that (1)has neither Euler circuits nor paths (it has four odd vertices) and (2) has Hamilton circuits (for example A, B, C, D, E, A – there are plenty more)
and consequently has Hamilton paths (for example, A, B, C, D, E)
This figure shows a graph that (1) has no Euler circuits but has Euler paths (F and G are the two odd vertices) and (2) has neither Hamilton circuits nor Hamilton paths