13.3 Hamilton Paths and Hamilton Circuits 867 The graph in Fig. 13.36(a) has Hamilton path A B C E D , , , , . The graph in Fig. 13.36(a) also has Hamilton path C B A D E , , , , . The graph in Fig. 13.36(b) has a Hamilton path A B C F H E G D , , , , , , , . The graph in Fig. 13.36(b) also has Hamilton path G D E H F C B A , , , , , , , . Both of the graphs in Fig. 13.36 have other Hamilton paths. Can you determine some of them? A D C B E (a) A B E C D F G H (b) Figure 13.36 Notice that, unlike Euler paths, not every edge needs to be traced in a Hamilton path. To help distinguish between Euler paths and Hamilton paths, remember that Euler paths are concerned with visiting all the edges, whereas Hamilton paths are concerned with visiting all the vertices. Now we introduce Hamilton circuits. Definition: Hamilton Circuit A Hamilton circuit is a path that begins and ends at the same vertex and passes through all other vertices of a graph exactly one time. An alternate definition for a Hamilton circuit is that a Hamilton circuit is a Hamilton path that starts and ends at the same vertex. For example, the graph in Fig. 13.37(a) has Hamilton circuit A B C E D A , , , , , . The graph in Fig. 13.37(a) also has Hamilton circuit B A D E C B , , , , , . The graph in Fig. 13.37(b) has Hamilton circuit A B D G E H F C A , , , , , , , , . The graph in Fig. 13.37(b) also has Hamilton circuit E G D B A C F H E , , , , , , , , . Note that in an Euler circuit, the path followed must include every edge and must begin and end at the same vertex. In a Hamilton circuit, the path followed must include every vertex and must begin and end at the same vertex. Unlike the Euler circuit, however, a Hamilton circuit does not have to include every edge. In Section 13.2, we were fortunate that Euler’s theorem could tell us under what conditions an Euler path or an Euler circuit would exist. We are not as fortunate with Hamilton paths and Hamilton circuits; no such general theorem exists. We now shift our focus to graphs that are guaranteed to have Hamilton circuits. A complete graph is a graph that has exactly one edge between each pair of its vertices. Fig. 13.38 shows complete graphs with three, four, and five vertices, respectively. A B C A B C D A B C D E Figure 13.38 Complete graphs are important because every complete graph has a Hamilton circuit, and traveling salesman problems can be represented by complete graphs. Since each pair of vertices on a complete graph is connected by an edge, we can create a Hamilton circuit by simply starting at any vertex and moving from vertex to vertex until we have passed through each vertex exactly one time. Then to complete the circuit we simply move back to the vertex from which we started. A B D E C (a) Figure 13.37 A B G H D F C E (b)
RkJQdWJsaXNoZXIy NjM5ODQ=