UNI-MB - logo
UMNIK - logo
 
Narodna in univerzitetna knjižnica, Ljubljana (NUK)
Naročanje gradiva za izposojo na dom
Naročanje gradiva za izposojo v čitalnice
Naročanje kopij člankov
Urnik dostave gradiva z oznako DS v signaturi
  • Elementarni benzenoidni grafi in nad njimi definirani grafi : doktorska disertacija
    Taranenko, Andrej
    V disertaciji najprej proučujemo elementarne benzenoidne grafe ter se posvetimo dekompoziciji reducibilnih lic, s pomočjo katere lahko konstruiramo poljuben elementarni benzenoidni graf. Najprej s ... pomočjo l-faktorjev karakteriziramo reducibilna lica elementarnih benzenoidnih grafov. To so tista lica grafa, ki po odstranitvi iz grafa ohranjajo lastnost elementarnosti. S pomočjo karakterizacije reducibilnih lic podamo algoritem, ki nam za dani elementarni benzenoidni graf poišče tako zaporedje reducibilnih lic, da z njihovo odstranitvijo dobimo en sam šestkotnik. Podani algoritem je mogoče izvesti v kvadratnem času. Za družino elementarnih benzenoidnih grafov z natanko eno perikondenzirano komponento podamo linearni algoritem, ki zanje poišče dekompozicij o reducibilnih lic. Nadalje s pomočjo 4-tlakovanj podamo novo karakterizacijo elementarnih benzenoidnih grafov, saj pokažemo, da je benzenoidni graf elementaren natanko tedaj, ko zanj obstaja 4-tlakovanje. Nato se posvetimo strukturi resonančnih grafov elementarnih benzenoidnih grafov, ki ne vsebujejo koronena kot podgraf, ter zanje pokažemo dekompozicijski izrek. Še več, pokažemo, da so njihovi ▫$\tau$▫-grafi tesno povezani s 4-tlakovanji pripadajočega benzenoidnega grafa. Na koncu se posvetimo Fibonaccijevim kockam, ki so resonančni grafi fibonaccenov, ki so posebna družina katakondenziranih benzenoidnih grafov. S proučevanjem strukture Fibonaccijevih kock podamo novo karakterizacijo teh grafov. Ta karakterizacija služi kot osnova za algoritem, ki v času ▫$0(m log n)$▫ prepozna, ali je dani graf Fibonaccijeva kocka. Podani algoritem te grafe prepoznava hitreje od do sedaj znanih algoritmov.
    Vrsta gradiva - disertacija ; neleposlovje za odrasle
    Založništvo in izdelava - [S. l. : A. Taranenko], 2008
    Jezik - slovenski
    COBISS.SI-ID - 16568328

Rezervirajte gradivo na želenem mestu prevzema.

Mesto prevzema Status gradiva Rezervacija
Časopisna čitalnica
prosto - za čitalnico
Velika čitalnica
prosto - za čitalnico
Signatura – lokacija, inventarna št. ... Status izvoda
GS II 0000703575 glavno skladišče GS II 703575 glavno skladišče prosto - za čitalnico
loading ...
loading ...
loading ...