Fleischner tétele

Fleischner tétele  egy gráfelméleti állítás, amely elégséges feltételt ad ahhoz, hogy egy gráf tartalmazzon Hamilton-ciklust : ha a gráf egy 2 csúcsú gráf , akkor a Hamilton-gráf négyzete . Herbert Fleischnerről nevezték el , aki 1974 -ben publikálta a tétel bizonyítását .

Definíciók és nyilatkozat

Egy irányítatlan G gráf Hamilton-féle, ha olyan ciklust tartalmaz , amely minden csúcson pontosan egyszer halad át. Egy gráf 2 csúcsú, ha nem tartalmaz artikuláló csúcsokat, azaz olyan csúcsokat, amelyek eltávolítása a fennmaradó gráfot szétválasztja. Nem minden 2 csúcshoz kapcsolódó gráf Hamilton-féle. Az ellenpéldák közé tartozik a Petersen-gráf és a teljes kétrészes gráf K 2,3 .

A G gráf négyzete egy olyan G 2  gráf , amelynek ugyanaz a csúcskészlete, mint a G gráfnak , és amelyben két csúcs akkor és csak akkor szomszédos, ha a távolságuk G -ben legfeljebb kettő. Fleischer tétele kimondja, hogy egy véges, 2-es csúcshoz kapcsolódó, három vagy több csúcsú gráf négyzetének mindig Hamilton-félenek kell lennie. Ezzel egyenértékűen bármely 2-csúccsal összefüggő G gráf csúcsai ciklikus sorrendbe rendezhetők úgy , hogy a szomszédos csúcsok G -ben ebben a sorrendben legfeljebb két távolságra legyenek egymástól.

Kiterjesztések

Fleischner tételében egy Hamilton-ciklust úgy lehet korlátozni, hogy három kiválasztott élt tartalmazzon, amelyek két kiválasztott csúcson mennek át [1] [2] .

Amellett, hogy tartalmaz egy Hamilton-ciklust, egy 2 csúcsú G gráf négyzetének Hamilton-összefüggésben kell lennie (ami azt jelenti, hogy van egy Hamilton-útja , amely bármely két kiválasztott csúcsban kezdődik és végződik) és 1-Hamilton-féle (ami azt jelenti, hogy ha eltávolítasz minden csúcsot, a fennmaradó gráf is tartalmazni fog egy Hamilton-ciklust) [3] [4] . A gráfnak vertex- panciklikusnak is kell lennie , ami azt jelenti, hogy bármely v csúcs és bármely k egész szám esetén 3 ≤ k ≤ | V ( G )| van egy k hosszúságú ciklus, amely v -t tartalmaz [5] .

Ha a G gráf nem 2-csúccsal összefüggő, akkor négyzetének lehet Hamilton-ciklusa vagy nem, és annak meghatározása, hogy a gráfnak van-e ilyen ciklusa, NP-teljes feladat [6] [7] .

Egy végtelen gráfnak nem lehet Hamilton-ciklusa, mivel bármelyik ciklus véges, de Carsten Thomassen bebizonyította, hogy abban az esetben, ha G egy végtelen, lokálisan véges, 2-es csúcshoz kapcsolódó gráf egyetlen véggel, akkor G 2 -nek szükségszerűen van egy kétszeresen végtelen hamiltoni út [8] . Általánosabban fogalmazva, ha G lokálisan véges, 2-csúccsal összefüggő, és tetszőleges számú vége van, akkor G2 - nek Hamilton-ciklusa van. Egy kompakt topológiai térben , amelyet úgy alakítunk ki, hogy egy gráfot egyszerű komplexként kezelünk, és a gráf mindkét végéhez adunk egy plusz pontot a végtelenben, a Hamilton-ciklust olyan altérként határozzuk meg, amely homeomorf az euklideszi körrel, és lefedi az összes csúcsot [9 ] [10] .

Történelem

A tétel bizonyítását Herbert Fliashner 1971-ben jelentette be, és 1974-ben publikálta, ezzel megoldva az 1966 -os Nash-Williams sejtést , amelyet L.W. önállóan is megfogalmazott. Bynik és Plummer [11] . Fleischner cikkéről írt áttekintésében Nash-Williams azt írja, hogy megoldott "egy jól ismert problémát, amely több éven át meghiúsította más gráfelméletek találékonyságát" [12] .

Fleischer eredeti bizonyítása nehéz volt. Vaclav Chvatal munkájában, amelyben bevezette a gráf merevségének fogalmát , megjegyezte, hogy a csúcs - k -összefüggésű gráf négyzete szükségszerűen k -merev. Feltételezte, hogy a 2-merev gráfok Hamilton-gráfok, ami Fleischer tételének újabb bizonyításához vezet [13] [7] . Később találtak ellenpéldákat erre a sejtésre [14] , de az a lehetőség, hogy egy véges merevségi határ Hamiltonitásra utalhat, továbbra is fontos nyitott probléma maradt a gráfelméletben. Fleischner tételének és Chartrand, Hobbs, Young és Kapuur [3] kiterjesztésének egyszerűbb bizonyítását adta Riha [15] [7] [4] , a tétel másik egyszerűsített bizonyítását pedig Georgakopoulus [16] [ 4 ] ] [10] .

Jegyzetek

  1. ↑ Fleischner 1976 , p. 125–149.
  2. ↑ Müttel, Rautenbach, 2012 .
  3. ↑ 1 2 Chartrand, Hobbs, Jung, Kapoor, 1974 .
  4. ↑ 1 2 3 Chartrand, Lesniak, Zhang, 2010 .
  5. ↑ Hobbs ( Hobbs (1976 )), válasz Bondy hipotézisére ( Bondy, 1971 ).
  6. ↑ Underground, 1978 .
  7. ↑ 1 2 3 Bondy, 1995 .
  8. ↑ Thomassen (1978) .
  9. ↑ Georgakopoulos, 2009b .
  10. ↑ 12 Diestel , 2012 .
  11. ↑ Fleischner (1974 ). A korábbi hipotézisekhez lásd Fleischner és Chartrand, Lesniak és Zhang ( Chartrand, Lesniak, Zhang (2010 )).
  12. ↑ MR : 0332573 .
  13. ↑ Chvatal, 1973 .
  14. ↑ Bauer, Broersma, Veldman, 2000 .
  15. ↑ Shiha, 1991 .
  16. ↑ Georgakopoulos, 2009a .

Irodalom