 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.

Graph
A graph is a collection of vertices (or points) and edges (which connect the vertices). This project deals, specifically, with undirected graphs of size 2n vertices, each of order of at least n.
Vertex
Vertices are points or locations on the graph. They can represent people, places, computers, or anything else, but generally an object or resting place.
Edge
Edges connect vertices. They can represent roads, relationships, connections, datapaths, or anything connecting vertices. They can be directed or undirected.
Degree or Order
The degree or order of vertex A is the number of edges connected to it.
Directed vs. Undirected
A directed edge is one that only flows in one direction, from vertex a to vertex b. An undirected edge is bidirectional. In an undirected graph, all edges are undirected.
Simple Graph
A simple graph is one that no more than one edge (in each direction, if directed) between vertices, and no loops from a vertex to itself.
Path
A path is a series of n edges. Each edge must end in the same vertex where the next edge begins. In a simple graph, this is equivalent to a series of n+1 vertices.
Circuit or Closed Path
A circuit is a path which starts and ends at the same vertex.
Hamiltonian Circuit
A Hamiltonian circuit is a closed path which visits every vertex in the graph exactly one time, and its first vertex is also its last. (A Hamiltonian path does not make a cycle, but visits every vertex.)
Ceiling(x)
Ceiling is a function which takes a real number and rounds up to the nearest integer. (This is not really a graph-theory term.)
(The glossary is hidden. Show glossary)

### 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.