RAČUNALNIŠ TVO Stabilnost fulerenov in računalništvo •is ■i' ■i' Katja Breznik, Simon Brezovnik in Janez Dolšak Uvod Ste že slišali za kemijsko spojino fuleren? Ali veste, da lahko iz njega izdelamo material, ki je tudi do 200-krat trdnejši od jekla? Ali pa, da lahko fuleren zavira širjenje virusa HIV po telesu? Fulereni so poleg grafita in diamanta ena izmed oblik ogljikovih molekul. Pojavljajo se v obliki sfere, elipsoida ali cevi. Imajo veliko koristnih lastnosti: so protivirusno aktivni, sposobni prenosa elektronov, prenosa zdravil v našem telesu in so potencialna orodja za ugotavljanje malignosti tumorjev. Prisotni so tudi v povsem vsakdanjih predmetih, npr. v oblacilih, teniških loparjih in v premazu krogel za bowling. Na sliki 1 vidimo primer v naravi najbolj pogostega fulerena, znanega pod imenom Buckmin-sterfuleren (krajše Buckyball). Odkrili so ga v 80-ih letih prejšnjega stoletja. Tvori ga 60 ogljikovih atomov, ki se povezujejo v obliko prisekanega ikozae-dra, ki spominja na nogometno žogo. Ime je dobil po arhitektu in izumitelju Buckminsterju Fullerju, ki je v kupolo ene izmed svojih slavnih konstrukcij vključil heksagonske in pentagonske oblike. SLIKA 1. Buckyball SLIKA 2. Ogljikove nanocevke V splošnem obstaja več fulerenov, ki imajo različne lastnosti in dajejo različne možnosti uporabe. Bučkminsterfuleren npr. zavira encim HIV-1 prote-aza, kar lahko zaustavi širjenje virusa HIV po telesu. Ogljikove nanocevke (slika 2) zaradi velike stabilnosti in nereaktivnosti omogočajo shranjevanje močno reaktivnega elementa vodika, hkrati pa jih zaradi dobre električne prevodnosti uporabljajo tudi v elektroniki. Ker so močnejše in lažje od jekla, jih uporabljajo tudi v vesoljskih plovilih. Kemija fulerenov doživlja vzpon in ob tem je zra-stlo tudi zanimanje za raziskovanje matematičnih modelov, ki so v pomoč pri določanju stabilnosti fulerenov. To raziskovanje povezuje kemijo s teorijo grafov in z računalništvom. Pojasnimo najprej, kaj pojem kemijske stabilnosti sploh pomeni. Kemijska stabilnost je kriterij, ki določa, kakšna je težnja snovi k ohranitvi kemijske Presek 42 (2014/2015) 1 23 RAČUNALNIŠTVO zunanje lice vzporedni povezavi SLIKA 3. Primer grafa z označenimi osnovnimi elementi strukture, ko je snovi dodana neka druga (reaktivna) snov ali pa je ta izpostavljena visokemu tlaku, temperaturi ali svetlobi. Dejstvo je, da vecja kot je notranja energija snovi, bolj je snov reaktivna in zato manj stabilna. Vec o stabilnosti fulerena si lahko bralec ogleda v [5]. Osnovni pojmi teorije grafov O grafih je bilo v Preseku že veliko napisanega (npr. [2]). Ponovimo osnovne pojme. Graf G tvori urejen par (V(G),E(G)), pri cemer je V (G) množica vozlišč, E(G) pa množica neurejenih parov vozlišc, ki jih imenujemo povezave grafa. Graf G je koncni graf, ce ima koncno mnogo vozlišc in povezav. Obmocja grafa G, ki so omejena s povezavami, vkljucno z zunanjim neomejenim obmocjem, imenujemo lica. Povezavo v grafu, ki ima obe krajišci enaki, imenujemo zanka. Povezavi, ki imata enaki krajišci, pa imenujemo vzporedni povezavi. Ce v grafu ni ne zank in ne vzporednih povezav, pravimo, da je graf enostaven. Na sliki 3 je prikazan graf z oznacenim licem, zunanjim licem, zanko in vzporednima povezavama. Ravninski graf je graf, ki ga lahko narišemo v ravnini, tako da se poljubni par povezav seka le v skupnem vozlišcu ali pa se ne seka. Graf G je regularen, ce gre iz vsakega njegovega vozlišca enako število povezav. Natancneje grafu, pri katerem iz vsakega vozlišca izhaja natanko k povezav, pravimo k-regularen graf. 3-regularnemu grafu pravimo tudi kubicni graf. Primer kubicnega grafa vidimo na sliki 4. Graf G je dvodelen, ce lahko množico njegovih vozlišc V (G) razdelimo v dve disjunktni množici V\(G) in V2(G), tako da vsaka povezava e iz E(G) poteka iz vozlišca v\ iz V\(G) v vozlišce v2 iz V2(G). Na sliki 4 lahko vidimo, da je prikazani graf dvodelen (bela in crna vozlišca predstavljajo disjunktni množici). Graf H je podgraf grafa G, ce velja, da je množica vozlišc V (H) grafa H podmnožica vozlišc V (G) grafa G in da je množica povezav E(H) grafa H podmnožica povezav E(G) grafa G. SLIKA 4. Kubicni graf 24 Presek 42 (2014/2015) 1 RACUNALNIŠ TVO SLIKA 5. Levo graf in desno njegovvpet podgraf Graf H je vpeti podgraf grafa G, če je H podgraf grafa G in velja V (G) = V (H) (slika 5). Predstavljajmo si, da imamo ravninsko risbo povezanega ravninskega grafa G. Potem v tem grafu v notranjosti vsakega lica narišemo po eno točko. Za vsako povezavo e grafa G narišemo crto, ki povezuje tocki, ki ležita v licih grafa G, ki si delita povezavo e. Ta crta bo predstavljala povezave, prej določene tocke pa vozlišča grafa, ki ga bomo imenovali dualni graf grafa G [4]. Na sliki 6 lahko vidimo, kako iz grafa skonstruiramo njegov dual. Graf K je polni graf, kadar med poljubnim parom različnih vozlišč obstaja povezava. Polni graf, ki ga sestavlja n vozlišč, označimo z Kn. Na sliki 7 vidimo polni graf na dvanajstih vozlišcih. Naj bo M podmnožiča množiče povezav grafa G. Množiči M pravimo prirejanje, če za poljubni različni povezavi iz te množiče velja, da nimata skupnega krajišča. Prirejanje M, v katerem je vsako vozlišče grafa krajišče neke povezave iz M, imenujemo popolno prirejanje. Na sliki 8 je primer tega: levo graf in desno njegovo popolno prirejanje (povezave prirejanja so modre in odebeljene). Naj bo A podmnožiča množiče vseh povezav grafa G. Ce je podgraf (V(G), E(G)\A) grafa G dvodelen, potem pravimo, da je A množiča nedvodelnih povezav. Moč najmanjše mno-žiče nedvodelnih povezav imenujemo nedvodelnost grafa G. Potrebovali bomo še pojem poti. Pred tem ponovimo, kaj je sprehod med poljubnima vozliščema v1 in vn grafa G. Sprehod je zaporedje vozlišč v1,v2, ...,vn, kjer sta vt in vt+1 krajišči neke povezave iz E(G) , za i = 1, 2,..., n-1. Ce imamo sprehod, v katerem so vozlišča paroma različna, govorimo o poti v grafu G in njeno dolžino merimo s številom povezav na tej poti. Predstavitev problema Vsakemu fulerenu je mogoče prirediti graf, katerega vozlišča predstavljajo ogljikove atome, povezave pa kovalentne vezi med njimi. Takšen fulerenski graf je ravninski, kubični graf, ki ima 12 pentagonskih lič, vsa ostala pa so heksagonska. Vsi fulerenski grafi so tudi končni in enostavni. Na sliki 9 je prikazana ravninska vložitev fulerena C60. Preko ugotavljanja nedvodelnosti grafa je mogoče ovrednotiti stabilnost grafu pripadajočega fulerena. Manjša kot je nedvodelnost fulerenskega grafa, večja je njegova stabilnost. Načinov, kako bi ovrednotili nedvodelnost grafa, je več. Naraven način je štetje povezav, ki kvarijo dvodelnost. Predstavili bomo postopek, ki za fule-renski graf izračuna najmanjše število povezav, ki bi jih bilo potrebno odstraniti, da bi graf postal dvodelen. SLIKA 6. Konstrukcija dualnega grafa Presek 42 (2014/2015) 1 25 RAČUNALNIŠTVO SLIKA 7. Polni graf Ku Zakaj fulerenski graf ni dvodelen? Ključen kriterij dvodelnosti grafa je odsotnost lihih ciklov, kar pomeni, da fulerenski graf ne more biti dvodelen, saj vsebuje točno 12 pentagonskih lic. Ker so vsi ostali gradniki fulerenskih grafov heksagonska lica, to obenem pomeni, da so pentagonska lica edina ovira do dvodelnosti teh grafov. Pentagonska lica bodo tako kljucni objekti v tem postopku. Imamo fulerenski graf G. Želimo poiskati (fi(G) - najmanjše število povezav, ki kvarijo dvodelnost grafa G. V nadaljevanju bomo postopek iskanja (p(G) prikazali na primeru fulerenskega grafa C2o (glej sliko 10). Fuleren C20 je najmanjši izmed fulerenov in kot vsi fulereni ima natanko 12 pentagonskih lic. Posebnost grafa je, da so to tudi edina lica, ki jih premore, saj C20 ne vsebuje nobenega heksagonskega lica. Naj bo graf G' dual grafa G. Spomnimo se, da vsako lice grafa G' ustreza voz-lišcu grafa G in obratno, kar pomeni, da ima dual fulerenskega grafa vsa vozlišca stopnje 5 ali 6. Ponovimo: Lice je neko območje ravninske vložitve grafa in velikost lica merimo s številom povezav, ki ga omejujejo. Vozlišce grafa G' stopnje 5 leži v pentagonskem licu grafa G. Tako lahko z iskanjem vozlišc stopnje 5 v G', poišcemo vsa pentagonska lica grafa G (glej sliko 11). SLIKA 9. Fuleren C60 SLIKA 8. Primer grafa in njegovega popolnega prirejanja SLIKA 10. Fuleren C2q. 26 Presek 42 (2014/2015) 1 RAČUNALNIŠ TVO ■ Označimo nekatere povezave grafa G'. Želimo označiti nekatere povezave grafa G' tako, da bodo preostale povezave tvorile vpeti podgraf s samimi vozlišči sode stopnje. Opazimo lahko, da če pentagonsko lice kvari dvo-delnost grafa G, potem pripadajoče vozlišče grafa G' stopnje 5 kvari vpeti podgraf s samimi vozlišči sode stopnje. Imenujmo množico označenih povezav grafa G' ovira. Najmanjša takšna množiča je naša rešitev. Kako jo poiščemo, bomo izvedeli v naslednjem koraku. Lahko pa povzamemo, da v kolikor tako množičo povezav grafa G' odstranimo, graf G postane dvodelen. Potem je namreč vsako vozlišče grafa G' sode stopnje in tako vozlišče tvori pripadajoči čikel sode stopnje v grafu G, kar ustreza definičiji dvodelnosti. ■ Poiščimo ovire. Poljubno izberemo dve izmed dvanajstih penta-gonskih lič v grafu G. Ce želimo, da ta del grafa G ne kvari njegove dvodelnosti, moramo odstraniti nekatere povezave tako, da bosta izbrani liči postali skupno liče sode stopnje (glej sliko 12). V splošnem to storimo tako, da v izbranih pen-tagonskih ličih grafa G označimo vozlišči grafa G'. Razdaljo med njima definiramo kot najmanjše število povezav, ki jih prečkamo, da pridemo od enega do drugega po povezavah grafa G' (glej sliko 13). Ce sedaj odstranimo vse povezave grafa G, ki jih ta pot seka, dobimo skupno liče teh dveh penta-gonskih lič. Skupno liče je seveda sode stopnje, saj ga sestavljata dve pentagonski liči in morebitna heksagonska liča (glej sliko 13). Postopek ponovimo še za preostale poljubno izbrane pare pentagonskih lič. To pomeni, da smo v grafu G' izbrali šest medseboj nepovezanih poti SLIKA 11. SLIKA 12. Dual fulerena C2o Združevanje dveh pentagonskih lic v fulerenu C2o Presek 42 (2014/2015) 1 27 RAČU N A L NIŠTVO —^ in unija teh predstavlja oviro. Če sedaj odstranimo vse povezave grafa G, ki jih ta ovira seka, dobimo dvodelni graf G (glej sliko 14). ■ Najmanjša izmed ovir V prejšnjem koraku smo poiskali eno izmed ovir. Naš namen je poiskati najmanjšo med njimi. Tukaj si pomagamo s polnim grafom na 12 vozliščih K12(G), v katerem vsako vozlišče predstavlja pentagonsko liče grafa G in vsaka povezava pot med pripadajočima vozliščema stopnje 5 v grafu G'. Povezavam grafa K12(G) dodamo uteži tako, da teža povezave med dvema vozlišČčema ustreza dolžini najkrajše poti v grafu G' med njima (glej sliko 15). Sedaj grafu K12(G) poiščemo popolno prirejanje z najmanjšo vsoto uteži. Ponovimo: Prirejanje je popolno, če se vsako vozlišče grafa v množici prirejanja pojavi natanko enkrat. In najmanjše prirejanje je tako, da ne obstaja prirejanje, katerega vsota uteži poti bi bila manjša. Tako dobimo unijo šestih povezav grafa K12(G), katerih vsota uteži je najmanjša možna, kar je prikazano na sliki 15. Izbrane povezave grafa K12(G) pomenijo izbrane poti grafa G'. Če seštejemo povezave grafa G, ki jih te poti sekajo, dobimo taisto vsoto. To je torej najmanjše število povezav v grafu G, ki bi jih bilo potrebno odstraniti, da bi G postal dvodelen. Tako smo izraČčunali očeno stabilnosti fulerena, ki ga predstavlja graf G. SLIKA 13. Primeri poti različnih dolžin v dualu. Izberemo najkrajšo pot ter odstranimo povezave fulerena C20, ki jih ta seka. SLIKA 14. Izberemo šest medsebojno nepovezanih poti duala in odstranimo povezave osnovnega grafa, ki jih ta pot seka. Dobimo dvodelni vpeti podgraf fulerena C20. 28 Presek 42 (2014/2015) 1 RAČUNALNIŠ TVO V računalniškem svetu je ta postopek možno rešiti v polinomskem času. Najzahtevnejši del postopka je poiskati uteži v grafu K12(G), ki so razdalje med vozlišči stopnje 5 v G'. Ta del je možno rešiti v linearnem času O(n). Potrebno je le še poiskati najmanjše popolno prirejanje, česar časovna zahtevnost je v splošnem O(n3), a ker ima naš graf K12(G) vedno 12 vozlišč, je časovna zahtevnost konstantna O(123) ne glede na velikost grafa G. Torej je skupna časovna zahtevnost postopka O(n). Izjemna in vsestranska uporabnost molekule fule-rena motivira in navdušuje mnoge raziskovalče, zato verjamemo, da boste o njej spoznali še veliko zanimivega. SLIKA15. Grafu K12(C20) dodamo uteži. Zaradi simetrije so povezave vsakega vozlišča enako obtežene, in sicer v zaporedju: 1,2, 1, 2, 1, 3, 2, 1, 2, 1, 2. Če sedaj poiščemo najmanjše popolno prirejanje, dobimo unijo šestih disjunktnih povezav, katerih vsota uteži je 6. www.dmfa.si www.presek.si Literatura [1] T. Došlic in W. D. Vukicevic, Computing the bipartite edge frustration of fullerene graphs, Department of Informatics and Mathematics, Faculty of Agriculture, University of Zagreb, 2006. [2] M. Kren, Prirejanja grafov in maturantski ples, Presek 39 5, Ljubljana, 2011-2012. [3] R. Wilson in W. J. Watkins, Uvod v teorijo grafov, DMFA - založništvo, Ljubljana, 1997. [4] T. Malec, Ravninski grafi (seminarska naloga), Fakulteta za matematiko in fiziko, str. 12, Ljubljana, 2007. [5] M. S. Dresselhaus, G. Dresselhaus in P. C. Eklund, Science ofFullerenes and Carbon Nano-tubes, Academic Press, San Diego, 1996. _XXX Križne vsote Rešitev s strani 12 -i' -i' -i' 5 19 3 4 9 3 14 9 1 8 11 8 19 2 6 7 2 5 14 10 5 1 8 15 6 1 8 15 9 6 XXX www.dmfa-zaloznistvo.si www.obzornik.si Presek 42 (2014/2015) 1 29