Wikipedija

Hipohamiltonov graf

Ne zamenjajte za Hamiltonov 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]

Zgodovina uredi

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.«

Uporabe uredi

Računalništvo uredi

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][7][9] Grötschel je leta 1980[7] 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.[10]

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

Značilnosti uredi

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).[12] Obstaja n-točkovnohipohamiltonovih grafov v katerih je največja stopnja enaka n/2 in v katerih je približno n2/4 povezav.[13]

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

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,[14] 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.[15]

Ravninskost uredi

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,[16] ter Chvátal, Klarner in Knuth leta 1972.[17] Za konstrukcijo takšnega grafa so ponudili nagrado 5 $. Obstajala je tudi domneva, da takšnih grafov ni.[18] Thomassen[19] 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[20] 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)[21], Zamfirescu in Zamfirescu (48-Zamfirescujev graf)[22], ter Wiener in Araja (Wiener-Arajev graf).[23]

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

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

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

Regularnost in barvanje uredi

Č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.[26][27] 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[28] 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.

Dvodelnost uredi

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.[29]

Zgledi uredi

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[30] 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.[31]

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,[12] Doyen in van Diest,[32] ter Gutt.[33]

Preštevanje uredi

Chvátal je leta 1973 dokazal, da za vsak dovolj velik n obstaja hipohamiltonov graf z n točkami. Kasnejša odkritja[34][32] 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[35] (OEIS A141150):

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,[36], 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.[35] Š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[16] 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.[29][37][38]

Posplošitve uredi

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.[39][40][18][34] Več avtorjev je obravnavalo analogne definicije hipohamiltonosti in hiposledljivosti za usmerjene grafe.[41][42][43][25]

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[44] 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[36] 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[11] definirali graf, ki je ƒ-okvarnoodporen hamiltonov, če odstranitev največ ƒ točk da Hamiltonov podgraf. Schauerte in Zamfirescu[45] sta raziskovala grafe s cikličnostjo n − 2.

Glej tudi uredi

Sklici uredi

  1. ↑ 1,0 1,1 1,2 Lindgren (1967).
  2. ↑ Krnc; Škrekovski (2015), str. 27.
  3. ↑ Sousselier (1963).
  4. ↑ 4,0 4,1 Gaudin; Herz; Rossi (1964).
  5. ↑ Busacker; Saaty (1965).
  6. ↑ 6,0 6,1 6,2 6,3 Herz; Duby; Vigué (1967).
  7. ↑ 7,0 7,1 7,2 Grötschel (1980).
  8. ↑ Grötschel (1977).
  9. ↑ Grötschel; Wakabayashi (1981).
  10. ↑ Goemans (1995).
  11. ↑ 11,0 11,1 Park; Lim; Kim (2007).
  12. ↑ 12,0 12,1 Bondy (1972).
  13. ↑ Thomassen (1981).
  14. ↑ 14,0 14,1 Thomassen (1974b).
  15. ↑ Goedgebeur; Zamfirescu (2016).
  16. ↑ 16,0 16,1 Chvátal (1973).
  17. ↑ Chvátal; Klarner; Knuth (1972).
  18. ↑ 18,0 18,1 Grünbaum (1974).
  19. ↑ Thomassen (1976).
  20. ↑ 20,0 20,1 Jooyandeh idr. (2013).
  21. ↑ Hatzel (1979).
  22. ↑ Zamfirescu; Zamfirescu (2007).
  23. ↑ Wiener; Araja (2009).
  24. ↑ Wiener; Araja (2011).
  25. ↑ 25,0 25,1 Thomassen (1978).
  26. ↑ Steffen (1998).
  27. ↑ Steffen (2001).
  28. ↑ Häggkvist (2007).
  29. ↑ 29,0 29,1 Collier; Schmeichel (1977).
  30. ↑ Robertson (1969).
  31. ↑ Alspach (1983).
  32. ↑ 32,0 32,1 Doyen; van Diest (1975).
  33. ↑ Gutt (1977).
  34. ↑ 34,0 34,1 Thomassen (1974a).
  35. ↑ 35,0 35,1 Aldred; McKay; Wormald (1997).
  36. ↑ 36,0 36,1 Herz (1968).
  37. ↑ Skupień (1989).
  38. ↑ Skupień (2007).
  39. ↑ Kapoor; Kronk; Lick (1968).
  40. ↑ Kronk (1969).
  41. ↑ Fouquet; Jolivet (1978).
  42. ↑ Grötschel; Wakabayashi (1980).
  43. ↑ Grötschel; Wakabayashi (1984).
  44. ↑ Menke; Zamfirescu; Zamfirescu (1998).
  45. ↑ Schauerte; Zamfirescu (2006).

Viri uredi

Zunanje povezave uredi

Pridobljeno iz »https://sl.wikipedia.org/w/index.php?title=Hipohamiltonov_graf&oldid=5960188«