| | 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 - 8 / 8
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
GEODETSKO IN OVOJNIŠKO ŠTEVILO PRODUKTOV GRAFOV
Jasna Mrkonjić, 2010, diplomsko delo

Opis: Diplomsko delo obravnava geodetsko in ovojniško število standardnih produktov grafov s poudarkom na kartezičnem in krepkem produktu. V prvem delu so zapisane osnovne definicije s področja teorije grafov, ki se uporabljajo v nadaljevanju. V naslednjem poglavju si pogledamo grafe, za katere je geodetsko število enako ali za ena manjše od števila vozlišč ter enako za ovojniško število. Sledi poglavje v katerem se osredotočimo na geodetsko in ovojniško število v kartezičnem produktu grafov in si pogledamo robne množice. Zadnji del diplomske naloge je namenjen geodetskemu in ovojniškemu številu v krepkem produktu grafov, kjer so podane meje za obe števili in natančne vrednosti za določene tipe grafov.
Ključne besede: konveksnost, ovojnica, geodetska množica grafa, geodetsko število, ovojniško število, poln graf, cikel, produkt grafov, kartezični produkt grafov, krepki produkt grafov, robne množice
Objavljeno: 15.12.2010; Ogledov: 1933; Prenosov: 98
.pdf Celotno besedilo (754,64 KB)

2.
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: 1792; Prenosov: 152
.pdf Celotno besedilo (2,43 MB)

3.
Median graphs, the remoteness function, periphery transversals, and geodetic number two
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Wilfried Imrich, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2008

Opis: Periferna transverzala medianskega grafa ▫$G$▫ je vpeljana kot množica vozlišč, ki zadane vse periferije grafa $G$. S pomočjo tega koncepta so na dva različna načina karakterizirani medianski grafi z geodetskim številom 2. To so natanko tisti medianski grafi, ki vsebujejo periferno transverzalo moči 2, kot tudi medianski grafi, za katere obstaja takšen profil, da je funkcija oddaljenosti konstantna na ▫$G$▫. Predstavljen je tudi algoritem, ki v času ▫$O(m log n)$▫ odloči, ali je dani graf z ▫$n$▫ vozlišči in ▫$m$▫ povezavami medianski graf z geodetskim številom 2. Dobljenih je še več nadaljnjih lastnosti funkcije oddaljenosti na hiperkockah in medianskih grafih. Navedenih je tudi nekaj odprtih problemov.
Ključne besede: medianski graf, medianska množica, funkcija oddaljenosti, geodetsko število, periferna transverzala, median graph, median set, remoteness function, geodetic number, periphery transverzal, hypercube
Objavljeno: 10.07.2015; Ogledov: 365; Prenosov: 10
URL Povezava na celotno besedilo

4.
On the geodetic number of median graphs
Boštjan Brešar, Aleksandra Tepeh, 2008, izvirni znanstveni članek

Opis: Množica vozlišč ▫$S$▫ v grafu se imenuje geodetska množica, če vsako vozlišče tega grafa leži na kaki najkrajši poti med dvema vozliščema iz množice ▫$S$▫. V članku raziskujemo najmanjše geodetske množice medianskih grafov z ozirom na operacijo periferne ekspanzije. Spotoma obravnavamo geodetske množice medianskih prizem in karakteriziramo medianske grafe, ki imajo geodetsko množico velikosti 2.
Ključne besede: matematika, teorija grafov, medianski grafi, geodetsko število, geodetska množica, kartezični produkt grafov, ekspanzija, mathematics, graph theory, median graphs, geodetic number, geodetic set, Cartesian product, geodesic, expansion
Objavljeno: 10.07.2015; Ogledov: 307; Prenosov: 40
URL Povezava na celotno besedilo

5.
On the geodetic number and related metric sets in Cartesian product graphs
Boštjan Brešar, Sandi Klavžar, Aleksandra Tepeh, 2008, izvirni znanstveni članek

Opis: Množica vozlišč ▫$S$▫ grafa ▫$G$▫ je geodetska množica, če vsako vozlišče grafa ▫$G$▫ leži na vsaj enem intervalu med vozliščema iz ▫$S$▫. Moč najmanjše geodetske množice v ▫$G$▫ imenujemo geodetsko število grafa ▫$G$▫. Dokazana je zgornja meja za geodetsko število kartezičnega produkta in za nekatere razrede grafov je dobljena tudi natančna vrednost. Prav tako je dokazano, da imajo mnoge metrično definirane množice v kartezičnih produktih produktno strukturo in da je konturna množica v kartezičnem produktu geodetska natanko tedaj, ko sta njeni projekciji geodetski množici v faktorjih.
Ključne besede: matematika, teorija grafov, kartezični produkt, geodetsko število, geodetska množica, konturna množica, mathematics, graph theory, Cartesian product, geodetic number, geodetic set, contour set
Objavljeno: 10.07.2015; Ogledov: 364; Prenosov: 55
URL Povezava na celotno besedilo

6.
On the remoteness function in median graphs
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Wilfried Imrich, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2009, izvirni znanstveni članek

Opis: Profil grafa ▫$G$▫ je poljubna neprazna multimnožica vozlišč iz ▫$G$▫. Pripadajoča funkcija oddaljenosti priredi vsakemu vozlišču iz ▫$V(G)$▫ vsoto razdalj do vozlišč iz profila. Najprej so dobljene nekatere uporabne lastnosti funkcije oddaljenosti na hiperkockah, nato pa je funkcija oddaljenosti obravnavana na poljubnih medianskih grafih glede na njihove izometrične vložitve v hiperkocke. V posebnem je najdena povezava med vozlišči medianskega grafa ▫$G$▫, katerega funkcija oddaljenosti je največja (antimedianska množica v ▫$G$▫), z antimediansko množico pripadajoče hiperkocke. Medtem ko je za lihe profile antimedianska množica neodvisna množica, ki leži na strogem robu medianskega grafa, obstajajo medianski grafi, v katerih določeni sodi profili porajajo konstantno funkcijo oddaljenosti. Take medianske grafe karakteriziramo na dva načina: kot grafe, katerih periferna transverzala je 2, in kot grafe z geodetskim številom 2. Nazadnje predstavimo algoritem, ki za dani graf ▫$G$▫ z ▫$n$▫ vozlišči in ▫$m$▫ povezavami v času ▫$O(m log n)$▫ odloči, ali je ▫$G$▫ medianski graf z geodetskim številom 2.
Ključne besede: hiperkocka, medianski graf, medianska množica, funkcija oddaljenosti, geodetsko število, periferna transverzala, median graph, median set, remoteness function, geodetic number, periphery transverzal, hypercube
Objavljeno: 10.07.2015; Ogledov: 361; Prenosov: 60
URL Povezava na celotno besedilo

7.
Geodetic sets in graphs
Boštjan Brešar, Matjaž Kovše, Aleksandra Tepeh, 2011, samostojni znanstveni sestavek ali poglavje v monografski publikaciji

Opis: Na kratko so povzeti rezultati o geodetskih množicah v grafih. Po pregledu rezultatov iz prejšnjih raziskav se posvetimo geodetskemu številu in sorodnim invariantam v grafih. Podrobno so obravnavane geodetske množice kartezičnih produktov grafov in geodetske množice v medianskih grafih. Predstavljen je tudi algoritmični vidik in povezava z nekaterimi ostalimi koncepti iz teorije konveksnih in intervalskih struktur v grafih.
Ključne besede: matematika, teorija grafov, geodetsko število, geodetska množica, kartezični produkt, medianski graf, mejna množica, mathematics, graph theory, geodetic number, geodetic set, Cartesian product, median graph, boundary set
Objavljeno: 10.07.2015; Ogledov: 186; Prenosov: 13
URL Povezava na celotno besedilo

8.
The geodetic number of the lexicographic product of graphs
Boštjan Brešar, Tadeja Kraner Šumenjak, Aleksandra Tepeh, 2011, izvirni znanstveni članek

Opis: Množica ▫$S$▫ vozlišč grafa ▫$G$▫ je geodetska, če vsako vozlišče grafa ▫$G$▫ leži na intervalu med dvema vozliščema iz ▫$S$▫. Velikost najmanjše geodetske množice grafa ▫$G$▫ se imenuje geodetsko število ▫$g(G)$▫ grafa ▫$G$▫. V članku dokažemo, da geodetsko število leksikografskega produkta ▫$G circ H$▫, kjer ▫$H$▫ ni poln graf, leži med 2 in ▫$3g(G)$▫. Okarakteriziramo vse grafe ▫$G$▫ in ▫$H$▫, za katere je ▫$G circ H = 2$▫, kot tudi leksikografske produkte ▫$T circ H$▫, za katere je ▫$g(T circ H) = 3g(G)$▫, kjer je ▫$T$▫ izomorfen drevesu. Z uporabo novega koncepta geodominantnih trojic grafa ▫$G$▫ najdemo formulo, ki določi točno geodetsko število ▫$G circ H$▫, kjer je ▫$G$▫ poljuben graf in ▫$H$▫ graf, ki ni poln.
Ključne besede: matematika, teorija grafov, leksikografski produkt, geodetsko število, geodominantna trojica, mathematics, graph theory, lexicographic product, geodetic number, geodominating triple
Objavljeno: 10.07.2015; Ogledov: 364; Prenosov: 47
URL Povezava na celotno besedilo

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