| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava
Prva stran > Izpis gradiva

Izpis gradiva Pomoč

Naslov:Elementarni benzenoidni grafi in nad njimi definirani grafi : doktorska disertacija
Avtorji:ID Taranenko, Andrej (Avtor)
ID Vesel, Aleksander (Mentor) Več o mentorju... Novo okno
Datoteke:.pdf DR_Taranenko_Andrej_i2008.pdf (705,16 KB)
MD5: D0CF794A6A79CC2EE206B24FC9C0A17F
PID: 20.500.12556/dkum/0d35e121-bdfb-4d99-99b5-e5afa5e4fca8
 
Jezik:Slovenski jezik
Vrsta gradiva:Doktorska disertacija
Organizacija:FNM - Fakulteta za naravoslovje in matematiko
Opis: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 τ-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(mlogn) prepozna, ali je dani graf Fibonaccijeva kocka. Podani algoritem te grafe prepoznava hitreje od do sedaj znanih algoritmov.
Ključne besede:matematika, teorija grafov, benzenoidni graf, reducibilno lice, resonančni graf, notranji dual, hiperkocka, Fibonaccijeva kocka, disertacije
Kraj izida:[S. l.
Založnik:A. Taranenko]
Leto izida:2008
PID:20.500.12556/DKUM-9574 Novo okno
UDK:519.17(043.3)
COBISS.SI-ID:16568328 Novo okno
NUK URN:URN:SI:UM:DK:UBYYWXGN
Datum objave v DKUM:21.01.2009
Število ogledov:7056
Število prenosov:571
Metapodatki:XML DC-XML DC-RDF
Področja:FNM
:
TARANENKO, Andrej, 2008, Elementarni benzenoidni grafi in nad njimi definirani grafi : doktorska disertacija [na spletu]. Doktorska disertacija. S. l. : A. Taranenko. [Dostopano 14 april 2025]. Pridobljeno s: https://dk.um.si/IzpisGradiva.php?lang=slv&id=9574
Kopiraj citat
  
Skupna ocena:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:Bookmark and Share


Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Elementary benzenoid graphs and graphs defined on them
Opis:In this thesis we first study elementary benzenoid graphs and focus on the reducible face decomposition which can be used to construct any elementary benzenoid graph. Using 1-factors we characterize reducible faces of elementary benzenoid graphs, i. e. faces which after their removal from the original graph preserve the property of the graph being elementary. Given this characterization we present an algorithm that finds a reducible face decomposition of the given graph in quadratic time. Moreover, for elementary benzenoid graphs with at most one pericondensed component we present a linear algorithm for finding a reducible face decomposition. With the concept of 4-tiling we give a new characterization of elementary benzenoid graphs, namely we show that a benzenoid graph is elementary it and only if it allows a 4-tiling. Next we focus on the structure of resonance graphs of elementary benzenoid graphs which do not possess a coronene as a subgraph. The structure is presented in the form of a decomposition theorem. We conclude that there is a connection between 4-tilings of elementary benzenoid graphs without a coronene as a subgraph and τ-graphs of their resonance graphs. Finally, we focus on the structure of Fibonacci cubes, which are resonance graphs of fibonaccenes - a family of catacondensed benzeniod graphs. Studying their structure enables us to give a new characterization of Fibonacci cubes which serves as a basis for a recognition algorithm of Fibonacci cubes. This algorithm with the time complexity of 0(mlogn) is faster than any previously known algorithm.


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici