| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 1 / 1
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
Geodetsko število medianskih grafov
Sanja Lakner, 2011, diplomsko delo

Opis: Množico točk S grafa G=(V(G),E(G)) imenujemo geodetska množica v G, če vsako vozlišče grafa G leži na neki najkrajši poti med dvema vozliščema iz množice S. Diplomsko delo preučuje lastnosti minimalnih geodetskih množic v medianskih grafih, ki so definirani kot grafi, v katerih za poljubna tri vozlišča u,v,w∈V(G) presek I(u,v)∩I(u,w)∩I(v,w) sestoji iz natanko enega vozlišča. Prvo poglavje vsebuje osnovne definicije in opažanja s področja teorije grafov, ki so pomembna za nadaljnje razumevanje. V drugem poglavju so predstavljene osnovne lastnosti medianskih grafov, osredotočili smo se predvsem na dva podrazreda medianskih grafov imenovana kot hiperkocke in drevesa, medianske grafe pa smo karakterizirali s pomočjo periferne ekspanzije. V tretjem poglavju je predstavljeno geodetsko število grafov, v zadnjem pa predstavimo še minimalne geodetske množice v medianskih grafih, preučevane skozi postopek periferne ekspanzije. Karakterizirani so še primeri, ko geodetsko število tudi po postopku periferne ekspanzije ostane enako. Nalogo zaključimo s karakterizacijo medianskih grafov, ki imajo geodetsko število enako 2.
Ključne besede: medianski grafi, periferna ekspanzija, zastražene množice, geodetska množica, geodetsko število
Objavljeno: 07.07.2011; Ogledov: 1851; Prenosov: 162
.pdf Celotno besedilo (2,43 MB)

Iskanje izvedeno v 0.04 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici