Hipohamiltonov graf

Hipohamiltonov graf G je v teoriji grafov graf brez Hamiltonovega cikla, pri čemer postane vsak nov graf, ki nastane z odvzemanjem ene točke iz G, Hamiltonov. To mora veljati za vse točke grafa G.[2]

Hipohamiltonov graf na 16-ih točkah, Lindgrenova konstrukcija[1]

ZgodovinaUredi

Hipohamiltonove grafe je najprej raziskoval Sousselier leta 1963 v delu Problèmes plaisants et délectables.[3] Lindgren je leta 1967 skonstruiral neskončno zaporedje hipohamiltonovih grafov.[1] Navedel je članka Gaudina, Herza in Rossija[4] ter Busackra in Saatyja[5] kot zgodnejša članka o tej temi. Še eno zgodnejše delo je članek Herza, Dubyja in Viguéja.[6] Grafi v tem zaporedju imajo vsi število točk enako   za vsako celo število k. Enako zaporedje je neodvisno skonstruiral Sousselier.[6]

Grötschel je leta 1980[7] povzel veliko raziskovalnih dosežkov na tem področju: »Članki, ki se ukvarjajo s temi grafi ... imajo po navadi nove razrede hipohamiltonovih ali hiposledljivih grafov, in kažejo, da za določene rede n takšni grafi res obstajajo ali, da imajo nenavadne in nepričakovane značilnosti.«

UporabeUredi

RačunalništvoUredi

Hipohamiltonovi grafi se pojavljajo v celoštevilskem programiranju pri rešitvah problema trgovskega potnika: določene vrste hipohamiltonovih grafov določajo facete politopa trgovskega potnika, oblike definirane kot konveksna ogrinjača množice možnih rešitev problema trgovskega potnika. Te facete se lahko uporabijo v metodah presečne ravnine za reševanje problema.[8][9][10] Grötschel je leta 1980[11] opazil, da bo računska zahtevnost določanja ali je graf hipohamiltonov, čeprav neznana, verjetno zelo velika, kar bo otežilo oskanje facet takšne vrste razen za tiste, ki jih določajo majhni hipohamiltonovi grafi. K sreči najmnajši grafi vodijo do najmočnejših neenakosti te uporabe.[12]

Koncepte, tesno povezane s hipohamiltonostjo, so leta 2007 uporabili tudi Park, Lim in Kim[13] pri merjenju okvarne odpornosti omrežne topologije za vzporedno računanje.

ZnačilnostiUredi

Vsak hipohamiltonov graf mora biti 3-točkovnopovezan, saj odstranjevanje poljubne točke vodi do Hamiltonovega cikla in poljubnih dveh točk do Hamiltonove poti, ki je povezana. Zaradi tega so posebej zanimivi kubični hipohamiltonovi grafi saj imajo najmanjšo možno velikost (število povezav) za dani red (število točk).[14] Obstaja n-točkovnohipohamiltonovih grafov v katerih je največja stopnja enaka n/2 in v katerih je približno n2/4 povezav.[15]

 
Thomassenov hipohamiltonov graf na 60-ih točkah z notranjim obsegom 3.[16]

Herz, Duby in Vigué so leta 1967[6] domnevali, da ima vsak hipohamiltonov graf notranji obseg enak 5 ali več. To je ovrgel Thomassen leta 1974,[16] ko je našel protiprimera za notranji obseg 3 in 4.

Najmanjša hipohamiltonova grafa z notranjim obsegom 4 in 5 imata 10 točk, z notranjim obsegom 6 ima 25 točk, z notranjim obsegom 7 ima 28 točk.[17]

RavninskostUredi

