# Hamiltonian Circuits

### Learning Outcomes

- Identify whether a graph has a Hamiltonian circuit or path
- Find the optimal Hamiltonian circuit for a graph using the brute force algorithm, the nearest neighbor algorithm, and the sorted edges algorithm
- Identify a connected graph that is a spanning tree
- Use Kruskal's algorithm to form a spanning tree, and a minimum cost spanning tree

## Hamiltonian Circuits and the Traveling Salesman Problem

In the last section, we considered optimizing a walking route for a postal carrier. How is this different than the requirements of a package delivery driver? While the postal carrier needed to walk down every street (edge) to deliver the mail, the package delivery driver instead needs to visit every one of a set of delivery locations. Instead of looking for a circuit that covers every edge once, the package deliverer is interested in a circuit that visits every vertex once.### putting all your study skills together

This section contains a bit of everything you've encountered so far: new vocabulary, new usages of familiar words, multi-step processes, and new ideas. Allow yourself ample time to work through the examples and problems multiple times so that you can develop a good understanding.### Hamiltonian Circuits and Paths

**Hamiltonian circuit**is a circuit that visits every vertex once with no repeats. Being a circuit, it must start and end at the same vertex. A

**Hamiltonian path**also visits every vertex once with no repeats, but does not have to start and end at the same vertex.

### Example

### Example

Does a Hamiltonian path or circuit exist on the graph below? We can see that once we travel to vertex E there is no way to leave without returning to C, so there is no possibility of a Hamiltonian circuit. If we start at vertex E we can find several Hamiltonian paths, such as ECDAB and ECABD### Try It

[ohm_question]6557[/ohm_question]**Traveling salesman problem**(TSP) because the question can be framed like this: Suppose a salesman needs to give sales pitches in four cities. He looks up the airfares between each city, and puts the costs in a graph. In what order should he travel to visit each city once then return home with the lowest cost? To answer this question of how to find the lowest cost Hamiltonian circuit, we will consider some possible approaches. The first option that might come to mind is to just try all different possible circuits. question can be framed like this: Suppose a salesman needs to give sales pitches in four cities. He looks up the airfares between each city, and puts the costs in a graph. In what order should he travel to visit each city once then return home with the lowest cost? To answer this question of how to find the lowest cost Hamiltonian circuit, we will consider some possible approaches. The first option that might come to mind is to just try all different possible circuits.

### Brute Force Algorithm (a.k.a. exhaustive search)

### Example

Apply the Brute force algorithm to find the minimum cost Hamiltonian circuit on the graph below.Circuit |
Weight |

ABCDA | 4+13+8+1 = 26 |

ABDCA | 4+9+8+2 = 23 |

ACBDA | 2+13+9+1 = 25 |

### Try It

[ohm_question]78158[/ohm_question]**complete graph.**Suppose we had a complete graph with five vertices like the air travel graph above. From Seattle there are four cities we can visit first. From each of those, there are three choices. From each of those cities, there are two possible cities to visit next. There is then only one choice for the last city before returning home. This can be shown visually:

### Number of Possible Circuits

*N*vertices in a complete graph, there will be [latex](n-1)!=(n-1)(n-2)(n-3)\dots{3}\cdot{2}\cdot{1}[/latex] routes. Half of these are duplicates in reverse order, so there are [latex]\frac{(n-1)!}{2}[/latex] unique circuits. The exclamation symbol, !, is read “factorial” and is shorthand for the product shown.

### Example

Cities |
Unique Hamiltonian Circuits |

9 | 8!/2 = 20,160 |

10 | 9!/2 = 181,440 |

11 | 10!/2 = 1,814,400 |

15 | 14!/2 = 43,589,145,600 |

20 | 19!/2 = 60,822,550,204,416,000 |

**not**an efficient algorithm.

### Nearest Neighbor Algorithm (NNA)

