Grafteori: Eulervei og Hamiltonsti

Hva er den handelsreisendes problem?

Den handelsreisendes problem er et klassisk problem i grafteori.

Den handelsreisendes skal besøke flere byer nøyaktig en gang hver og deretter returnere til opprinnelsesbyen. Den handelsreisende vet avstanden mellom hvert par av byer og ønsker den korteste ruten.

Problemet kan modelleres med å finne den korteste Hamiltonsykelen gjennom en vektet graf.