Section 9.1: Euler Circuits and Hamiltonian Cycles

by

9.1 Outline

  1. Euler circuits
    1. Konigsberg bridge problem
    2. definition of a graph (or a network)
    3. traversable network
    4. degree of a vertex
    5. Euler circuit
    6. odd/even vertex
    7. connected network
    8. Euler’s circuit theorem
  2. Applications of Euler circuits
    1. supermarket problem
    2. police patrol problem
    3. floor-plan problem
    4. water-pipe problem
  3. Hamiltonian cycles
    1. traveling salesperson problem (TSP)
    2. definition
    3. loop
    4. brute-force method
    5. nearest neighbor method
    6. sorted-edge method
    7. number of routes

9.1 Essential Ideas

Given a network, begin at some vertex and travel on each edge exactly once, and then return to the starting vertex. Such as path is called an Euler circuit. There is a solution to the question of whether an Euler circuit for a given network exists; it is known as Euler’s circuit theorem.

Euler’s Circuit Theorem

Every vertex on a graph with an Euler circuit has an even degree, and conversely, if in a connected graph every vertex has an even degree, then the graph has an Euler circuit.

Hamiltonian Cycle

Given a network, begin a some vertex and travel to each vertex exactly once, ending at the original vertex. Such a path is called a Hamiltonian cycle. There is no solution to the question of whether a Hamiltonian cycle for a given network exists. The methods we use in this text are brute force (listing all possible routes); nearest neighbor (at each city, go to the nearest neighbor next); and sorted-edge (sometimes the nearest neighbor plan will form a loop without going to some city) procedures.

Sorted-Edge Method

Draw a graph showing the cities and the distances; identify the starting vertex.
Step 1: Choose the edge attached to the starting vertex that has the shortest distance or the lowest cost. Travel along this edge to the next vertex.
Step 2: At the second vertex, travel along the edge with the shortest distance or lowest cost. Do not choose a vertex that would lead to a vertex already visited.
Step 3: Continue until all vertices are visited until arriving back at the original vertex.