*and*optimal algorithm to solve the TSP, and it is very unlikely anyone ever will. Since it is not practical to use brute force to solve the problem, we turn instead to

**heuristic algorithms**; efficient algorithms that give approximate solutions. In other words, heuristic algorithms are fast, but may or may not produce the optimal circuit.

### Example

**greedy**algorithm, meaning it only looks at the immediate decision without considering the consequences in the future. In this case, following the edge AD forced us to use the very expensive edge BC later.

### Example

### Example

### Try It

The table below shows the time, in milliseconds, it takes to send a packet of data between computers on a network. If data needed to be sent in sequence to each computer, then notification needed to come back to the original computer, we would be solving the TSP. The computers are labeled A-F for convenience.A | B | C | D | E | F | |

A | -- | 44 | 34 | 12 | 40 | 41 |

B | 44 | -- | 31 | 43 | 24 | 50 |

C | 34 | 31 | -- | 20 | 39 | 27 |

D | 12 | 43 | 20 | -- | 11 | 17 |

E | 40 | 24 | 39 | 11 | -- | 42 |

F | 41 | 50 | 27 | 17 | 42 | -- |

### Example

### Example

*Derivative Work*, is doing a bar tour in Oregon. The driving distances are shown below. Plan an efficient route for your teacher to visit all the cities and return to the starting location. Use NNA starting at Portland, and then use Sorted Edges.

Ashland | Astoria | Bend | Corvallis | Crater Lake | Eugene | Newport | Portland | Salem | Seaside | |

Ashland | - | 374 | 200 | 223 | 108 | 178 | 252 | 285 | 240 | 356 |

Astoria | 374 | - | 255 | 166 | 433 | 199 | 135 | 95 | 136 | 17 |

Bend | 200 | 255 | - | 128 | 277 | 128 | 180 | 160 | 131 | 247 |

Corvallis | 223 | 166 | 128 | - | 430 | 47 | 52 | 84 | 40 | 155 |

Crater Lake | 108 | 433 | 277 | 430 | - | 453 | 478 | 344 | 389 | 423 |

Eugene | 178 | 199 | 128 | 47 | 453 | - | 91 | 110 | 64 | 181 |

Newport | 252 | 135 | 180 | 52 | 478 | 91 | - | 114 | 83 | 117 |

Portland | 285 | 95 | 160 | 84 | 344 | 110 | 114 | - | 47 | 78 |

Salem | 240 | 136 | 131 | 40 | 389 | 64 | 83 | 47 | - | 118 |

Seaside | 356 | 17 | 247 | 155 | 423 | 181 | 117 | 78 | 118 | - |

*To see the entire table, scroll to the right*

Using NNA with a large number of cities, you might find it helpful to mark off the cities as they’re visited to keep from accidently visiting them again. Looking in the row for Portland, the smallest distance is 47, to Salem. Following that idea, our circuit will be:

Using Sorted Edges, you might find it helpful to draw an empty graph, perhaps by drawing vertices in a circular pattern. Adding edges to the graph as you select them will help you visualize any circuits or vertices with degree 3.

We start adding the shortest edges:

Seaside to Astoria 17 miles

Corvallis to Salem 40 miles

Portland to Salem 47 miles

Corvallis to Eugene 47 miles

Newport to Astoria (reject – closes circuit)

Newport to Bend 180 miles

Bend to Ashland 200 miles

At this point the only way to complete the circuit is to add:

Crater Lk to Astoria 433 miles. The final circuit, written to start at Portland, is:

Portland, Salem, Corvallis, Eugene, Newport, Bend, Ashland, Crater Lake, Astoria, Seaside, Portland. Total trip length: 1241 miles.

While better than the NNA route, neither algorithm produced the optimal route. The following route can make the tour in 1069 miles:

Portland, Astoria, Seaside, Newport, Corvallis, Eugene, Ashland, Crater Lake, Bend, Salem, Portland

### Try It

