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. 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.

Egy ${\displaystyle P}$ út egy ${\displaystyle G=(V,E)}$ gráfban Hamilton-út, ha ${\displaystyle P}$ a ${\displaystyle V}$ összes elemét pontosan egyszer tartalmazza.

• 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.

• 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.

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

• Hamilton-kör

• Eric W. Weisstein: Hamilton-kör a MathWordnél
• G. Gutin – P. Moscato: The Hamiltonian Page
• Hamilton játékai

Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!