Revision history [back]

Hi,

Sage has the command:

hamiltonian_cycle(algorithm='tsp')

"Returns a Hamiltonian cycle/circuit of the current graph/digraph A graph (resp. digraph) is said to be Hamiltonian if it contains as a subgraph a cycle (resp. a circuit) going through all the >vertices. Computing a Hamiltonian cycle/circuit being NP-Complete, this algorithm could run for some time depending on the instance.

ALGORITHM:

See Graph.traveling_salesman_problem for ‘tsp’ algorithm and find_hamiltonian from sage.graphs.generic_graph_pyx for >>‘backtrack’ algorithm.

INPUT:

algorithm - one of ‘tsp’ or ‘backtrack’. OUTPUT: If using the ‘tsp’ algorithm, returns a Hamiltonian cycle/circuit if it exists; otherwise, raises a EmptySetError exception. If >>using the ‘backtrack’ algorithm, returns a pair (B,P). If B is True then P is a Hamiltonian cycle and if B is False, P is a >>longest path found by the algorithm. Observe that if B is False, the graph may still be Hamiltonian. The ‘backtrack’ >>algorithm is only implemented for undirected graphs."

The above is directly from Hamiltonian Cycle

Added in the same area on the page is:

sage: g = graphs.HeawoodGraph()
sage: g.hamiltonian_cycle()
TSP from Heawood graph: Graph on 14 vertices
sage: g = graphs.PetersenGraph()
sage: g.hamiltonian_cycle()
Traceback (most recent call last):
...
EmptySetError: The given graph is not Hamiltonian

So clearly there is some algorithms on your question, though it is also known that this is an NP-Complete problem.

Good luck, fieldofnodes