Can someone introduce me to the Hamiltonian Cycle?

Question

I have this project where I have to come up with Java source code implementing the Hamiltonian cycle. I searched on google and at least now I know what a Hamiltonian cycle is, path that passes through all vertices just once except the starting vertex because it's also the last vertex (tell me if I'm wrong). The problem is I don't know how to implement it. Basically, my questions are:

How, where do you implement a Hamiltonian cycle?
What is the application of a Hamiltonian Cycle (so that it helps to understand why it's so important)

Better to use its full name - Hamiltonian cycle, not Ham cycle. — duffymo, Mar 16 '11 at 09:49
We build pig farms, give the pigs grain and such to eat, the pigs get fat, we eat the pigs, and in turn we gain energy to build and maintain the existing pig farms. Hence the ham cycle is maintained. — Chris Dennett, Mar 18 '11 at 12:29
it is not TSP. TSP: find the shortest path. HC: find path with no repetitions. — Bernd Elkemann, Mar 18 '11 at 12:43

score 3 · Answer 1 · edited Aug 30 '12 at 10:30

You don't implement a Hamiltonian cycle, you find it (or find out that none exists for your given graph). Since this is an NP-complete problem, which means this is probably no efficient solution, I'd just implement a simple backtracking algorithm. Since you're looking for a cycle, it does not matter at which node you start.
Hamiltonian cycles can be used in cryptography for zero-knowledge proofs. I'm not sure whether this is still just research or whether it's being actively used in any cryptographic protocol.

score 0 · Answer 2 · answered Mar 18 '11 at 12:48

Is this homework? If so please tag it as such.

It is easy to implement it if you can use recursion (not the case if the graph gets too large). What you do is write a function that takes as argument the graph (there are different representations for this), the function checks whether the graph consists of only the starting-point, if so it returns, if it didnt return it calls itself recursively for each node N that is still in the graph and gives the graph minus the node N as arguments.

score 0 · Answer 3 · answered Mar 18 '11 at 13:07

The simplest way is to start with one node, "tag it", choose the next reachable "untagged" node, "tag it", and continue until either:

you reach the starting node, thus you found Hamiltonian cycle. Repeat the cycle for every node to find each and every Hamiltonian cycle in that graph.
You cannot choose another "untagged" node, which means that there is no Hamiltonian cycle for that starting node (but you found a Hamiltonian Path, anyway).

That algorithm can be optimized in several ways, but I let you that to you. Any solution you find will be NP-complete.

As for they uses, I only saw them in Graph theory and AI classes (this is a particular travelsman problem, where each edge has a cost of 1) and they never told me real-life uses for that.

score 0 · Answer 4 · edited Oct 28 '12 at 14:52

0

(B) Practical Application

Determining most efficient switching network for phone systems
Best bus routes, postal routes, meter checking routes

edited Oct 28 '12 at 14:52

j0k

22,600
28
79
90

answered Feb 27 '12 at 16:23

Haneef Mohamed

1

Can someone introduce me to the Hamiltonian Cycle?

4 Answers4