Wikipédia

Fleischner-tétel

gráfelméleti állítás

A matematika, azon belül a gráfelmélet területén a Fleischner-tétel megadja annak egy elégséges feltételét, hogy egy gráf tartalmazzon Hamilton-kört. Kimondja, hogy ha G kétszeresen csúcsösszefüggő, akkor G négyzete tartalmaz Hamilton-kört. A tétel Herbert Fleischnerről kapta a nevét, aki 1974-ben megadott rá egy bizonyítását.

Egy kétszeresen összefüggő gráf, annak négyzete, és a négyzetnek egy Hamilton-köre

Definíciók és állítás szerkesztés

Egy G irányítatlan gráf Hamilton-köre olyan kör, ami minden csúcsot pontosan egyszer tartalmaz. A kétszeres összefüggőség azt jelenti, hogy nincs benne elvágó csúcs, tehát olyan csúcs, melynek eltávolításával a maradék gráf két vagy több komponensre esne szét. Nem minden 2-összefüggő gráfnak van Hamilton-köre; az ellenpéldák közé tartozik a Petersen-gráf és a K2,3 teljes páros gráf is.

A G gráf négyzete, G2 csúcskészlete megegyezik az eredeti gráféval, és két csúcsa akkor van éllel összekötve, ha G-beli távolságuk legfeljebb kettő. A Fleischner-tétel kimondja, hogy egy véges, legalább három csúcsból álló, kétszeresen csúcsösszefüggő gráf négyzete mindig tartalmaz Hamilton-kört. Ezzel ekvivalens állítás, hogy bármely 2-összefüggő G gráf ciklikus sorrendbe állítható oly módon, hogy a rendezés szomszédos csúcsai a G gráfban egymástól legfeljebb kettő távolságra legyenek.

Kiterjesztések szerkesztés

A Fleischner-tételben szereplő G2 Hamilton-köre megalkotható azzal a megszorítással együtt is, hogy G adott v és w csúcsaira két v-re illeszkedő és egy w-re illeszkedő élt tartalmazzon. Továbbá, ha v és w G szomszédos csúcsai, akkor az előbb említetteket G három különböző éle teljesíti.[1]

A Hamilton-kör mellett a 2-összefüggő gráfok négyzete Hamilton-összefüggő is (ami azt jelenti, hogy bármely két kijelölt csúcsa között vezet Hamilton-út), továbbá 1-hamiltoni (vagyis bármely csúcs törlésével kapott gráf még mindig rendelkezik Hamilton-körrel).[2] Ezen kívül csúcs-pánciklikus, azaz minden v csúcsra és minden k egész számra, ahol 3 ≤ k ≤ |V(G)|, létezik v-t tartalmazó, k hosszúságú kör.[3]

Ha G gráf nem 2-csúcsösszefüggő, négyzetének vagy van Hamilton-köre vagy nincs, ennek meghatározása pedig NP-teljes feladat.[4]

Egy végtelen gráfnak nem lehet Hamilton-köre, mivel minden kör véges, de Carsten Thomassen igazolta, hogy ha G egy végtelen, de lokálisan véges 2-csúcsösszefüggő gráf egyetlen véggel, akkor G2 rendelkezik duplán végtelen Hamilton-úttal.[5] Általánosabban, ha G lokálisan véges, 2-csúcsösszefüggő és tetszőleges számú véggel rendelkezik, akkor G2-nek van Hamilton-köre. Abban a kompakt topologikus térben, amit úgy kapunk, hogy a gráfot szimpliciális komplexusnak tekintjük és a végeihez egy-egy végtelenben lévő pontot adunk, egy Hamilton-kör definiálható úgy, mint egy euklideszi körrel homeomorf és minden csúcson áthaladó altér.[6]

Algoritmusok szerkesztés

Egy n-csúcsú, 2-összefüggő gráf négyzetének egy Hamilton-köre O(n2) időben található meg.[7] A Fleischner-tétel segítségével a metrikus terek bottleneck utazó ügynök problémájához (wd) 2-approximáció szerkeszthető.[8]

Történet szerkesztés

A Fleischner-tétel bizonyítását Herbert Fleischner 1971-ben jelentette be és 1974-ben publikálta, bizonyítva ezzel Crispin Nash-Williams 1966-os sejtését, amit tőle függetlenül L. W. Beineke és Michael D. Plummer is megfogalmazott.[9] Fleischner cikkének kritikájában Nash-Williams azt írta, megoldott „egy jól ismert problémát, ami éveken át dacolt a többi gráfelmélész leleményességével”.[10]

Fleischner eredeti bizonyítása komplikált volt. Václav Chvátal a gráfok szívósságával foglalkozó cikkében megfigyelte, hogy egy k-csúcsösszefüggő gráf négyzete mindenképpen k-szívós; sejtése szerint a 2-szívós gráfoknak rendelkezniük kell Hamilton-körrel, amiből a Fleischner-tétel is következne.[11] Erre a sejtésre később találtak ellenpéldákat,[12] de annak lehetősége, hogy egy gráf korlátos szívóssága implikálhatja Hamilton-körének létezését, a gráfelmélet fontos nyitott kérdése maradt. A Fleischner-tételre és (Chartrand et al. 1974) általi kiterjesztéseire egyszerűbb bizonyítást adott (Říha 1991).[13] további egyszerűsített bizonyítást pedig (Georgakopoulos 2009a).[14]

Fordítás szerkesztés

  • Ez a szócikk részben vagy egészben a Fleischner's theorem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek szerkesztés

  1. ↑ (Fleischner 1976); (Müttel & Rautenbach 2012).
  2. ↑ (Chartrand et al. 1974); (Chartrand, Lesniak & Zhang 2010)
  3. ↑ (Hobbs 1976), answering a conjecture of (Bondy 1971).
  4. ↑ (Underground 1978); (Bondy 1995).
  5. ↑ Thomassen (1978).
  6. ↑ (Georgakopoulos 2009b); (Diestel 2012).
  7. ↑ (Lau 1980); (Parker & Rardin 1984).
  8. ↑ (Parker & Rardin 1984); (Hochbaum & Shmoys 1986).
  9. ↑ (Fleischner 1974). A korábbi sejtéseket lásd Fleischnernél és itt: (Chartrand, Lesniak & Zhang 2010).
  10. ↑ MR0332573.
  11. ↑ (Chvátal 1973); (Bondy 1995).
  12. ↑ Bauer, Broersma & Veldman (2000).
  13. ↑ (Bondy 1995); (Chartrand, Lesniak & Zhang 2010).
  14. ↑ (Chartrand, Lesniak & Zhang 2010); (Diestel 2012).

Elsődleges források szerkesztés

Másodlagos források szerkesztés

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Fleischner-tétel&oldid=25467940”