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

Hamiltonskost usmerjenih cirkulantov

Iva Antončič (2011) Hamiltonskost usmerjenih cirkulantov. Diplomsko delo.

[img]
Predogled
PDF
Download (3567Kb)

    Povzetek

    Usmerjeni cirkulant Circ(n; S) je digraf, katerega točke so elementi ciklične grupe Zn, usmerjena povezava od u do v pa v digrafu obstaja natanko tedaj, ko je v=u+s za nek s iz S. Diplomsko delo obravnava obstoj Hamiltonovih ciklov v usmerjenih cirkulantih, ki imajo izhodno stopnjo 2 ali 3. Hamiltonov cikel digrafa je tak sklenjen sprehod po usmerjenih povezavah digrafa, v katerem vsako točko obiščemo natanko enkrat. Vprašanje hamiltonskosti usmerjenih cirkulantov z izhodno stopnjo 2 je po zaslugi Rankina v celoti rešeno že od leta 1946. Za veliko težji zalogaj so se izkazali usmerjeni cirkulanti z izhodno stopnjo 3. Za nekatere družine obstoj Hamiltonovega cikla znamo dokazati, za nekatere družine znamo dokazati, da ga ni, za veliko večino usmerjenih cirkulantov z izhodno stopnjo 3 pa še nič ne vemo. V diplomskem delu si ogledamo Rankinov rezultat za usmerjene cirkulante z izhodno stopnjo 2 ter dosedanje rezultate za usmerjene cirkulante z izhodno stopnjo 3. Poleg tega s pomočjo računalniškega programa preverimo, kateri usmerjeni cirkulanti z izhodno stopnjo 3 na do vključno 87 točkah imajo Hamiltonov cikel.

    Tip vnosa: Delo ali doktorska disertacija (Diplomsko delo)
    Ključne besede: Cayleyev digraf, usmerjeni cirkulant, hamiltonskost, Hamiltonov cikel
    Število strani: 66
    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=8903753)
    Ustanova: Univerza v Ljubljani
    Fakulteta: Pedagoška fakulteta
    ID vnosa: 532
    Datum vnosa: 02 Dec 2011 13:25
    Zadnja sprememba: 02 Dec 2011 13:25
    URI: http://pefprints.pef.uni-lj.si/id/eprint/532

    Akcije (potrebna je prijava)

    Pregled vnosa