Az utazó ügynök problémája: egy utazóügynök n várost akar meglátogatni úgy, hogy az út végén visszaérjen a központi irodába. Bármely két város közötti utazás költsége ismert. Keressünk egy hatékony algoritmust, amely megtalálja a legolcsóbb utat.

A válasz meglepő: nem ismert az, hogy létezik-e hatékony algoritmus a probléma megoldására.

Megjegyzés.

Hatékony algoritmuson olyan eljárást értünk, amely a bemenő adatok számának függvényében polinomiálisan sok lépésben megoldja a feladatot. Ilyen például n szám rendezése, amelyet -nel arányos számú lépésben megoldhatunk.

A fenti feladatnak egy változata a következő variáns: Mi történik akkor, ha az úttól azt követeljük meg, hogy körút legyen, azaz nincs megengedve az, hogy az utazás alatt ugyanazt a várost kétszer is érintse.

Azt a körutat, amely tartalmazza a problémához tartozó gráf minden csúcspontját, Hamilton körnek nevezzük, és azt a gráfot, amelynek van Hamilton köre, Hamilton gráfnak nevezzük.

Megjegyzés.

A Hamilton kör problémájának a története - röviden - a következő: 1855-ben Thomas P. Kirkman következő kérdést tette fel: Legyen adott egy poliéderhez tartozó gráf. Lehet-e mindig konstruálni egy olyan körutat, amely minden csúcspontot egyszer és csak egyszer érint? Sir William Rowan Hamilton 1857-ben konstruált egy játékot, amely során a feladat az volt, hogy miként lehet a dodekaéder csúcsaiba vert szögeken végigvezetni egy madzagot úgy, hogy minden csúcsot csak egyszer érintünk. Ez volt  19. század "Rubik kockája ".

A gazdaságos Hamilton kör meghatározásánál lényegesen egyszerűbb az a feladat, hogy létezik-e Hamilton kör a gráfban?  Ennek - a látszólag egyszerű kérdésnek a megválaszolása is nehéz. Általános esetben erre sincs hatékony eljáráson alapuló válasz. Ismerünk néhány tételt, amely elegendő feltételeket ad arra, hogy egy gráf Hamilton gráf legyen:

Tétel 10.5 (Dirac): Ha G egy 2n-ed rendű gráf, és minden csúcspontja legalább n-ed fokú, akkor a gráf Hamilton-gráf.

Tétel 10.6 (O. Ore, 1960): Ha G egy n-ed rendű, n ≥ 3, és minden nem szomszédos u, v csúcspontjára deg u + deg v ≥ n, akkor G Hamilton-gráf.

Reguláris gráfok esetében a Dirac-tétel javítható: Jackson (1980) kimutatta, hogy minden olyan 2-összefüggő r-reguláris  gráf, amely-nek legalább 3r csúcspontja van, az Hamilton-gráf. A Petersen gráf mutatja, hogy a 3r feltétel nem helyettesíthető  3r+1-el.