Opombe
Leta 2013 so Gradišar in sod. predstavili novo strategijo za oblikovanje samosestavljivih nanostruktur. Poglavitni uspeh njihove raziskave predstavlja izdelava polipeptidnega samosestavljivega tetraedra z združevanjem dvanajstih odsekov, ki paroma tvorijo ovite vijačnice v natančno določenem vrstnem redu. Natančneje, ena polipeptidna veriga je razporejena med 6 stranic tetraedra tako, da vsako stranico prečka natanko dvakrat. Na tak način se šest dimerov ovitih vijačnic zaklene v stabilno tetraedrsko strukturo. Polieder ?$P$?, ki je sestavljen iz ene polipeptidne verige, lahko naravno predstavimo z grafom poliedra ?$G(P)$?. Ker v tehnološkem procesu vsaka povezava ?$G(P)$? ustreza dimeru ovitih vijačnic, ustrezata vsaki povezavi natanko dva odseka. V ta namen predstavimo strogi (in ?$d$?-stabilni) obhod grafa kot sklenjen sprehod, ki vsako povezavo grafa prečka dvakrat (takšen sprehod imenujemo tudi dvojni obhod), pri tem pa za vsako vozlišče ?$v$? velja, da ne obstaja taka podmnožica njegovih sosedov ?$N \subseteq N(v)$?, ?$1 \leq |N| < d(v)$? (?$1 \leq |N| \leq d$?), da vsakič, ko sprehod pride v ?$v$? iz vozlišča v ?$N$?, tudi zapusti ?$v$? v smeri proti vozlišču v ?$N$?. S pomočjo povezave med vložitvami grafov z enim licem v ploskve višjega roda in strogimi obhodi ter klasičnima rezultatoma Edmondsa in Ringla lahko dokažemo, da vsak povezan graf vsebuje strogi obhod in da graf ?$G$? vsebuje ?$d$?-stabilni obhod natanko tedaj, ko je povezan in je njegova minimalna stopnja ?$\delta(G) > d$?. Dvojni obhod vsako povezavo grafa prečka dvakrat. Posledično lahko v dvojnem obhodu definiramo dva tipa povezav.Če dvojni obhod ?$W$? prečka povezavo ?$e$? dvakrat v isti smeri, pravimo, da je ?$e$? paralelna povezava (glede na ?$W$?), sicer pa rečemo, da je ?$e$? antiparalelna povezava (glede na ?$W$?). Nadalje je dvojni obhod grafa ?$G$? paralelni dvojni obhod, če je vsaka povezava v ?$G$? paralelna (glede na ?$W$?), in antiparalelni dvojni obhod, če je vsaka povezava v ?$G$? antiparalelna (glede na ?$W$?). Tudi motivacija za takšen pristop naravno izhaja iz lastnosti samosestavljivih nanostruktur. V delu karakteriziramo grafe, ki vsebujejo: (i) paralelne stroge obhode kot Eulerjeve grafe, (ii) paralelne ?$d$?-stabilne obhode kot Eulerjeve grafe z minimalno stopnjo ?$\delta > d$?, (iii) antiparalelne stroge obhode kot vse povezane grafe, v katerih obstaja vpeto drevo ?$T$? z lastnostjo, da ima vsaka povezana komponenta ko-drevesa ?$G - E(T)$? sodo število povezav, in (iv) antiparalelne ?$d$?-stabilne obhode kot vse povezane grafe ?$G$? z minimalno stopnjo ?$\delta(G) > d$?, v katerih obstaja vpeto drevo ?$T$? z lastnostjo, da je vsaka povezana komponenta ko-drevesa ?$G - E(T)$? soda ali pa vsebuje vozlišče stopnje najmanj ?$2d + 2$?. Zadnji rezultat predstavlja tudi posplošitev problema, ki ga je leta 1951 postavil Ore in šele slabih 40 let kasneje rešil Thomassen (omenjeni problem v našem jeziku predstavlja karakterizacijo grafov, ki vsebujejo antiparalelne 1-stabilne obhode). Pri tem si med drugim pomagamo tudi z novimi ugotovitvami o vpetih drevesih s podobnimi lastnostmi, kot jih imajo Xuongova drevesa. Koncept ?$E$?-predpisanih obhodov, tj. dvojnih obhodov, v katerih je vsaka povezava iz ?$E \subseteq E(G)$? antiparalelna in vsaka povezava iz ?$E(G) \setminus E$? paralelna, po eni strani združi rezultate o paralelnih in antiparalelnih dvojnih obhodih v preproste izreke ter po drugi strani v praksi pomaga kontrolirati lastnosti samosestavljivih nanostruktur. ?$E$?-predpisane dvojne obhode sta neodvisno raziskovala že Vastergaard in Fleischner, medtem ko so rezultati o ?$E$?-predpisanih strogih obhodih in ?$E$?-predpisanih ?$d$?-stabilnih obhodih povsem novi. Ker grafi vsebujejo več dvojnih obhodov, definiramo, da sta dva dvojna obhoda ?$W$? in ?$W'$? grafa ?$G$? ekvivalentna, kadar je moč ?$W'$? dobiti z obratom ?$W$?, z zamikom ?$W$?, z delovanjem permutacije, inducirane z avtomorfizmom grafa ?$G$? na ?$W$?, ali s kombinacijo prej naštetih treh možnosti. V želji, da bi v praksi za dani polieder znali izbrati strogi obhod, ki bo imel največjo verjetnost, da se uspešno sestavi v samosestavljivo nanostrukturo želene oblike, smo razvili dva algoritma, ki generirata vse stroge obhode za dani graf ?$G$?. Prvi algoritem temelji na algebraičnem pristopu in uporablja nekatera nova dognanja o grupi avtomorfizmov dvojnih obhodov, drugi pa se zanaša na topološke lastnosti grafa. Pri tem je časovna zahtevnost drugega za kubične grafe le ?$O(mf)$?, kjer je ?$m$? število povezav, ?$f$? pa število lic v neki znani vložitvi grafa ?$G$?.