I am interested in the Hamiltonian Cycle problem.
I have built some simple tools in Perl, to visualize graphs, and to attempt to solve the Hamiltonian Cycle problem for a user-entered graph.
Note: This application utilizes inline SVG for the diagrams, and is compatible only with Chrome and later versions of Safari (5.1.4 and above).
Firefox and IE are not supported. Try it. It might work.
HTML5 version coming soon.
Here is a relatively complex graph being evaluated by the
Hamiltonian Graph Detector. This script often simplifies the input graph by removing vertices and edges, according to certain rules. Also, the Hamiltonian Graph Detector generates isomorphs of the input graph. All transforms are done while preserving the
- Here is another complex graph which the script correctly detects as non-Hamiltonian.
- Here is a simple graph which is obviously Hamiltonian.
- Another complex graph, correctly detected as Hamiltonian.
- Here is the Herschel Graph.
The Herschel Graph is richly connected; all vertices have degree 3 or 4. One would intuitively expect the Herschel Graph to be Hamiltonian. However, the Herschel Graph is the smallest, non-Hamiltonian, polyhedral graph.
- Ashwin Dixit
ganesha - dot - computes - at - gmail - dot - com