Hipohamiltoni gráf

A gráfelméletben egy G gráfot hipo -Hamilton-nak mondunk , ha magának a gráfnak nincs Hamilton-ciklusa , de bármely olyan gráf, amelyet G -ből egy csúcs eltávolításával kapunk, Hamilton -féle .

Történelem

A hypo-Hamiltoni gráfokat először Sousselier tanulmányozta 1963-ban [2] . Lindgren [1] Gaudint, Hertz-et és Rossit (1964) [3] , valamint Busaker-t és Saaty-t (1965) [4] idézi kiegészítő anyagként a témában. Egy másik korai munka Hertz, Duby és Vige 1967-es tanulmánya [5] .

Grötschel [6] az ezen a területen végzett munka nagy részét a következő kijelentéssel foglalta össze: „Az ezekről a gráfokról szóló írások... általában a hipo-hamiltoni és a hiporajzolt gráfok új osztályait tárják fel, és megmutatják, hogy néhány n esetében léteznek ilyen gráfok, vagy hogy furcsa és váratlan tulajdonságaik vannak."

Alkalmazások

Hipo-Hamilton gráfok jelennek meg az utazó eladó probléma egész megoldásaiban - egy bizonyos típusú hypo-Hamilton gráfok az utazó eladó poliéder oldalait határozzák meg , amely test az utazó eladó probléma lehetséges megoldásainak halmazának konvex teste , és ezek a fazetok a Gomory-algoritmussal [7] [6] [8] való problémamegoldáskor vágási síkmódszerekhez használhatók . Grötschel megjegyezte [6] , hogy a gráf hipo-hamiltoni-e meghatározásának számítási bonyolultsága , bár nem ismert, nagynak tűnik, ami megnehezíti az ilyen típusú aspektusok megtalálását, kivéve a kis méretű hipo-Hamilton-gráfok által meghatározott aspektusokat. . Szerencsére a legkisebb grafikonok vezetnek a legerősebb egyenlőtlenségekhez egy adott probléma esetén [9] .

A hipo-Hamiltonitáshoz hasonló fogalmakat használt Park, Lim és Kim [10] a párhuzamos számítási hálózati topológiák hibatűrésének mérésére .

Tulajdonságok

Bármely hipo-Hamilton gráfnak 3-as csúcshoz kell kapcsolódnia , mivel bármely két csúcs eltávolítása egy összefüggő Hamilton-útvonalat hagy hátra (az egyik csúcsot eltávolított gráfnak Hamilton-ciklusa van, a második csúcs eltávolítása pedig Hamilton-útvonalat ad). Léteznek n csúcsú hipo-Hamilton gráfok , amelyekben egy csúcs maximális foka n /2, és amelyekben körülbelül n 2 /4 él van [11] .

Hertz, Duby és Vige úgy sejtették [5] , hogy minden hipo-Hamilton-gráf 5-ös vagy nagyobb kerülettel rendelkezik , de a sejtést Thomassen [12] cáfolta , és talált példákat a 3. és 4. kerületre. Egy ideig nem lehetett tudni, hogy A hipo-Hamilton-gráfok lehetnek síkbeliek is , de ma már ismert néhány példa ilyen gráfokra [13] , és a legkisebb gráfnak 40 csúcsa van [14] . Minden síkbeli hipo-Hamilton gráfnak van legalább egy csúcsa, amelynek csak három beeső éle van [15] .

Ha egy 3-homogén Hamilton-gráf, annak élei három színnel színezhetők - a Hamilton-ciklus mentén felváltva két színnel színezzük az éleket (amelynek a kézfogási lemma szerint egyenletes hosszúságúnak kell lennie ), és az összes fennmaradó élt színezzük a harmadik szín. Így az összes snark , vagyis a négy színt igénylő híd nélküli gráf nem Hamilton-féle kell, hogy legyen, és sok ismert snark hipo-Hamilton-féle. Bármely hipokamiltoni snark bikritikus – bármely két csúcs törlésével egy részgráf marad, amelynek élei három színnel színezhetők [16] [17] . Ennek a részgráfnak a háromszínű színezése könnyen leírható - a csúcs eltávolítása után a fennmaradó rész egy Hamilton-ciklust tartalmaz. A második csúcs eltávolítása után a ciklus olyan pályává válik, amelynek élei felváltva két színnel színezhetők. A fennmaradó élek egy illőt alkotnak , és ezek az élek mindegyike kiszínezhető a harmadik színnel.

Egy 3-homogén gráf bármely 3 színű élszínezésének színosztályai három egyezést alkotnak úgy, hogy minden él pontosan egy illesztéshez tartozik. A hypo-Hamilton-féle snarkoknak nincs ilyen típusú egyező dekompozíciója, de Heggquist [18] úgy sejtette, hogy bármely hypo-Hamiltoni snark élei hat illeszkedést képezhetnek úgy, hogy minden él pontosan két egyezéshez tartozik. Ez egy speciális esete a Berge–Fulkerson-sejtésnek, amely szerint bármely snarknak hat egyezése van ezzel a tulajdonsággal.

A hipo-Hamilton-gráfok nem lehetnek kétrészesek – egy kétrészes gráfban egy csúcs csak akkor távolítható el, hogy Hamilton-részgráfot képezzen, ha az a gráf két színosztálya közül a nagyobbikhoz tartozik. Azonban bármely kétrészes gráf valamilyen hipo-Hamilton-gráf generált részgráfjaként fordul elő [19] .

Példák

A legkisebb hipo-Hamilton-gráf a Petersen-gráf [5] . Általánosabban, egy általánosított Petersen-gráf GP( n ,2) hipo-Hamilton-gráf, ha n értéke 5 (mod 6) [20] . A Petersen-gráf reprezentálja ezt a konstrukciót n  = 5-tel.

Lindgren [1] talált egy másik végtelen számú hipo-Hamiltoni gráfot, amelyben a csúcsok száma 4 (mod 6). Lindgren konstrukciója egy 3 hosszúságú ciklusból (mod 6) és egy központi csúcsból áll. A központi csúcsot a ciklus minden harmadik csúcsához egy él köti össze, amit ő küllőnek nevez, és a küllő végső csúcsától két pozícióban lévő csúcsok kapcsolódnak egymáshoz. A Lindgren-konstrukció legkisebb képviselője ismét a Petersen-gráf.

További végtelen családokat adott Bondy [21] , Doyen és van Diest [22] , valamint Gutt [23] .

Felsorolás

Vaclav Chvatal 1973-ban bebizonyította, hogy minden kellően nagy n esetén vannak n csúcsú hipo-Hamiltonok. A későbbi felfedezéseket [24] [22] figyelembe véve , ma már "elég nagy szám" ismert, így minden n ≥ 18- ra léteznek ilyen gráfok . A legfeljebb 17 csúcsot tartalmazó hipo-Hamilton-gráfok teljes listája ismert . 25] - ez a 10 csúcsos Petersen-gráf, a Hertz által számítógépes kereséssel [26] talált 13 és 15 csúcsú gráfok és négy 16 csúcsú gráf. Legalább tizenhárom hipo-Hamilton-gráf létezik 18 csúcsgal. Chvatal trigger módszerét [27] a Petersen-gráfra és a virágsnarkra alkalmazva kimutatható, hogy a hipo-Hamilton-gráfok száma, pontosabban a hipo-Hamilton-snarkok száma a csúcsok számának exponenciálisaként növekszik. [28] [29] .

Általánosítások

A teoretikusok hiporajzolt gráfokat is tanulmányoznak , olyan gráfokat, amelyek nem tartalmaznak Hamilton-pályát, de amelyekben bármely n  − 1 csúcsból álló részhalmaz összekapcsolható egy útvonallal [30] [31] [32] [24] . A hipo-Hamiltonitás és a hiporajzolhatóság hasonló definícióit javasolták egyes szerzők irányított gráfokhoz [33] [34] [35] [15] .

