## 9.1 Outline

- Euler circuits
- Konigsberg bridge problem
- definition of a graph (or a network)
- traversable network
- degree of a vertex
- Euler circuit
- odd/even vertex
- connected network
- Euler’s circuit theorem

- Applications of Euler circuits
- supermarket problem
- police patrol problem
- floor-plan problem
- water-pipe problem

- Hamiltonian cycles
- traveling salesperson problem (TSP)
- definition
- loop
- brute-force method
- nearest neighbor method
- sorted-edge method
- 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.