Hamilton-út

A Wikipédiából, a szabad enciklopédiából

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ó[szerkesztés | forrásszöveg szerkesztése]

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

Megjegyzések[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

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 legalább \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[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]