Hamilton-út

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. Különbséget kell tenni, hogy Hamilton-útról, Hamilton-körről van-e szó, és hogy a gráf irányított, vagy irányítatlan. 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 $P$ út egy $G=(V, E)$ gráfban Hamilton-út, ha $P$ a $V$ ö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 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.

• G. A. Dirac (1952): Minden olyan gráfban van Hamilton-kör, amiben a minimális fokszám $\frac{n}{2}$.
• W. T. Tutte (1956): Minden 4-összefüggő síkgráfban van Hamilton-kör.
• Ø. 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 $n\!$, akkor a gráfban van Hamilton-kör.
• Ø. Ore (1960): Ha az $x,y\!$ nem szomszédos csúcsok foka összesen legalább $n\!$, akkor $G+\{x,y\}\!$ 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 $p\!$, $1\leq p<\frac{n-1}{2}$-re a $\leq p$ fokú csúcsok száma kevesebb, mint $p\!$, és ha n páratlan, akkor még a $\leq \frac{n-1}{2}$ fokú csúcsok száma is legfeljebb $\frac{n-1}{2}$ , akkor a gráf tartalmaz Hamilton-kört.
• V. Chvátal (1972): Az $(a_{1},...,a_{n})\!$ n-es, amire $a_{1}\leq...\leq a_{n}<n$, akkor és csak akkor egy Hamilton-kört tartalmazó gráf fokszámainak sorozata, ha minden $i<\frac{n}{2}$-re teljesül: $a_{i}\leq i \Rightarrow a_{n-i}\geq n-i$.
• V. Chvátal és Erdős Pál (1972): Ha $G\!$ k-összefüggő, és G-ben minden maximális független ponthalmaz mérete $\leq k$, akkor G-ben van Hamilton-kör.
• H. Fleischner (1974): Ha G 2-összefüggő, akkor $G^2\!$-ben van Hamilton-kör.

Lásd még

• 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