## Spanning Trees

A company requires reliable internet and phone connectivity between their five offices (named A, B, C, D, and E for simplicity) in New York, so they decide to lease dedicated lines from the phone company. The phone company will charge for each link made. The costs, in thousands of dollars per year, are shown in the graph. In this case, we don’t need to find a circuit, or even a specific path; all we need to do is make sure we can make a call from any office to any other. In other words, we need to be sure there is a path from any vertex to any other vertex.### Spanning Tree

**spanning tree**is a connected graph using all vertices in which there are no circuits. In other words, there is a path from any vertex to any other vertex, but no circuits.

**subgraph**– a new graph formed using all the vertices but only some of the edges from the original graph. No edges will be created where they didn’t already exist. Of course, any random spanning tree isn’t really what we want. We want the

**minimum cost spanning tree (MCST)**.

### Minimum Cost Spanning Tree (MCST)

### Kruskal’s Algorithm

- Select the cheapest unused edge in the graph.
- Repeat step 1, adding the cheapest unused edge, unless:
- adding the edge would create a circuit

### Example

### Example

Ashland | Astoria | Bend | Corvallis | Crater Lake | Eugene | Newport | Portland | Salem | Seaside | |

Ashland | - | 374 | 200 | 223 | 108 | 178 | 252 | 285 | 240 | 356 |

Astoria | 374 | - | 255 | 166 | 433 | 199 | 135 | 95 | 136 | 17 |

Bend | 200 | 255 | - | 128 | 277 | 128 | 180 | 160 | 131 | 247 |

Corvallis | 223 | 166 | 128 | - | 430 | 47 | 52 | 84 | 40 | 155 |

Crater Lake | 108 | 433 | 277 | 430 | - | 453 | 478 | 344 | 389 | 423 |

Eugene | 178 | 199 | 128 | 47 | 453 | - | 91 | 110 | 64 | 181 |

Newport | 252 | 135 | 180 | 52 | 478 | 91 | - | 114 | 83 | 117 |

Portland | 285 | 95 | 160 | 84 | 344 | 110 | 114 | - | 47 | 78 |

Salem | 240 | 136 | 131 | 40 | 389 | 64 | 83 | 47 | - | 118 |

Seaside | 356 | 17 | 247 | 155 | 423 | 181 | 117 | 78 | 118 | - |

*To see the entire table, scroll to the right*

*The graph up to this point is shown below.*

Continuing,

Newport to Salem reject Corvallis to Portland reject Eugene to Newport reject Portland to Astoria reject Ashland to Crater Lk 108 miles Eugene to Portland reject Newport to Portland reject Newport to Seaside reject### Try It

Find a minimum cost spanning tree on the graph below using Kruskal’s algorithm. [embed]https://www.myopenmath.com/multiembedq.php?id=6581&theme=oea&iframe_resize_id=mom5[/embed]*n*vertices if each vertex has degree

*n*/2 or greater.

## Licenses & Attributions

### CC licensed content, Original

- Revision and Adaptation.
**Provided by:**Lumen Learning**License:**CC BY: Attribution.

### CC licensed content, Shared previously

- Hamiltonian circuits .
**Authored by:**LIPPMAN, DAVID.**License:**CC BY: Attribution. - TSP by brute force .
**Authored by:**OCLPhase2.**License:**CC BY: Attribution. - Number of circuits in a complete graph .
**Authored by:**OCLPhase2.**License:**CC BY: Attribution. - Nearest Neighbor ex2 .
**Authored by:**OCLPhase2.**License:**CC BY: Attribution. - Sorted Edges ex 2 .
**Authored by:**OCLPhase2.**License:**CC BY: Attribution. - Kruskal's ex 1 .
**Authored by:**OCLPhase2.**License:**CC BY: Attribution. - Kruskal's from a table .
**Authored by:**OCLPhase2.**License:**CC BY: Attribution.