Hamiltonian circuit

A graph G consists of a set of nodes and a set of edges between nodes.

A Hamiltonian circuit in G is a cycle of nodes such that every node appears in the cycle exactly once.

Example.


This is also known as the "Traveling Salesman Problem" which has been the subject of much research over many years. A leader in this work is the Mathematics department at Princeton University who produced a solution for over 15,000 towns and cities in Germany!

[Prev][TOC][Next]


CS1104 Main Page
Last Updated 2002/02/01
© L.Heath, 2000, upgraded by J.A.N. Lee as above.