Data Structures- A Look At Hamiltonian Circuits - Java Tutorials | Dream.In.Code

Data Structures- A Look At Hamiltonian Circuits - Java Tutorials | Dream.In.Code

What Is a Hamiltonian Circuit?
A Hamiltonian Circuit is a cyclic Graph (or sub-graph) such that each vertex can only be accessed in a single path. They also contain all the vertices in the given graph. As such, all Graphs containing Hamiltonian Circuits have at least three vertices. Hamiltonian circuits are cyclic graphs with n vertices and edges. As such, each vertex in the circuit has a degree of two.

There are a number of different theorems that can be used to determine the Hamiltonicity of a graph. The two simplest theorems to look at are Dirac's Theorem and Ore's Theorem. Dirac's Theorem states that a simple graph has a Hamiltonian circuit if it has at least three vertices, all of which have a degree of at least number of vertices/2. Ore's Theorem states that for a simple graph with at least three vertices, the graph has a Hamiltonian circuit if each pair of vertices that are not adjacent have a combined degree greater than or equal to the number of vertices.

Finding Hamiltonian Circuits in Unweighted Graphs
Based on the above properties of Hamiltonian circuits, let's examine an algorithm to find these circuits in unweighted graphs. Kruskal's algorithm to find a minimum spanning tree is a good place to start because it deals with reassembling edges on a graph. Simply by applying Kruskal's algorithm with a couple checks, finding a Hamiltonian circuit in a graph becomes pretty simple. Simply reassemble the edges such that no Vertex has a degree of two, and that no circuit is created. Order the vertices based on degree, and deal with the vertices of degree two first using Kruskal's algorithm. This helps assure that at the end, no additional vertices will have a degree that isn't two. Next, deal with the vertices of degree greater than two. For each vertex, choose an edge that satisfies the above conditions. Repeat until any edge choice would violate the tree property.

Wait, the purpose of the algorithm is to find a Hamiltonian circuit though? By the time this portion of the algorithm finishes, the final result will be a singly-linked list with a head and tail node. Every other vertex will have a degree of two. Simply connect the head and tail nodes to complete the Hamiltonian circuit.

Travelling Salesman Problem
The goal in finding Hamiltonian circuits in weighted graphs is to find the circuit with the lowest total cost. This is also called the Travelling Salesman Problem, and it is considered an NP problem, meaning there is no known polynomial time solution. In this section, we will explore the Held-Karp algorithm, which is the best known solution, solving the Travelling Salesman Problem within 0.5% of the optimal solution. It has a runtime complexity of O(n² * 2ⁿ).

The Held-Karp algorithm works by finding a Vertex such that the sum of the distances across its two lowest-cost Edges is less than that of any other Vertex. It then finds the minimum spanning tree along the remaining Vertices using Prim's algorithm, which is essentially the same as Dijkstra's algorithm except it doesn't violate the Tree property. The other constraint it places is that no Vertex can have a degree greater than two in the final Hamiltonian circuit.

Read full article from Data Structures- A Look At Hamiltonian Circuits - Java Tutorials | Dream.In.Code