Hipohamiltoni gráf

A matematika, azon belül a gráfelmélet területén G gráf akkor hipohamiltoni (hypohamiltonian), azaz „majdnem Hamilton-körös”, ha nem rendelkezik Hamilton-körrel, de tetszőleges csúcsát eltávolítva már lesz benne Hamilton-kör. Hasonlóan, egy hypotraceable, azaz „majdnem Hamilton-utas” gráf nem tartalmaz Hamilton-utat, de bármely n − 1 csúcsból álló részhalmazát Hamilton-út köti össze.^[1]

Történet

A hipohamiltoni gráfokat először (Sousselier 1963) vizsgálta. (Lindgren 1967) a korai cikkek közül (Gaudin, Herz & Rossi 1964)-t és (Busacker & Saaty 1965)-t említi, további korai munka a (Herz, Duby & Vigué 1967).

(Grötschel 1980) a kutatási terület nagy részét a következőképp összegzi: „az ilyen gráfokat taglaló cikkek általában hipohamiltoni vagy hipotraceable gráfok egy-egy új osztályát mutatják be, megmutatva hogy léteznek n rendű ilyen gráfok, vagy hogy különös és meglepő tulajdonságokkal rendelkeznek”.

Alkalmazások

A hipohamiltoni gráfok előfordulnak az utazó ügynök problémájának egészértékű programozási megoldásaiban: bizonyos fajta hipohamiltoni gráfok az „utazóügynök-politóp” hiperlapjait határozzák meg; ez az alak az utazó ügynök problémája lehetséges megoldásai halmazának konvex burka, a hiperlapokat pedig a probléma vágási módszerrel való megoldásában használják.^[2] (Grötschel 1980) megfigyelése szerint egy gráf hipohamiltonisága meghatározásának számítási bonyolultsága, bár nem ismert a pontos értéke, de valószínűleg magas, ezért a hiperlapok megkeresése is nehéz az egészen kicsi hipohamiltoni gráfokén kívül; szerencsére a legkisebb gráfokból nyerhetők ki a legerősebb egyenlőtlenségek, melyeket ez az alkalmazás igényel.^[3]

(Park, Lim & Kim 2007) a hipohamiltonisághoz közel álló fogalmakkal operálva mérik meg a párhuzamos számítástechnika által használt hálózati topológiák hibatűrését.

Tulajdonságok

Minden hipohamiltoni gráf 3-szorosan összefüggő, hiszen két tetszőleges csúcs eltávolítása után egy Hamilton-út marad, ami összefüggő. Léteznek olyan, n-csúcsú hipohamiltoni gráfok, melyek maximális fokszáma n/2, éleik száma pedig kb. n²/4.^[4] Nem ismert, hogy létezik-e négyszeresen összefüggő hypohamiltonian gráf, mint ahogy az sem, hogy létezik-e olyan, amelynek nincs 3 fokú csúcsa. Minden síkbarajzolható hipohamiltoni gráfban van viszont legalább egy olyan csúcs, amelyből csak három él indul ki.^[5]

(Herz, Duby & Vigué 1967) sejtése szerint a hypohamiltonian gráfok girthparamétere 5 vagy több, de ezt cáfolta (Thomassen 1974b), aki talált 3 és 4 bőségű ellenpéldákat is.

Az 1970-es évek elején ismert hypohamiltonian gráfok többnyire a Petersen-gráf általánosításaként, illetve Chvátal flip-flopjainak^[6] segítségével álltak elő, és egyikük sem volt síkbarajzolható. Ez motiválta Chvátalt, amikor felvetette, hogy léteznek-e egyáltalán síkbarajzolható hypohamiltonian gráfok ((Chvátal, Klarner & Knuth 1972) 5 dollárt ajánlott fel annak, aki konstruál egyet) és ha igen, vannak-e köztük 3-regulárisak.

Az első síkbarajzolható hypohamiltonian gráfot a Grinberg-tétel felhasználásával 1976-ban találta (Thomassen 1976), ennek 105 csúcsa volt; talált 3, 4 és 5 bőségű ilyen gráfokat és megmutatta, hogy végtelen sok létezik belőlük. 1979-ben (Hatzel 1979) talált egy 57 csúcsú hypohamiltonian síkgráfot. 1993-ban (Holton & Sheehan 1993) tette fel a kérdést, hogy létezik-e ennél kisebb hypohamiltonian síkgráf. (Zamfirescu & Zamfirescu 2007) 48 csúcsú példát, (Wiener & Araya 2009) 42 csúcsút találtak, az eddigi legkisebbet pedig, 40 csúccsal, (Jooyandeh et al. 2013), a Grinberg-tétel alapján végzett számítógépes kereséssel.

2011-ig nem volt ismert, hogy minden elegendően nagy n-re létezik-e n csúcsú hypohamiltonian, illetve hypotraceable síkgráf. (Wiener & Araya 2011) megmutatta, hogy minden n ≥ 76 esetén létezik n csúcsú síkbarajzolható hypohamiltonian gráf, illetve minden n ≥ 180 esetén létezik n csúcsú síkbarajzolható hypotraceable gráf. Ezeket a becsléseket (Jooyandeh et al. 2013) 2014-ben 42-re, illetve 156-ra javította. A legkisebb ismert síkbarajzolható hypotraceable gráf 138 csúcsból áll, (Wiener 2016) almost hypohamiltonian gráfból kiinduló konstrukciója alapján.

A 3-reguláris, síkbarajzolható, hypohamiltonian gráfok közül az elsőt (Thomassen 1981) találta, ennek 94 csúcsa van. 2011-ig nem is sikerült ennél kisebb példát találni és az sem volt ismert, hogy kellően nagy páros n-ekre mindig létezik-e n csúcsú 3-reguláris, hypohamiltonian síkgráf. Mindkét kérdés (Holton & Sheehan 1993) cikkében még a megoldatlan problémák között szerepel. (Aldred et al. 2000) cikkéből azonban következett, hogy nem létezik 42 vagy kevesebb csúcsú ilyen gráf. 2011-ben mindkét kérdést megválaszolta (Wiener & Araya 2011): bemutatott egy 70 csúcsú 3-reguláris hypohamiltonian síkgráfot, ami jelenleg is a legkisebb ismert ilyen tulajdonságú gráf és bizonyította, hogy n ≥ 86 esetén mindig létezik n csúcsú 3-reguláris hypohamiltonian síkgráf; utóbbi korlátot (Zamfirescu 2015) 74-re javította.

Minden páros n ≥ 356 esetre létezik 3-reguláris, síkbarajzolható, hypotraceable gráf (sőt: poliédergráf), ahogy azt (Araya & Wiener 2011) megmutatta.

Ha egy 3-reguláris gráfnak van Hamilton-köre, élei kiszínezhetők három színnel: a Hamilton-kör éleit váltakozó színekkel kiszínezzük (ezt megtehetjük, mert a kézfogás-lemma miatt páros a hosszúsága), a maradék élekre pedig felhasználjuk a harmadik színt. Így aztán egyetlen snarknak (összefüggő, hídmentes, 3-reguláris gráf, 4-es kromatikus számmal) sem lehet Hamilton-köre, és számos ismert snark hipohamiltoni. Minden hipohamiltoni snark ún. bikritikus: bármely két csúcsát eltávolítva a maradék részgráf éleinek színezéséhez három szín elegendő.^[7] A részgráf 3-színezése egyszerűen megadható: egy csúcs eltávolításával a maradék csúcsok Hamilton-kört alkotnak. A második csúcs eltávolításával a körből egy út marad, melynek éleit két színnel váltakozva kiszínezhetjük. A maradék élek párosítást alkotnak, ezért a harmadik szín elegendő hozzájuk.

Egy 3-reguláris gráf 3-színezésének a színosztályai olyan három párosítást alkotnak, melyben minden él pontosan egy párosításhoz tartozik.. A hipohamiltoni snarkoknak nincs ilyen párosításuk, de (Häggkvist 2007) sejtése szerint éleik hat párosításba oszthatók oly módon, hogy minden él pontosan két párosításba tartozzon. Ez a Berge–Fulkerson-sejtés speciális esete, mely kimondja, hogy bármely snarknak hat ilyen tulajdonságú párosítása van.

A hipohamiltoni gráfok nem lehetnek párosak: egy páros gráfban egy csúcs törlésével csak akkor jön létre Hamilton-körű részgráf, ha a gráf két színosztálya közül a nagyobbikba tartozik. Minden páros gráf előáll azonban valamely hipohamiltoni gráf feszített részgráfjaként.^[8]

Hatzel-gráf, egy 57 csúcsú síkbarajzolható hipohamiltoni gráf 4-es girthszel
48-Zamfirescu gráf, egy 48 csúcsú síkbarajzolható hipohamiltoni gráf 4-es girthszel
Wiener-Araya-gráf, az ismert legkisebb síkbarajzolható hipohamiltoni gráf, 42 csúccsal és 4-es girthszel

Példák

A legkisebb hypohamiltonian gráf a Petersen-gráf (Herz, Duby & Vigué 1967). Általánosabban, a GP(n,2) általánosított Petersen-gráf akkor hypohamiltonian, amikor n kongruens 5 (mod 6);^[9] maga a Petersen-gráf az n = 5 esetben áll elő.

(Lindgren 1967) talált egy másik végtelen hipohamiltoni gráfosztályt, melyben a csúcsok száma kongruens 4 (mod 6). Lindgren konstrukciója egy 3 (mod 6) hosszúságú körből és egyetlen központi csúcsból áll; a központi csúcsot összeköti a kör minden harmadik csúcsával (ezeket nevezi küllőknek) és a küllő-végpontoktól kettő-kettő távolságra lévő csúcsokat pedig egymással. Lindgren konstrukciója esetében is a legkisebb előállítható gráf a Petersen-gráf.

További végtelen családokat ír le (Bondy 1972), (Doyen & van Diest 1975) és (Gutt 1977).

Leszámlálás

Václav Chvátal 1973-as bizonyítása szerint elegendően nagy n-re létezik n csúcsú hipohamiltoni gráf. A későbbi felfedezéseket is figyelembe véve,^[10] jelenlegi tudásunk szerint az „elegendően nagy” azt jelenti, hogy minden n ≥ 18 értékre léteznek ilyen gráfok. A legfeljebb 17 csúcsú hipohamiltoni gráfok teljes listája ismert:^[11] ezek a 10 csúcsú Petersen-gráf, a (Herz 1968) számítógépes keresése által fellelt 13, illetve 15 csúcsú gráf és négy 16 csúcsú gráf. Legalább tizenhárom 18 csúcsú hipohamiltoni gráf létezik. (Chvátal 1973) flip-flop módszerét a Petersen-gráfra és a virág-snarkra alkalmazva megmutatható, hogy a hypohamiltonian gráfok, azon belül is a hypohamiltonian snarkok száma a csúcsok számának exponenciális függvényében növekszik.^[12]

Hypotraceable gráfok

Az első, 40 csúcsú hypotraceable gráfot Horton találta 1976-ban (Thomassen 1976), az eddigi legkisebb, 34 csúcsú hypotraceable gráf felfedezése (Thomassen 1976) érdeme. A legkisebb hypotraceble gráf méretére nincs jó alsó becslés, részben azért, mert ezeket a gráfokat eddig Thomassen két módszerét felhasználva hypohamiltonian gráfokból állították elő. Az ugyanakkor (Jooyandeh et al. 2013) alapján ismert, hogy az n ≥ 42 esetekre létezik n csúcsú hypotraceable gráf.

Általánosítások

A hipohamiltoni és hypotraceable gráfok irányított gráf-analógiáival több szerző is foglalkozott már.^[13]

A hipohamiltoni gráfok egy ekvivalens definíciója szerint ezek a gráfok, melyek leghosszabb köre n − 1 hosszúságú és az összes leghosszabb kör metszete üres. (Menke, Zamfirescu & Zamfirescu 1998) azokat a gráfokat vizsgálta, melyekben a leghosszabb körök metszete szintén üres, de leghosszabb kör rövidebb n − 1-nél. (Herz 1968) úgy definiálja egy gráf cyclability paraméterét, mint az a legnagyobb k szám, melyre bármely k csúcs ugyanabba a körbe tartozik; a hypohamiltonian gráfok pontosan azok a gráfok, melyek cyclability paramétere n − 1. Hasonlóan (Park, Lim & Kim 2007) definíciója szerint egy gráf ƒ-fault hamiltonian (ƒ hibával hamiltoni), ha a legfeljebb ƒ csúcs eltávolításával kapott részgráfnak van Hamilton-köre. (Schauerte & Zamfirescu 2006) azokat a gráfokat vizsgálja, melyekben a cyclability értéke n − 2.

Foglalkoznak továbbá almost hypohamiltonian és almost hypotraceable gráfokkal is.

Fordítás

Ez a szócikk részben vagy egészben a Hypohamiltonian graph 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

↑ (Kapoor, Kronk & Lick 1968); (Kronk 1969); (Grünbaum 1974); (Thomassen 1974a).
↑ (Grötschel 1977); (Grötschel 1980); (Grötschel & Wakabayashi 1981).
↑ (Goemans 1995).
↑ (Thomassen 1981).
↑ (Thomassen 1978).
↑ (Chvátal 1973)
↑ (Steffen 1998); (Steffen 2001).
↑ (Collier & Schmeichel 1977).
↑ (Robertson 1969) igazolta, hogy ezeknek a gráfoknak nincs Hamilton-körük, pedig egyszerűen ellenőrizhető, hogy az egy csúcs kitörlésével kapott gráfoknak viszont van. Lásd (Alspach 1983) munkáját a Hamilton-kör nélküli általánosított Petersen-gráfok osztályozásáról.
↑ (Thomassen 1974a); (Doyen & van Diest 1975).
↑ (Aldred, McKay & Wormald 1997). Lásd még (A141150 sorozat az OEIS-ben).
↑ (Skupień 1989); (Skupień 2007).
↑ (Fouquet & Jolivet 1978); (Grötschel & Wakabayashi 1980); (Grötschel & Wakabayashi 1984); (Thomassen 1978).

Aldred, R. A.; McKay, B. D. & Wormald, N. C. (1997), "Small hypohamiltonian graphs", J. Combinatorial Math. Combinatorial Comput. 23: 143–152, <http://cs.anu.edu.au/people/bdm/papers/hypo.pdf>.
Aldred, R. A.; Bau, S. & Holton, D. A. et al. (2000), "Nonhamiltonian 3-connected cubic planar graphs", SIAM Journal on Discrete Mathematics 13: 25–32, <https://users.cecs.anu.edu.au/~bdm/papers/c4cp.pdf>.
Alspach, B. R. (1983), "The classification of Hamiltonian generalized Petersen graphs", Journal of Combinatorial Theory, Series B 34 (3): 293–312, DOI 10.1016/0095-8956(83)90042-4.
Araya, M. & Wiener, G. (2011), "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs", The Electronic Journal of Combinatorics 18 (1), <http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/pdf>.
Bondy, J. A. (1972), "Variations of the Hamiltonian theme", Canadian Mathematical Bulletin 15: 57–62, DOI 10.4153/CMB-1972-012-3.
Busacker, R. G. & Saaty, T. L. (1965), Finite Graphs and Networks, McGraw-Hill.
Chvátal, V. (1973), "Flip-flops in hypo-Hamiltonian graphs", Canadian Mathematical Bulletin 16: 33–41, DOI 10.4153/CMB-1973-008-9.
Chvátal, V.; Klarner, D. A. & Knuth, D. E. (1972), Selected Combinatorial Research Problems, Tech. Report STAN-CS-72-292, Computer Science Department, Stanford University, <http://i.stanford.edu/pub/cstr/reports/cs/tr/72/292/CS-TR-72-292.pdf>.
Collier, J. B. & Schmeichel, E. F. (1977), "New flip-flop constructions for hypohamiltonian graphs", Discrete Mathematics 18 (3): 265–271, DOI 10.1016/0012-365X(77)90130-3.
Doyen, J. & van Diest, V. (1975), "New families of hypohamiltonian graphs", Discrete Mathematics 13 (3): 225–236, DOI 10.1016/0012-365X(75)90020-5.
Fouquet, J.-L. & Jolivet, J. L. (1978), "Hypohamiltonian oriented graphs", Cahiers Centre Études Rech. Opér. 20 (2): 171–181.
Gaudin, T.; Herz, P. & Rossi (1964), "Solution du problème No. 29", Rev. Franç. Rech. Opérationnelle 8: 214–218.
Goemans, Michel X. (1995), "Worst-case comparison of valid inequalities for the TSP", Mathematical Programming 69 (1–3): 335–349, DOI 10.1007/BF01585563.
Grötschel, M. (1977), "Hypohamiltonian facets of the symmetric travelling salesman polytope", Zeitschrift für Angewandte Mathematik und Mechanik 58: 469–471.
Grötschel, M. (1980), "On the monotone symmetric traveling salesman problem: hypohamiltonian/hypotraceable graphs and facets", Mathematics of Operations Research 5 (2): 285–292, DOI 10.1287/moor.5.2.285.
Grötschel, M. & Wakabayashi, Y. (1980), "Hypohamiltonian digraphs", Methods of Operations Research 36: 99–119.
Grötschel, M. & Wakabayashi, Y. (1981), "On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets", Discrete Mathematics 24: 43–59, DOI 10.1016/0012-365X(81)90021-2.
Grötschel, M. & Wakabayashi, Y. (1984), "Constructions of hypotraceable digraphs", in Cottle, R. W.; Kelmanson, M. L. & Korte, B., Mathematical Programming (Proc. International Congress, Rio de Janeiro, 1981), North-Holland.
Grünbaum, B. (1974), "Vertices missed by longest paths or circuits", Journal of Combinatorial Theory, Series A 17: 31–38, DOI 10.1016/0097-3165(74)90025-9.
Gutt, S. (1977), "Infinite families of hypohamiltonian graphs", Académie Royale de Belgique, Bulletin de la Classe des Sciences, Koninklijke Belgische Academie, Mededelingen van de Klasse der Wetenschappen, 5e Série 63 (5): 432–440.
Häggkvist, R. (2007), "Problem 443. Special case of the Fulkerson Conjecture", in Mohar, B.; Nowakowski, R. J.; West, D. B., Research problems from the 5th Slovenian Conference (Bled, 2003), Discrete Mathematics 307 (3–5): 650–658, doi:10.1016/j.disc.2006.07.013.
Hatzel, W. (1979), "Ein planarer hypohamiltonscher Graph mit 57 Knoten", Math. Ann. 243 (3): 213–216, DOI 10.1007/BF01424541.
Herz, J. C. (1968), "Sur la cyclabilité des graphes", Computers in Mathematical Research, North-Holland, pp. 97–107.
Herz, J. C.; Duby, J. J. & Vigué, F. (1967), "Recherche systématique des graphes hypohamiltoniens", in Rosenstiehl, P., Theory of Graphs: International Symposium, Rome 1966, Paris: Gordon and Breach, pp. 153–159.
Jooyandeh, Mohammadreza; McKay, Brendan D. & Östergård, Patric R. J. et al. (2013), Planar Hypohamiltonian Graphs on 40 Vertices.
Holton, D. A. & Sheehan, J. (1993), Hypohamiltonian graphs, The Petersen Graph, Cambridge University Press.
Kapoor, S. F.; Kronk, H. V. & Lick, D. R. (1968), "On detours in graphs", Canadian Mathematical Bulletin 11: 195–201, DOI 10.4153/CMB-1968-022-8.
Kronk, H. V. (1969), Klee, V., ed., "Does there exist a hypotraceable graph?", American Mathematical Monthly (Mathematical Association of America) 76 (7): 809–810, DOI 10.2307/2317879.
Lindgren, W. F. (1967), "An infinite class of hypohamiltonian graphs", American Mathematical Monthly (Mathematical Association of America) 74 (9): 1087–1089, DOI 10.2307/2313617.
Máčajová, E. & Škoviera, M. (2007), "Constructing hypohamiltonian snarks with cyclic connectivity 5 and 6", Electronic Journal of Combinatorics 14 (1): R14, <http://www.combinatorics.org/Volume_14/Abstracts/v14i1r18.html>.
Menke, B.; Zamfirescu, T. I. & Zamfirescu, C. M. (1998), "Intersections of longest cycles in grid graphs", Journal of Graph Theory 25 (1): 37–52, DOI 10.1002/(SICI)1097-0118(199705)25:1<37::AID-JGT2>3.0.CO;2-J.
Mohanty, S. P. & Rao, D. (1981), "A family of hypo-hamiltonian generalized prisms", Combinatorics and Graph Theory, vol. 885, Lecture Notes in Mathematics, Springer-Verlag, pp. 331–338, DOI 10.1007/BFb0092278.
Park, J.-H.; Lim, H.-S. & Kim, H.-C. (2007), "Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements", Theoretical Computer Science 377 (1–3): 170–180, DOI 10.1016/j.tcs.2007.02.029.
Robertson, G. N. (1969), Graphs minimal under girth, valency and connectivity constraints, Ph. D. thesis, Waterloo, Ontario: University of Waterloo.
Schauerte, Boris & Zamfirescu, C. T. (2006), "Regular graphs in which every pair of points is missed by some longest cycle", An. Univ. Craiova Ser. Mat. Inform. 33: 154–173, <http://czamfirescu.tricube.de/CTZamfirescu-02.pdf>.
Skupień, Z. (1989), "Exponentially many hypohamiltonian graphs", Graphs, Hypergraphs and Matroids III (Proc. Conf. Kalsk 1988), Zielona Góra: Higher College of Engineering, pp. 123–132. As cited by (Skupień 2007).
Skupień, Z. (2007), "Exponentially many hypohamiltonian snarks", 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, vol. 28, Electronic Notes in Discrete Mathematics, pp. 417–424, DOI 10.1016/j.endm.2007.01.059.
Sousselier, R. (1963), Berge, C., ed., "Problème no. 29: Le cercle des irascibles", Rev. Franç. Rech. Opérationnelle 7: 405–406.
Steffen, E. (1998), "Classification and characterizations of snarks", Discrete Mathematics 188 (1–3): 183–203, DOI 10.1016/S0012-365X(97)00255-0.
Steffen, E. (2001), "On bicritical snarks", Math. Slovaca 51 (2): 141–150.
Thomassen, Carsten (1974a), "Hypohamiltonian and hypotraceable graphs", Discrete Mathematics 9: 91–96, DOI 10.1016/0012-365X(74)90074-0.
Thomassen, Carsten (1974b), "On hypohamiltonian graphs", Discrete Mathematics 10 (2): 383–390, DOI 10.1016/0012-365X(74)90128-9.
Thomassen, Carsten (1976), "Planar and infinite hypohamiltonian and hypotraceable graphs", Discrete Mathematics 14 (4): 377–389, DOI 10.1016/0012-365X(76)90071-6.
Thomassen, Carsten (1978), "Hypohamiltonian graphs and digraphs", Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), vol. 642, Lecture Notes in Mathematics, Berlin: Springer-Verlag, pp. 557–571.
Thomassen, Carsten (1981), "Planar cubic hypo-Hamiltonian and hypotraceable graphs", Journal of Combinatorial Theory, Series B 30: 36–44, DOI 10.1016/0095-8956(81)90089-7.
Wiener, Gábor & Araya, Makoto (2009), The ultimate question.
Wiener, Gábor & Araya, Makoto (2011), "On planar hypohamiltonian graphs", Journal of Graph Theory 67 (1): 55–68, DOI 10.1002/jgt.20513.
Wiener, Gábor (2016), "On constructions of hypotraceable graphs", Electronic Notes in Discrete Mathematics 54: 127–132, doi:10.1016/j.endm.2016.09.023, <http://real.mtak.hu/40505/1/barcelona16.pdf>.
Zamfirescu, C. T. (2015), "On Hypohamiltonian and Almost Hypohamiltonian Graphs", Journal of Graph Theory 79 (1): 63–81, DOI 10.1002/jgt.21815.
Zamfirescu, C. T. & Zamfirescu, T. I. (2007), "A planar hypohamiltonian graph with 48 vertices", Journal of Graph Theory 55 (4): 338–342, DOI 10.1002/jgt.20241.