Hamilton-út

A Wikiszótárból, a nyitott szótárból
Ugrás a navigációhoz Ugrás a kereséshez

Flag of Hungary.svg Magyar

Főnév

Hamilton-út

  1. (matematika) A Hamilton-út a gráfelmélet egy fogalma, nevét William Rowan Hamilton ír matematikus, fizikus és csillagászról kapta. Akkor nevezünk egy utat Hamilton-útnak, ha az a gráf minden csúcsán pontosan egyszer halad át. Irányított és irányítatlan gráfokban egyaránt értelmezhető az út, így a Hamilton-út fogalma is. Ha van Hamilton-kör, akkor van Hamilton-út is, de ez megfordítva már nem igaz.

Egy kellően bonyolult gráfban nehéz megtalálni a Hamilton-utat. A feladat az utazóügynök-probléma speciális esete, és mint ilyen, NP-teljes.

Fordítások