1. Robne množice v grafihLucija Mernik, 2013, diplomsko delo Opis: V diplomskem delu raziskujemo različne tipe robnih vozlišč: periferna, konturna in ekscentrična vozlišča. Predstavimo osnovne koncepte teorije grafov s poudarkom na standardnih produktih grafov, se osredotočimo na različne tipe robnih množic in predstavimo številne njihove strukturne lastnosti. Iz glavnega izreka je razviden obstoj grafa s predpisano močjo periferne, konturne, ekscentrične in robne množice. Pokažemo tudi, da je robna množica vsakega povezanega grafa tudi geodetska in predstavimo nekaj zadostnih pogojev za to, da je konturna množica grafa tudi geodetska. Na koncu naredimo pregled znanih rezultatov glede robnih množic v standardnih produktih grafov.
Ključne besede: robne množice, produkti grafov, konturna množica.
Objavljeno: 28.05.2013; Ogledov: 1208; Prenosov: 91
 Celotno besedilo (1,34 MB) |
2. On the geodetic number and related metric sets in Cartesian product graphsBoš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: 447; Prenosov: 66
 Povezava na celotno besedilo |
3. Robne in geodetske množice v grafihVesna Lebar, 2015, magistrsko delo Opis: V magistrskem delu so obravnavane lastnosti in povezave med posameznimi robnimi množicami grafa, ki jih sestavljajo robna, ekscentrična, periferna, konturna in ekstremna vozlišča grafa. Zanimale nas bodo predvsem povezave med robnimi in geodetskimi množicami grafa, posebej se bomo posvetili preučevanju konturne množice grafa.
V prvem poglavju so zapisani osnovni pojmi in definicije iz teorije grafov, ki jih bomo potrebovali v nadaljevanju. V drugem poglavju definiramo tipe robnih množic, navedemo osnovne lastnosti le-teh in dokažemo dva realizacijska izreka, ki govorita o obstoju poljubnega grafa pri podanih kardinalnostih različnih skupin robnih množic. V tretjem poglavju navedemo rezultate, ki pravijo, da je konturna množica tetivnih, razdaljno hereditarnih, 3-SDH in HHD-prostih grafov geodetska množica. Obravnavamo tudi konturno množico dvodelnih grafov in dokažemo, da za vsak diameter $kgeq 8$ obstaja dvodelni graf, katerega konturna množica ni geodetska. V zadnjem razdelku obravnavamo konturne in geodetske množice delnih kock.
Ključne besede: robne množice, geodetska množica, konturna množica
Objavljeno: 05.11.2015; Ogledov: 605; Prenosov: 58
Celotno besedilo (1,41 MB) |