Nekaj časa ni bilo znano ali je hipohamiltonov graf lahko ravninski, sedaj pa je znanih več primerov. Obstoj ravninskih hipohamiltonovih grafov so kot odprti problem postavili Chvátal,[18] ter Chvátal, Klarner in Knuth leta 1972.[19] Za konstrukcijo takšnega grafa so ponudili nagrado 5 $. Obstajala je tudi domneva, da takšnih grafov ni.[20] Thomassen[21] je leta 1976 uporabil Grinbergsov izrek za iskanje ravninskih hipohamiltonovih grafov z notranjim obsegom 3, 4 in 5, ter pokazal, da obstaja neskončno mnogo ravninskih hipohamiltonovih grafov, od katerih je najmanjši takšen graf na 105-ih točkah.

Najmanjši med njimi ima 40 točk. Našli so ga leta 2013 Jooyandeh, McKay, Östergård in Pettersson[22] s pomočjo računalniškega iskanja določenih družin ravninskih grafov z notranjim obsegom 4 in Grinbergsovega izreka. Pred tem so našli majhne ravninske hipohamiltonove grafe s 57-imi, 48-imi in 42-imi točkami Hatzel (Hatzlov graf)[23], Zamfirescu in Zamfirescu (48-Zamfirescujev graf)[24], ter Wiener in Araja (Wiener-Arajev graf).[25]

Najmanjši ravninski hipohamiltonov graf z notranjim obsegom 5 ima 45 točk.[22]

Najmanjši znani ravninski kubični hipohamiltonov graf ima 70 točk.[26]

Vsak ravninski hipohamiltonov graf ima vsaj eno točko z le tremi incidenčnimi povezavami.[27]

Regularnost in barvanjeUredi

Če je kubični graf Hamiltonov, se lahko njegove povezave pobarvajo s tremi barvami – dve alternirajoči barvi za povezave v Hamiltonovem ciklu (ki mora po lemi o rokovanju imeti sodo dolžino) in tretja barva za vse preostale povezave. Zaradi tega morajo biti vsi snarki, kubični grafi brez mostov, za katere so za barvanje povezav potrebne štiri barve, nehamiltonovi. Mnogo znanih snarkov je taradi tega hipohamiltonovih. Vsak hipohamiltonov snark je bikritičen – če se odstrani poljubni dve točki, ostane podgraf, katerega povezave se lahko pobarvajo le s tremi barvami.[28][29] Barvanje s tremi barvami tega podgrafa se preprosto opiše – po odstranitvi ene točke preostale točke vsebujejo Hamiltonov cikel. Po odstranitvi druge točke ta cikel postane pot, in njene povezave se lahko pobarvajo z izmenjavanjem dveh barv. Preostale povezave tvorijo parjenje in se lahko pobarvajo s tretjo barvo.

Barvni razredi poljubnega barvanja povezav s tremi barvami kubičnega grafa tvorijo tri takšna parjenja, da vsaka povezava pripada točno enemu parjenju. Hipohamiltonovi snarki nimajo particije v parjenje te vrste, in Häggkvist je leta 2007[30] domneval, da se lahko povezave kateregakoli hipohamiltonovega snarka uporabijo za oblikovanje šestih takšnih parjenj, da vsaka povezava pripada točno enemu parjenju. To je posebni primer Berge-Fulkersonove domneve, da ima vsak snark šest parjenj s to značilnostjo.

DvodelnostUredi

Hipohamiltonovi grafi ne morejo biti dvodelni. V dvodelnem grafu se lahko točka izbriše in da Hamiltonov podgraf, če pripada večjemu od dveh barvnih razredov grafa. Vendar se vsak dvodelni graf pojavi kot inducirani podgraf kakšnega hipohamiltonovega grafa.[31]

ZglediUredi

Najmanjši hipohamiltonov graf je Petersenov graf.[4][6] V splošnem je posplošeni Petersenov graf GP(n,2) hipohamiltonov za n enak 5 (mod 6). Petersenov graf je primer te konstrukcije za n = 5. Robertson je leta 1969[32] dokazal, da ti grafi niso Hamiltonovi, pri čemer se lahko neposredno preveri da odstranjevanja ene točke dajo Hamiltonov graf. Klasifikacijo nehamiltonovih posplošenih grafov je dal Alspach.[33]

Lindgren[1] je našel drug neskončni razred hipohamiltonovih grafov v katerih je število točk enako 4 (mod 6). Lindgrenova konstrukcija se sestoji iz cikla dolžine 3 (mod 6) in ene osrednje točke. Osrednja točka je povezana z vsako tretjo točko cikla s povezavami, ki jih je imenoval špice (spokes), točki dve dolžini stran od vsake špice pa sta povezani med seboj. Spet je najmanjši primer njegove konstrukcije Petersenov graf.

Druge neskončne družine so dali Bondy,[14] Doyen in van Diest,[34] ter Gutt.[35]

PreštevanjeUredi

Chvátal je leta 1973 dokazal, da za vsak dovolj velik n obstaja hipohamiltonov graf z n točkami. Kasnejša odkritja[36][34] so dala točnejši pomen za »dovolj velik« in je sedaj znano, da takšni grafi obstajajo za vse n ≥ 18. Znan je celotni seznam neizomorfnih hipohamiltonovih grafov z največ 17-imi točkami[37] (zaporedje A141150 v OEIS):

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 4, 0, (13), ...

To so Petersenov graf na 10-ih točkah, graf na 13-ih točkah in graf na 15-ih točkah, ki ga je z računalniškim iskanjem našel Herz,[38], ter štirje grafi na 16-ih točkah. Na 18-ih točkah obstaja vsaj trinajst neizomorfnih hipohamiltonovih grafov in od teh sta dva kubična grafa.[37] Število kubičnih hipohamiltonovih grafov reda n > 0 je:

0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 1, 0, 3, 0, 1, 0, 100, 0, 34, 0, 1, 0, ...

S pomočjo Chvátalove metode flip-flop[39] na Petersenovem grafu in cvetličnem snarku je mogoče pokazati, da število neizomorfnih hipohamiltonovih grafov in še posebej število neizomorfnih hipohamiltonovih snarkov narašča eksponentno s številom točk.[31][40][41]

PosplošitveUredi

Raziskovali so tudi hiposledljive grafe, grafe, ki ne vsebujejo Hamiltonove poti, vendar takšne, da se lahko vsaka podmnožica n − 1 točk poveže s potjo.[42][43][20][36] Več avtorjev je obravnavalo analogne definicije hipohamiltonosti in hiposledljivosti za usmerjene grafe.[44][45][46][27]

Enakovredna definicija hipohamiltonovih grafov je, da ima njihov najdaljši cikel dolžino n − 1 in da je presek vseh najdaljših ciklov prazen. Menke, Zamfirescu in Zamfirescu[47] so raziskali grafe z enako značilnostjo, da je presek najdaljših ciklov prazen, vendar v katerih je dolžina najdaljšega cikla manjša od n − 1. Herz[38] je definiral cikličnost grafa kot največje takšno število k, da vsaka k točka pripada ciklu. Hipohamiltonovi grafi so ravno grafi s cikličnostjo n − 1. Podobno so Park, Lim in Kim[13] definirali graf, ki je ƒ-okvarnoodporen hamiltonov, če odstranitev največ ƒ točk da Hamiltonov podgraf. Schauerte in Zamfirescu[48] sta raziskovala grafe s cikličnostjo n − 2.

Glej tudiUredi

SkliciUredi

