The graph represents a salesman’s area of activity with the shops that the salesman must visit each day. What route around the shops has the minimum total distance?
A Hamiltonian circuit (named after the Irish mathematician Sir William Rowan Hamilton) is a continuous path in a graph that passes through each of the vertices exactly once and returns to its starting point.
How many Hamiltonian circuits can you find in these graphs?
Here is another classic problem. A salesman lives in city A and he has to visit the cities B, C and D. The distances between the cities are: AB = 120, AC=140, AD=180, BC=70, BD=100, CD=110. Find the shortest round trip from A through the other three cities.