576
Graph Algorithms
hamiltonian circuit Problem
Another famous mathematician, William Rowan Hamilton (1805–1865), posed a
problem in graph theory that sounds very much like Euler’s. He asked how to tell
whether a graph has a hamiltonian circuit.
Definition hAMiltoNiAN ciRcuit
A Hamiltonian circuit in a graph is a cycle using every node of the graph.
(Recall that in a cycle, only the node that forms the beginning and the ending of
the cycle is repeated.)
An Euler path in a graph requires that each and every arc of the graph be used
once and only once, but nodes can be repeated. A Hamiltonian circuit requires
that each and every node of the graph be visited once and only once (except for the
start node, which is also the end node) but there can be unused arcs; no arc can be
used more than once because that would involve revisiting a node.
Like the Euler path problem, the Hamiltonian circuit problem can be solved
for a given graph by trial and error. The algorithm is as follows: Start from one
node of the graph and try some path by choosing various arcs. If the path results
in a repeated node, it is not a cycle, so throw it away and try a different path. If
the path can be completed as a cycle, then see whether it visited every node; if not,
throw it away and try a different path. Continue in this fashion until all possible
paths have been tried or a Hamiltonian circuit has been found. This will involve
some careful record keeping so that no path is tried more than once. The trial-anderror approach is theoretically possible—but it is practically impossible! In all but
the smallest of graphs, there will simply be too many paths to try.
Euler found a simple, efficient algorithm to determine, for an arbitrary graph,
if an Euler path exists. Although the Hamiltonian circuit problem sounds very
similar to the Euler path problem, there is a basic difference. No efficient algorithm has ever been found to determine if a Hamiltonian circuit exists. In fact,
there is some evidence (see Section 9.3) to suggest that no such algorithm will
ever be found.
In certain types of graphs we can easily determine whether a Hamiltonian
circuit exists. For example, an unconnected graph cannot have a Hamiltonian circuit because there would be no way to construct a path reaching all nodes. A
complete graph with n > 2 has a Hamiltonian circuit because for any node on
the path, there is always an arc to travel to any unused node and finally an arc
to return to the starting point. Exercise 37 describes an additional condition that
guarantees the existence of a Hamiltonian circuit. But in general—that is, for an
arbitrary graph—we cannot readily make a determination about the existence of
a Hamiltonian circuit.
Suppose we are dealing with a weighted graph. If a Hamiltonian circuit exists for the graph, can we find one with minimum weight? This is the traveling
praCtiCe 11 Do Hamiltonian circuits exist for the graphs of Figure 7.6? (Use trial and error to answer.) ■
Graph Algorithms
hamiltonian circuit Problem
Another famous mathematician, William Rowan Hamilton (1805–1865), posed a
problem in graph theory that sounds very much like Euler’s. He asked how to tell
whether a graph has a hamiltonian circuit.
Definition hAMiltoNiAN ciRcuit
A Hamiltonian circuit in a graph is a cycle using every node of the graph.
(Recall that in a cycle, only the node that forms the beginning and the ending of
the cycle is repeated.)
An Euler path in a graph requires that each and every arc of the graph be used
once and only once, but nodes can be repeated. A Hamiltonian circuit requires
that each and every node of the graph be visited once and only once (except for the
start node, which is also the end node) but there can be unused arcs; no arc can be
used more than once because that would involve revisiting a node.
Like the Euler path problem, the Hamiltonian circuit problem can be solved
for a given graph by trial and error. The algorithm is as follows: Start from one
node of the graph and try some path by choosing various arcs. If the path results
in a repeated node, it is not a cycle, so throw it away and try a different path. If
the path can be completed as a cycle, then see whether it visited every node; if not,
throw it away and try a different path. Continue in this fashion until all possible
paths have been tried or a Hamiltonian circuit has been found. This will involve
some careful record keeping so that no path is tried more than once. The trial-anderror approach is theoretically possible—but it is practically impossible! In all but
the smallest of graphs, there will simply be too many paths to try.
Euler found a simple, efficient algorithm to determine, for an arbitrary graph,
if an Euler path exists. Although the Hamiltonian circuit problem sounds very
similar to the Euler path problem, there is a basic difference. No efficient algorithm has ever been found to determine if a Hamiltonian circuit exists. In fact,
there is some evidence (see Section 9.3) to suggest that no such algorithm will
ever be found.
In certain types of graphs we can easily determine whether a Hamiltonian
circuit exists. For example, an unconnected graph cannot have a Hamiltonian circuit because there would be no way to construct a path reaching all nodes. A
complete graph with n > 2 has a Hamiltonian circuit because for any node on
the path, there is always an arc to travel to any unused node and finally an arc
to return to the starting point. Exercise 37 describes an additional condition that
guarantees the existence of a Hamiltonian circuit. But in general—that is, for an
arbitrary graph—we cannot readily make a determination about the existence of
a Hamiltonian circuit.
Suppose we are dealing with a weighted graph. If a Hamiltonian circuit exists for the graph, can we find one with minimum weight? This is the traveling
praCtiCe 11 Do Hamiltonian circuits exist for the graphs of Figure 7.6? (Use trial and error to answer.) ■