Fleischner-tétel
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Fleischner%27s_theorem.svg/360px-Fleischner%27s_theorem.svg.png)
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.
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 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]- ↑ (Fleischner 1976); (Müttel & Rautenbach 2012).
- ↑ (Chartrand et al. 1974); (Chartrand, Lesniak & Zhang 2010)
- ↑ (Hobbs 1976), answering a conjecture of (Bondy 1971).
- ↑ (Underground 1978); (Bondy 1995).
- ↑ Thomassen (1978).
- ↑ (Georgakopoulos 2009b); (Diestel 2012).
- ↑ (Lau 1980); (Parker & Rardin 1984).
- ↑ (Parker & Rardin 1984); (Hochbaum & Shmoys 1986).
- ↑ (Fleischner 1974). A korábbi sejtéseket lásd Fleischnernél és itt: (Chartrand, Lesniak & Zhang 2010).
- ↑ MR0332573.
- ↑ (Chvátal 1973); (Bondy 1995).
- ↑ Bauer, Broersma & Veldman (2000).
- ↑ (Bondy 1995); (Chartrand, Lesniak & Zhang 2010).
- ↑ (Chartrand, Lesniak & Zhang 2010); (Diestel 2012).
Elsődleges források
[szerkesztés]- Bauer, D.; Broersma, H. J. & Veldman, H. J. (2000), "Not every 2-tough graph is Hamiltonian", Discrete Applied Mathematics 99 (1-3): 317–321, DOI 10.1016/S0166-218X(99)00141-9.
- Bondy, J. A. (1971), "Pancyclic graphs", Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1971), Baton Rouge, Louisiana: Louisiana State University, pp. 167–172.
- Chartrand, G.; Hobbs, Arthur M. & Jung, H. A. et al. (1974), "The square of a block is Hamiltonian connected", Journal of Combinatorial Theory, Series B 16: 290–292, DOI 10.1016/0095-8956(74)90075-6.
- Chvátal, Václav (1973), "Tough graphs and Hamiltonian circuits", Discrete Mathematics 5 (3): 215–228, DOI 10.1016/0012-365X(73)90138-6.
- Fleischner, Herbert (1974), "The square of every two-connected graph is Hamiltonian", Journal of Combinatorial Theory, Series B 16: 29–34, DOI 10.1016/0095-8956(74)90091-4.
- Fleischner, H. (1976), "In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts", Monatshefte für Mathematik 82 (2): 125–149, DOI 10.1007/BF01305995.
- Georgakopoulos, Agelos (2009a), "A short proof of Fleischner's theorem", Discrete Mathematics 309 (23-24): 6632–6634, DOI 10.1016/j.disc.2009.06.024.
- Georgakopoulos, Agelos (2009b), "Infinite Hamilton cycles in squares of locally finite graphs", Advances in Mathematics 220 (3): 670–705, DOI 10.1016/j.aim.2008.09.014.
- Hobbs, Arthur M. (1976), "The square of a block is vertex pancyclic", Journal of Combinatorial Theory, Series B 20 (1): 1–4, DOI 10.1016/0095-8956(76)90061-7.
- Hochbaum, Dorit S. & Shmoys, David B. (1986), "A unified approach to approximation algorithms for bottleneck problems", Journal of the ACM (New York, NY, USA: ACM) 33 (3): 533–550, doi:10.1145/5925.5933, <https://www.researchgate.net/profile/David_Shmoys/publication/220430962_A_unified_approach_to_approximation_algorithms_for_bottleneck_problems/links/57dc685508ae4e6f1846abde.pdf>.
- Lau, H. T. (1980), Finding a Hamiltonian cycle in the square of a block., Ph.D. thesis, Montreal: McGill University. As cited by (Hochbaum & Shmoys 1986).
- Müttel, Janina & Rautenbach, Dieter (2012), "A short proof of the versatile version of Fleischner’s theorem", Discrete Mathematics, DOI 10.1016/j.disc.2012.07.032.
- Parker, R. Garey & Rardin, Ronald L. (1984), "Guaranteed performance heuristics for the bottleneck traveling salesman problem", Operations Research Letters 2 (6): 269–272, DOI 10.1016/0167-6377(84)90077-4.
- Říha, Stanislav (1991), "A new proof of the theorem by Fleischner", Journal of Combinatorial Theory, Series B 52 (1): 117–123, DOI 10.1016/0095-8956(91)90098-5.
- Thomassen, Carsten (1978), "Hamiltonian paths in squares of infinite locally finite blocks", in Bollobás, B., Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), vol. 3, Annals of Discrete Mathematics, Elsevier, pp. 269–277, ISBN 978-0-7204-0843-0, DOI 10.1016/S0167-5060(08)70512-0.
- Underground, Polly (1978), "On graphs with Hamiltonian squares", Discrete Mathematics 21 (3): 323, DOI 10.1016/0012-365X(78)90164-4.
Másodlagos források
[szerkesztés]- Bondy, J. A. (1995), "Basic graph theory: paths and circuits", Handbook of combinatorics, Vol. 1, 2, Amsterdam: Elsevier, pp. 3–110.
- Chartrand, Gary; Lesniak, Linda & Zhang, Ping (2010), Graphs & Digraphs (5th ed.), CRC Press, p. 139, ISBN 9781439826270, <https://books.google.com/books?id=K6-FvXRlKsQC&pg=PA139>.
- Diestel, Reinhard (2012), "10. Hamiltonian cycles", Graph Theory (corrected 4th electronic ed.), <http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch10.pdf>