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.
Definíció Egy út egy gráfban Hamilton-út, ha a összes elemét pontosan egyszer tartalmazza. Megjegyzések A Hamilton-út a gráf csúcsait, míg az Euler-út az éleit járja be. Nem minden gráfban van Hamilton-út. Hamilton-kör tetszőleges élét elhagyva Hamilton-úthoz jutunk. Vannak olyan gráfok, amik nem tartalmaznak Hamilton-kört, de Hamilton-utat igen. Ilyen például a Petersen-gráf és a kétcsúcsú teljes gráf is.
Példák Minden teljes gráfban van Hamilton-út. Minden hiperkocka gráfban van Hamilton-út. Minden szabályos test gráfja és élgráfja tartalmaz Hamilton-utat. Azonos számosságú pontosztályú teljes páros gráfok tartalmaznak Hamilton-utat. Az Euler-gráfok élgráfjai tartalmaznak Hamilton-kört, így Hamilton-utat is. A Hamilton-kört tartalmazó gráfok élgráfjaiban van Hamilton-kör.
Tulajdonságok A következőkben G jelöli a gráfot és n a csúcsainak számát. Gabriel Andrew Dirac (1952): Minden olyan gráfban van Hamilton-kör, amiben a minimális fokszám legalább . William T. Tutte (1956): Minden 4-összefüggő síkgráfban van Hamilton-kör. Øystein Ore (1960) általánosította Dirac tételét: Ha egy gráfban bármely két nem szomszédos csúcs fokszámának összege legalább , akkor a gráfban van Hamilton-kör. Øystein Ore (1960): Ha az nem szomszédos csúcsok foka összesen legalább , akkor akkor és csak akkor tartalmaz Hamilton-kört, ha G is tartalmaz. Pósa Lajos (1962) tovább általánosította a korábbi eredményeket: Ha minden , -re a fokú csúcsok száma kevesebb, mint , és ha n páratlan, akkor még a fokú csúcsok száma is legfeljebb , akkor a gráf tartalmaz Hamilton-kört. Vašek Chvátal (1972): Az n-es, amire , akkor és csak akkor egy Hamilton-kört tartalmazó gráf fokszámainak sorozata, ha minden -re teljesül: . V. Chvátal és Erdős Pál (1972): Ha k-összefüggő, és G-ben minden maximális független ponthalmaz mérete , akkor G-ben van Hamilton-kör. Herbert Fleischner (1974): Ha G 2-összefüggő, akkor -ben van Hamilton-kör.
Kapcsolódó szócikkek Hamilton-kör
Források Eric W. Weisstein: Hamilton-kör a MathWordnél G. Gutin – P. Moscato: The Hamiltonian Page Hamilton játékai
Kategória:Gráfelmélet Kategória:Számítási problémák a gráfelméletben Kategória:Hamilton-utak és -körök