[feed] pefprints@pef.uni-lj.si | [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0 |
English
Logo            
  Logo Prijava | Registracija
 
 

O simetričnih Nest grafih

Gorazd Vasiljević (2017) O simetričnih Nest grafih. Magistrsko delo.

[img]
Predogled
PDF
Download (3197Kb)

    Povzetek

    Magistrsko delo sodi na področje algebraične teorije grafov. V tej veji teorije grafov nas pogosto zanimajo t. i. avtomorfizmi (simetrije) grafov, torej permutacije množice vozlišč grafa, ki ohranjajo sosednosti. Pri tem je naš cilj pogosto klasifikacija vseh grafov z nekimi danimi simetrijskimi lastnostmi. Pri posebej »lepih« grafih velja, da za poljuben par vozlišč obstaja avtomorfizem, ki eno vozlišče preslika v drugo (t. i. grupa avtomorfizmov grafa deluje tranzitivno na množico vozlišč). Pravimo, da so taki grafi vozliščno tranzitivni. Na podoben način je lahko graf povezavno tranzitiven, če grupa avtomorfizmov deluje tranzitivno na množico njegovih povezav in je ločno tranzitiven (oziroma simetričen), če grupa avtomorfizmov deluje tranzitivno na množico njegovih lokov. Bicirkulant je graf, ki dopušča avtomorfizem z dvema orbitama iste dolžine. Za začetek preučevanja simetrij bicirkulantov štejemo rezultate Fruchta, Graverja in Watkinsa iz leta 1971, ki so preučili družino t. i. Posplošenih Petersenovih grafov in klasificirali vse njene vozliščno in povezavno tranzitivne člane. Naslednji korak je leta 2008 storil Wilson, ki je opravil velik del klasifikacije povezavno tranzitivnih Rozetnih grafov, njegovo delo pa so dve leti kasneje dokončali Kovács, Kutnar in Marušič. Podobno so Arroyo, Hubard, Kutnar, O'Reilly in Šparl leta 2015 klasificirali vse simetrične Tabačjn grafe. V magistrskem delu vpeljemo posplošitev Posplošenih Petersenovih grafov na stopnjo 6. Gre za doslej še neraziskano družino bicirkulantov. Pripadajoče grafe poimenujemo Nest grafi. Glavni namen magistrskega dela je začetek klasifikacije simetričnih Nest grafov, pri čemer storimo nekaj prvih, pomembnih korakov. Poleg predstavitve same družine Nest grafov, v kateri pokažemo nekaj njihovih osnovnih lastnosti in dejstev, povezanih z njimi, se v nadaljevanju osredotočimo predvsem na njihove simetrijske lastnosti. Na podlagi rezultatov programskega paketa Magma identificiramo nekatere družine ločno tranzitivnih Nest grafov in za njihove člane dokažemo, da so res simetrični. Kot zelo pomemben rezultat magistrsko delo predstavi skoraj popolno klasifikacijo simetričnih Nest grafov ožine 3.

    Tip vnosa: Delo ali doktorska disertacija (Magistrsko delo)
    Ključne besede: teorija grafov, bicirkulant, avtomorfizem, Nest graf, ločno tranzitiven graf
    Število strani: 67
    Jezik vsebine: Slovenščina
    Mentor / Somentorji:
    Mentor / SomentorjiIDFunkcija
    doc. dr. Primož ŠparlMentor
    Povezava na COBISS: http://www.cobiss.si/scripts/cobiss?command=search&base=50126&select=(ID=11588681)
    Ustanova: Univerza v Ljubljani
    Fakulteta: Pedagoška fakulteta
    ID vnosa: 4501
    Datum vnosa: 27 Jun 2017 14:21
    Zadnja sprememba: 27 Jun 2017 14:21
    URI: http://pefprints.pef.uni-lj.si/id/eprint/4501

    Akcije (potrebna je prijava)

    Pregled vnosa