Page 723 - Discrete Mathematics and Its Applications

702 10 / Graphs

complexity would be a major accomplishment because it has been shown that this problem
is NP-complete (see Section 3.3). Consequently, the existence of such an algorithm would
imply that many other seemingly intractable problems could be solved using algorithms with
polynomial worst-case time complexity.

Applications of Hamilton Circuits

Hamilton paths and circuits can be used to solve practical problems. For example, many appli-
cations ask for a path or circuit that visits each road intersection in a city, each place pipelines
intersect in a utility grid, or each node in a communications network exactly once. Finding a
Hamilton path or circuit in the appropriate graph model can solve such problems. The famous
traveling salesperson problem or TSP (also known in older literature as the traveling sales-
man problem) asks for the shortest route a traveling salesperson should take to visit a set of
cities. This problem reduces to finding a Hamilton circuit in a complete graph such that the total
weight of its edges is as small as possible. We will return to this question in Section 10.6.
We now describe a less obvious application of Hamilton circuits to coding.

EXAMPLE 8 Gray Codes The position of a rotating pointer can be represented in digital form. One way to
n
do this is to split the circle into 2 arcs of equal length and to assign a bit string of length n to
each arc. Two ways to do this using bit strings of length three are shown in Figure 12.
The digital representation of the position of the pointer can be determined using a set of n
contacts. Each contact is used to read one bit in the digital representation of the position. This
is illustrated in Figure 13 for the two assignments from Figure 12.
When the pointer is near the boundary of two arcs, a mistake may be made in reading its
position. This may result in a major error in the bit string read. For instance, in the coding
scheme in Figure 12(a), if a small error is made in determining the position of the pointer, the
bit string 100 is read instead of 011. All three bits are incorrect! To minimize the effect of an
n
error in determining the position of the pointer, the assignment of the bit strings to the 2 arcs
should be made so that only one bit is different in the bit strings represented by adjacent arcs.
This is exactly the situation in the coding scheme in Figure 12(b). An error in determining the
position of the pointer gives the bit string 010 instead of 011. Only one bit is wrong.
A Gray code is a labeling of the arcs of the circle such that adjacent arcs are labeled with bit
strings that differ in exactly one bit. The assignment in Figure 12(b) is a Gray code. We can find
a Gray code by listing all bit strings of length n in such a way that each string differs in exactly
one position from the preceding bit string, and the last string differs from the first in exactly one
position. We can model this problem using the n-cube Q n . What is needed to solve this problem
is a Hamilton circuit in Q n . Such Hamilton circuits are easily found. For instance, a Hamilton

(a) (b)
111 000 100 000
110 001 101 001

101 010 111
011
100 011 110 010

FIGURE 12 Converting the Position of a Pointer into Digital Form.