This project was originally done for “MAT 243: Discrete Math” with Dr. Susanna Fishel as part of a “Footnote 18” project for honors credit with Barrett, the Honors College at ASU, in Fall 2007.

Next spring, this project was presented at SUnMaRC 2008. You may download the presentation here as Keynote (original format, 0.4MB), Interactive QuickTime (full effects, 40MB), Flash (4.7MB), PowerPoint (0.5MB), or PDF (0.6MB). For source code and the original write-up, see below.


The Problem

Given an undirected graph, construct a Hamiltonian circuit. (Note: Finding such a circuit or showing none is possible on a certain graph is known as the Hamiltonian cycle problem and is NP-complete, that is, there is likely no efficient way to consistently solve it.)

The Solution

As noted, this problem is very complicated and usually inefficient to solve. Here we use a potentially more usable and efficient algorithm, albeit only able to solve the problem for graphs for which every vertex is of the order ceiling(n/2) where n is the number of vertices in the graph. That is, for a graph G of size n, consisting of vertices A = {a1, a2, ยทยทยท, an−1, an}, and d(a) is “degree” or “order” of vertex aA, then our solution applies when ∀a[d(a) ≥ ceil(n/2)] is true.

This is possible due to the idea that, in such a graph, an existing “almost-circuit” with a gap where there “should” be the final edge can be repaired. This is done by connecting the first vertex in question to a point early in the almost-circuit and the second vertex in question to a point immediately later in the almost-circuit, and removing the edge between those two earlier points. (We know that at least one pair of such desirable contiguous earlier vertices exist because each vertex has at least half as many edges as there are vertices.) The result is a circuit. This process can be repeated, which is the basis for our algorithm as shown below.

  1. Construct the simple undirected graph G1 based on user input.
  2. Remember the true graph G1, but also make a new simple undirected graph G2. The new graph G2 needs to be of the same size n as G1, but every vertex should be connected to every other vertex; that is, each vertex must be d(n−1).
  3. Construct a Hamiltonian circuit on G2. This is elementary since any attempted circuit will succeed, as all possible edges on G2 exist.
  4. One by one, remove edges from G2 if they are not in G1. If removing the edge breaks the Hamiltonian circuit on G2, then:
    • Consider the first vertex of the removed edge a and the second b (ordered as in the circuit).
    • Start at the beginning of the broken circuit and investigate each vertex. If the vertex in question c is connected to a and the immediately next vertex d is connected to b, then connect a to c and b to d in our broken circuit, and then remove the edge (b, c) from the circuit. It has now been repaired.
    • If the vertex in question did not satisfy the above condition, then continue until one is found that does.
  5. After all edges in G2 not in G1 have been removed and the circuit has been continually repaired as above, the circuit is now a Hamiltonian path that applies to the original graph G1. The algorithm has now completed discovering a Hamiltonian circuit in the original graph.

Implementation

This algorithm was implemented using C++ and the Boost library on Xcode. The source code for our implementation is shown below. While it does not use two graphs and a circuit, but rather one graph and one circuit represented as a graph with n vertices, we do not believe this to be the most efficient or elegant solution, as we were not used to the Boost Graph Library and pounded out a hack job.

References

  • Rosen, Kenneth H. Discrete Mathematics and Its Applications. McGraw-Hill, New York, 2007. Chapter 9: Graphs.
  • Ore, Oystein. “Note on Hamilton Circuits.” American Mathematical Monthly, 1960. Cites work done by D. J. Newman.