## Hamiltonian Cycle / Gray Code Animation |
||

A Hamiltonian Cycle is a cycle that visits each node exactly once.
Here we show a Hamiltonian cycle on a 5-dimensional hypercube.
Note that it starts by completely traversing the 4-dimensional hypercube on the
left before reversing the traversal on the right subcube.
Hamiltonian cycles on hypercubes provide constructions for Gray codes, namely
orderings of all subsets of Hamilitonian cycle is an NP-complete problem, so no worst-case efficient algorithm exists to find such a cycle. In practice, we can find Hamiltonian cycles in modest-sized graphs by using backtracking with clever pruning to reduce the search space. |
||

Download:
ham.gif - The Animation. ham.nb - Notebook file. |
||

These animations were produced using
Check out our dfs/bfs, connected components, Hamiltonian cycle, Eulerian cycle, shortest path, transitive closure, and minimum spanning tree animations! |