Hamilton-út

A Wikiszótárból, a nyitott szótárból

Magyar

Kiejtés

  • IPA: [ ˈhɒmiltonuːt]

Főnév

Hamilton-út

  1. (matematika, gráfelmélet) 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