Business Efficiency

Hamiltonian Circuits

A Hamiltonian Circuit is a circuit that visits every vertex exactly once.

Do these graphs have a Hamiltonian circuit?
Example 1:

Example 2:

Real life applications:
- anything where you have to visit all locations, such as

pizza delivery
mail delivery
traveling salesman
garbage pickup
bus service/ limousine service
reading gas meters

Example 3:
Minimum Cost Hamiltonian Circuit

You plan a vacation and wish to visit all spots, yet minimize the mileage driven.

Brute Force Algorithm: list all circuits
compute distances
choose tour of minimum mileage

do the tree.
start at A:

ABCDA        18
ABDCA        20
ACBDA        20

Example 4:
A complete graph on n vertices is a graph that has exactly one edge between any two vertices.

Given a complete graph on 7 vertices, how many possible itineraries are there

if the starting point is A and you care about the direction of travel?

if the starting point is A and you don't care about the direction of travel?

if you could start anywhere and you care about the direction of travel?

if you could start anywhere and you don't care about the direction of travel?

Example 5: compare magnitudes

n	1	2	3	4	5	6	7	8	9	10
n!	1	2	6	24	120	720	5,040	40,320	362,880	3,628,800
2ⁿ	2	4	8	16	32	64	128	256	512	1024

Whether a graph does or doesn't have a Hamiltonian circuit is an "NP-hard" problem, i.e an exponential type problem:
for a graph involving n vertices any known algorithm would involve at least 2ⁿsteps to solve it.
Finding a Hamiltonian circuit may take n! many steps and n! > 2ⁿfor most n.

Example 6:
A graph is bipartite if the vertices can be grouped into two sets S and T, so that every edge in the graph has one endpoint in S and the other in T.

Example:
this is a bipartite graph. Does it have a Hamiltonian circuit?

Theorem: A bipartite graph, where the sets S and T have an unequal number of vertices, doesn't have a Hamiltonian circuit.

there is a tie.

Heuristic Algorithms are algorithms that

do a pretty good job finding a solution most of the time,
are not optimal some of the time,
may not give a solution at all some of the time.

Two heuristics for the Minimum Cost Hamiltonian circuit problem:

Nearest Neighbor Algorithm
Sorted Edge Algorithm

Nearest Neighbor Algorithm:

start from home
repeat:
visit the nearest neighbor that hasn't been visited yet
return to home when no other choice is available

Comments:

this is a so called greedy algorithm, because it tries to optimize at every step
it is greedy in a local sense
it is quite fast

Sorted Edge Algorithm

sort the edges by increasing weight
repeat
        choose the edge with lowest weight such that
            1.    it never requires that 3 used edges meet at a vertex
            2.    it never closes up a circular tour that doesn't include all vertices

Comments:

also a greedy algorithm, but in a more global sense
it is not quite so fast, because of the edge sorting

Find a Hamiltonian circuit using the Nearest Neighbor Algorithm

starting at A,
starting at B.

Find a Hamiltonian circuit using the Sorted Edge Algorithm.