Hamiltonian Cycle

• Suppose a salesman wants to visit N cities and return home

        $cities = ['Philadelphia', 'Portland', 'Dayton', ...,
                   'Brussels'];

• But there aren't flights between every possible pair of cities:

        print $flight{Portland}{Dayton};
        # prints 0

        print $flight{Philadelphia}{Brussels};
        # prints 1
        print $flight{Brussels}{Philadelphia};
        # prints 1

• (Or perhaps flights between those cities are infeasible or uninteresting)

• Is there an itinerary that visits each city exactly once and then returns home?

• This problem is NP-complete

Next

Copyright © 2005 M. J. Dominus