CHAPTER 13 Summary 889 2. A graph with exactly two odd vertices has at least one Euler path but no Euler circuits. Each Euler path must begin at one of the two odd vertices and end at the other odd vertex. 3. A graph with more than two odd vertices has no Euler paths or Euler circuits. Fleury’s Algorithm To determine an Euler path or an Euler circuit: 1. Use Euler’s theorem to determine whether an Euler path or an Euler circuit exists. If one exists, proceed with Steps 2–5. 2. If the graph has no odd vertices (therefore has at least one Euler circuit that is also an Euler path), choose any vertex as the starting point. If the graph has exactly two odd vertices (therefore has only an Euler path), choose one of the two odd vertices as the starting point. 3. Begin to trace edges as you move through the graph. Number the edges as you trace them. Since you can’t trace any edges twice in Euler paths and Euler circuits, once an edge is traced consider it “invisible.” 4. When faced with a choice of edges to trace, if possible, choose an edge that is not a bridge (i.e., don’t create a disconnected graph with your choice of edges). 5. Continue until each edge of the entire graph has been traced once. Examples 5– 6, pages 857–860 Section 13.3 Paths and Circuits A Hamilton path is a path that contains each vertex of a graph exactly once. A Hamilton circuit is a path that begins and ends at the same vertex and passes through all vertices exactly one time. Number of Unique Hamilton Circuits in a Complete Graph The number of unique Hamilton circuits in a complete graph with n vertices is n( 1)!, − where n n n n ( 1)! ( 1)( 2)( 3) (3)(2)(1) − = − − − The Brute Force Method of Solving Traveling Salesman Problems To determine the optimal solution: 1. Represent the problem with a complete, weighted graph. 2. List all possible Hamilton circuits in this graph. 3. Determine the cost associated with each of these Hamilton circuits. 4. The Hamilton circuit with the lowest cost is the optimal solution. The Nearest Neighbor Method for Determining an Approximate Solution to a Traveling Salesman Problem To approximate the optimal solution: 1. Represent the problem with a complete, weighted graph. 2. Identify the starting vertex. 3. Of all the edges attached to the starting vertex, choose the edge that has the smallest weight. This edge is the shortest distance or the lowest cost. Travel along this edge to the second vertex. 4. At the second vertex, choose the edge that has the smallest weight that does not lead to a vertex already visited. Travel along this edge to the third vertex. 5. Continue this process, each time moving along the edge with the smallest weight until all vertices are visited. 6. Travel back to the original vertex. Discussion, pages 866 –867; Example 2, page 868 Examples 3–5, pages 868–870 Discussion, page 869; Example 5, pages 869–870 Discussion, page 871; Example 6, pages 871–872
RkJQdWJsaXNoZXIy NjM5ODQ=