ViriUredi

  • Aldred, R. A.; McKay, Brendan Damien; Wormald, Nicholas Charles (1997), "Small hypohamiltonian graphs" (PDF), J. Combinatorial Math. Combinatorial Comput., 23: 143–152
  • Alspach, Brian Roger (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, MR 0714452
  • Bondy, John Adrian (1972), "Variations of the Hamiltonian theme", Canadian Mathematical Bulletin, 15: 57–62, doi:10.4153/CMB-1972-012-3
  • Busacker, Robert George; Saaty, Thomas Lorie (1965), Finite Graphs and Networks, McGraw-Hill, COBISS 11638617
  • Chvátal, Václav (1973), "Flip-flops in hypo-Hamiltonian graphs", Canadian Mathematical Bulletin, 16: 33–41, doi:10.4153/CMB-1973-008-9, MR 0371722
  • Chvátal, Václav; Klarner, David Anthony; Knuth, Donald Ervin (1972), Selected Combinatorial Research Problems (PDF), Tech. Report STAN-CS-72-292, Computer Science Department, Stanford University
  • Collier, James Bryan; Schmeichel, Edward Fred (1977), "New flip-flop constructions for hypohamiltonian graphs", Discrete Mathematics, 18 (3): 265–271, doi:10.1016/0012-365X(77)90130-3, MR 0543828
  • Doyen, Jean; van Diest, Viviane (1975), "New families of hypohamiltonian graphs", Discrete Mathematics, 13 (3): 225–236, doi:10.1016/0012-365X(75)90020-5, MR 0416979
  • Fouquet, Jean-Luc; Jolivet, J. L. (1978), "Hypohamiltonian oriented graphs", Cahiers Centre Études Rech. Opér., 20 (2): 171–181, MR 0498218
  • Gaudin, T.; Herz, P.; Rossi (1964), "Solution du problème No. 29", Rev. Franç. Rech. Opérationnelle, 8: 214–218
  • Goedgebeur, Jan; Zamfirescu, Carol T. (2016), Improved bounds for hypohamiltonian graphs, arXiv:1602.07171
  • Goemans, Michel Xavier (1995), "Worst-case comparison of valid inequalities for the TSP", Mathematical Programming, 69 (1–3): 335–349, doi:10.1007/BF01585563
  • Grötschel, Martin (1977), "Hypohamiltonian facets of the symmetric travelling salesman polytope", Zeitschrift für Angewandte Mathematik und Mechanik, 58: 469–471
  • Grötschel, Martin (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, JSTOR 3689157
  • Grötschel, Martin; Wakabayashi, Yoshiko (1980), "Hypohamiltonian digraphs", Mathematics of Operations Research, 36: 99–119
  • Grötschel, Martin; Wakabayashi, Yoshiko (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, Martin; Wakabayashi, Yoshiko (1984), "Constructions of hypotraceable digraphs", v Cottle, R. W.; Kelmanson, M. L.; Korte, B. (ur.), Mathematical Programming (Proc. International Congress, Rio de Janeiro, 1981), North-Holland
  • Grünbaum, Branko (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, MR 0349474
  • Gutt, Simone (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, MR 0498243
  • Häggkvist, Roland (2007). "Problem 443. Special case of the Fulkerson Conjecture". V Mohar, Bojan; Nowakowski, R. J.; West, D. B. (ur.). Research problems from the 5th Slovenian Conference (Bled, 2003). Discrete Mathematics. 307 (3–5). str. 650–658. doi:10.1016/j.disc.2006.07.013.
  • Hatzel, Wolfgang (1979), "Ein planarer hypohamiltonscher Graph mit 57 Knoten", Mathematische Annalen, 243 (3): 213–216, doi:10.1007/BF01424541, MR 0548801
  • Herz, J. C. (1968), "Sur la cyclabilité des graphes", Computers in Mathematical Research, North-Holland, str. 97–107, MR 0245461
  • Herz, J. C.; Duby, J. J.; Vigué, F. (1967), "Recherche systématique des graphes hypohamiltoniens", v Rosenstiehl, Pierre (ur.), Theory of Graphs: International Symposium, Rome 1966, Pariz: Gordon and Breach, str. 153–159
  • Jooyandeh, Mohammadreza; McKay, Brendan Damien; Östergård, Patric R. J.; Pettersson, Ville H.; Zamfirescu, Carol T. (2013), Planar Hypohamiltonian Graphs on 40 Vertices, arXiv:1302.2698
  • Kapoor, Šašičand Fatehčand; Kronk, Hudson Van Etten; Lick, Don Raymond (1968), "On detours in graphs", Canadian Mathematical Bulletin, 11: 195–201, doi:10.4153/CMB-1968-022-8, MR 0229543
  • Krnc, Matjaž; Škrekovski, Riste (2015), Izbrana poglavja iz diskretne matematike (PDF), Ljubljana: samozal. R. Škrekovski, COBISS 279674880, ISBN 978-961-92887-5-7
  • Kronk, Hudson Van Etten (1969), Klee, Victor (ur.), "Does there exist a hypotraceable graph?", Research Problems, American Mathematical Monthly, Mathematical Association of America, 76 (7): 809–810, doi:10.2307/2317879, JSTOR 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, JSTOR 2313617, MR 0224501
  • Máčajová, E.; Škoviera, M. (2007), "Constructing hypohamiltonian snarks with cyclic connectivity 5 and 6", Electronic Journal of Combinatorics, 14 (1): R14
  • Menke, B.; Zamfirescu, Tudor I.; Zamfirescu, Carol T. (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
  • McKay, Brendan Damien (2015), Hypohamiltonian planar cubic graphs with girth five, arXiv:1507.07197
  • Mohanty, S. P.; Rao, Daljit (1981), "A family of hypo-hamiltonian generalized prisms", Combinatorics and Graph Theory, Lecture Notes in Mathematics, 885, Springer-Verlag, str. 331–338, doi:10.1007/BFb0092278
  • Park, Jung-Heum; Lim, Hyeong-Seok; Kim, Hee-Chul (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, George Neil (1969), Graphs minimal under girth, valency and connectivity constraints, Ph. D. thesis, Waterloo, Ontario: University of Waterloo
  • Schauerte, Boris; Zamfirescu, Carol 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, MR 2359901
  • Skupień, Zdzislaw (1989), "Exponentially many hypohamiltonian graphs", Graphs, Hypergraphs and Matroids III (Proc. Conf. Kalsk 1988), Zielona Góra: Higher College of Engineering, str. 123–132. Kot navedeno v Skupień (2007)
  • Skupień, Zdzislaw (2007), "Exponentially many hypohamiltonian snarks", 6th Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Electronic Notes in Discrete Mathematics, 28, str. 417–424, doi:10.1016/j.endm.2007.01.059
  • Sousselier, R. (1963), Berge, Claude (ur.), "Problème no. 29: Le cercle des irascibles", Problèmes plaisants et délectables, Rev. Franç. Rech. Opérationnelle, 7: 405–406
  • Steffen, Eckhard (1998), "Classification and characterizations of snarks", Discrete Mathematics, 188 (1–3): 183–203, doi:10.1016/S0012-365X(97)00255-0, MR 1630478
  • Steffen, Eckhard (2001), "On bicritical snarks", Mathematica Slovaca, 51 (2): 141–150, MR 1841443
  • Thomassen, Carsten (1974a), "Hypohamiltonian and hypotraceable graphs", Discrete Mathematics, 9: 91–96, doi:10.1016/0012-365X(74)90074-0, MR 0347682
  • Thomassen, Carsten (1974b), "On hypohamiltonian graphs", Discrete Mathematics, 10 (2): 383–390, doi:10.1016/0012-365X(74)90128-9, MR 0357226
  • Thomassen, Carsten (1976), "Planar and infinite hypohamiltonian and hypotraceable graphs", Discrete Mathematics, 14 (4): 377–389, doi:10.1016/0012-365X(76)90071-6, MR 0422086
  • Thomassen, Carsten (1978), "Hypohamiltonian graphs and digraphs", Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), Lecture Notes in Mathematics, 642, Berlin: Springer-Verlag, str. 557–571, MR 0499523
  • 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, MR 0609592
  • Wiener, Gábor; Araja, Makoto (2009), The ultimate question, arXiv:0904.3012
  • Wiener, Gábor; Araja, Makoto (2011), "On cubic planar hypohamiltonian and hypotraceable graphs", Electronic Journal of Combinatorics, 18 (1): 85
  • Zamfirescu, Carol T.; Zamfirescu, Tudor I. (2007), "A planar hypohamiltonian graph with 48 vertices", Journal of Graph Theory, 55 (4): 338–342, doi:10.1002/jgt.20241

Zunanje povezaveUredi