A hipo-Hamilton-gráfok ekvivalens definíciója az, hogy leghosszabb ciklusaik n  − 1 hosszúak, és a leghosszabb ciklusok metszéspontja üres. Menke és Zamfirescu [36] olyan gráfokat tanulmányozott, amelyeknél a leghosszabb ciklusok metszéspontja üres, de ezeknek a ciklusoknak a hossza kisebb, mint n  − 1. Hertz [26] a gráf ciklusképességét a legnagyobb számként definiálta . k úgy, hogy bármely k csúcs egy ciklushoz tartozik. A hipo-Hamilton gráfok pontosan olyan gráfok, amelyek ciklikussága n  − 1. Hasonlóan, Park, Lim és Kim [10] egy gráfot ƒ -stabilan nem Hamilton-nak definiált, ha legfeljebb ƒ csúcsok eltávolítása Hamilton részgráfot eredményez. Schauerte és Zamfirescu [37] n  − 2 ciklikusságú gráfokat vizsgált .

Jegyzetek

  1. ↑ 1 2 3 Lindgren, 1967 .
  2. ↑ Sousselier, 1963 .
  3. ↑ Gaudin, Herz, Rossi, 1964 .
  4. ↑ Busacker, Saaty, 1965 .
  5. ↑ 1 2 3 Herz, Duby, Vigué, 1967 .
  6. ↑ 1 2 3 Grötschel, 1980 .
  7. ↑ Grotschel, 1977 .
  8. ↑ Grötschel, Wakabayashi, 1981 .
  9. ↑ Goemans, 1995 .
  10. ↑ 12 Park, Lim, Kim, 2007 .
  11. ↑ Thomassen, 1981 .
  12. ↑ Thomassen, 1974b .
  13. ↑ A síkbeli hipo-Hamilton-gráfok létezésének problémáját nyitott kérdésként tette fel Václav Chvátal ( Chvátal 1973 ), és Chvátal, Klarner és Knuth egy csoportja 5 dolláros díjat ígért egy ilyen gráf megtalálójának ( Chvátal, Klarner , Knuth 1972 ). Thomassen ( Thomassen 1976 ) Greenberg tételét használta a 3., 4. és 5. kerületű síkbeli hipo-Hamilton-gráfok megtalálásához, és kimutatta, hogy végtelen sok síkbeli hipo-Hamilton-gráf létezik.
  14. ↑ Juyande, McKay, Östergaard és Pettersson ( Jooyandeh, McKay, et al. 2013 ) találta számítógépes keresés és Greenberg-tétel segítségével. Ezt megelőzően 42, 57 és 48 csúcsú kis síkbeli hipo-Hamilton gráfokat találtak Wiener és Araya ( Wiener, Araya 2009 ), Hatzel ( Hatzel 1979 ) és Zamfirescu ( Zamfirescu, Zamfirescu 2007 ).
  15. ↑ 12 Thomassen , 1978 .
  16. ↑ Steffen, 1998 .
  17. ↑ Steffen, 2001 .
  18. ↑ Häggkvist, 2007 .
  19. ↑ Collier, Schmeichel, 1977 .
  20. ↑ Robertson ( 1969 ) bebizonyította, hogy ezek a gráfok nem Hamilton-gráfok, bár könnyen ellenőrizhető, hogy egy csúcs eltávolítása Hamilton-gráfot eredményez. Lásd Alspach írását ( Alspach 1983 ) a nem-hamiltoni általánosított Petersen-gráfok osztályozásáról.
  21. ↑ Bondy, 1972 .
  22. ↑ 12 Doyen , van Diest, 1975 .
  23. ↑ Gutt, 1977 .
  24. ↑ 12 Thomassen, 1974a .
  25. ↑ Aldred, McKay, Wormald, 1997 . Lásd még az OEIS A141150 szekvenciáját .
  26. ↑ Herz 12. , 1968 .
  27. ↑ Chvatal, 1973 .
  28. ↑ Skupień, 1989 .
  29. ↑ Skupień, 2007 .
  30. ↑ Kapoor, Kronk, Lick, 1968 .
  31. ↑ Kronk, 1969 .
  32. ↑ Grünbaum, 1974 .
  33. ↑ Fouquet, Jolivet, 1978 .
  34. ↑ Grötschel, Wakabayashi, 1980 .
  35. ↑ Grötschel, Wakabayashi, 1984 .
  36. ↑ Menke, Zamfirescu, Zamfirescu, 1998 .
  37. ↑ Schauerte, Zamfirescu, 2006 .

Irodalom

Linkek