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

Dominacijsko število grafa

Neja Zubčič (2011) Dominacijsko število grafa. Diplomsko delo.

[img]
Predogled
PDF
Download (1206Kb)

    Povzetek

    Osrednja tema diplomskega dela so dominacijske množice in z njimi povezano dominacijsko število grafa. Množica vozlišč grafa G je dominacijska množica, če njena zaprta okolica pokrije celoten graf. Minimalno kardinalnost dominacijske množice grafa imenujemo dominacijsko število grafa. Predstavljena je zgodovina raziskovanja dominacijskega števila in opisan tako imenovan problem kraljic, ki predstavlja začetek raziskovanja na tem področju. Dominacijsko število grafa je praviloma zelo težko določiti, saj je problem določitve dominacijskega števila grafa tako imenovan NP-poln problem. Prepričamo se, da je temu res tako. Pri določanju dominacijskega števila si zato običajno pomagamo z nekaterimi zgornjimi in spodnjimi mejami. Ogledamo si nekatere, ki so odvisne tudi od minimalne in maksimalne stopnje grafa ter števila vozlišč. Podano je dominacijsko število nekaterih osnovnih družin grafov, kot so polni grafi, cikli, poti in polni dvodelni grafi, v zadnjem delu pa se posvetimo določitvi dominacijskega števila nekaterih posplošenih Petersenovih grafov.

    Tip vnosa: Delo ali doktorska disertacija (Diplomsko delo)
    Ključne besede: teorija grafov, dominacijsko število, dominacijska množica, minimalna dominacijska množica, NP-poln problem
    Število strani: 58
    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: 175
    Datum vnosa: 29 Sep 2011 13:16
    Zadnja sprememba: 29 Sep 2011 13:16
    URI: http://pefprints.pef.uni-lj.si/id/eprint/175

    Akcije (potrebna je prijava)

    Pregled vnosa