Iskanje po katalogu digitalne knjižnice

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 v DKUM: 10.07.2015; Ogledov: 1297; Prenosov: 144
Povezava na celotno besedilo

Opis: The resonance graph ▫$R(B)$▫ of a benzenoid graph ▫$B$▫ has the perfect matchings of ▫$B$▫ as vertices, two perfect matchings being adjacent if their symmetric difference forms the edge set of a hexagon of ▫$B$▫. A family ▫$mathscr{P}$▫ of pair-wise disjoint hexagons of a benzenoid graph ▫$B$▫ is resonant in ▫$B$▫ if ▫$B -- mathscr{P}$▫ contains at least one perfect matching, or if ▫$B -- mathscr{P}$▫ is empty. It is proven that there exists a surjective map ▫$f$▫ from the set of hypercubes of ▫$R(B)$▫ onto the resonant sets of B such that a ▫$k$▫-dimensional hypercube is mapped into a resonant set of cardinality ▫$k$▫.
Ključne besede: matematika, teorija grafov, benzenoidni graf, popolno prirejanje, resonančni graf, hiperkocka, mathematics, graph theory, benzenoid graph, perfect matching, resonance graph, hypercube
Objavljeno v DKUM: 10.07.2015; Ogledov: 1589; Prenosov: 79
Povezava na celotno besedilo

Opis: Chatrand, Kubicki in Schultz [Aequationes Math. 55 (1998) 129-145] so postavili domnevo, da so vsi dvodelni grafi razdaljni grafi. V tem članku pokažemo, da so vsi grafi podmnožice dvodelnih grafov, in sicer delne kocke, razdaljni grafi.
Ključne besede: matematika, teorija grafov, razdaljni graf, delna kocka, hiperkocka, izometrični podgraf, vložitev, mathematics, graph theory, distance graph, partial cube, hypercube, isometric subgraph, embedding
Objavljeno v DKUM: 10.07.2015; Ogledov: 1435; Prenosov: 112
Povezava na celotno besedilo

Opis: V diplomskem delu z naslovom Clarove formule benzenoidnega sistema in resonančni graf je obravnavana tematika iz področja kemijske teorije grafov. Diplomsko delo obravnava povezavo med Clarovimi formulami Kekulejevega benzenoidnega sistema in maksimalnimi hiperkockami pripadajočega resonančnega grafa. Na začetku so predstavljeni osnovni pojmi in definicije teorije grafov. V nadaljevanju so obravnavani benzenoidni ogljikovodiki in njihova grafična reprezentacija v obliki benzenoidnih sistemov. Obravnavane so Kekuléjeve strukture in Clarove formule benzenoidnega sistema ter predstavitev Clarovih formul z resonantnimi množicami. V osrednjem delu so obravnavani resonančni grafi benzenoidnega sistema, njihovi podgrafi, ki so izomorfni k-dimenzionalnim hiperkockam, ter povezava med Clarovimi formulami Kekuléjevega benzenoidnega sistema in maksimalnimi hiperkockami pripadajočega resonančnega grafa. Končna ugotovitev kaže na to, da je število Clarovih formul Kekuléjevega benzenoidnega sistema B enako številu podgrafov pripadajočega resonančnega grafa R(B), ki so izomorfni Cl(B)-dimenzionalni hiperkocki, kjer Cl(B) označuje Clarovo število danega benzenoidnega sistema.
Ključne besede: benzenoidni sistem, Kekuléjeva struktura, 1-faktor, Clarova formula, Clarovo število, resonantna množica, resonančni graf, hiperkocka
Objavljeno v DKUM: 17.09.2012; Ogledov: 2281; Prenosov: 120
Celotno besedilo (1,58 MB)

Opis: V uvodnem poglavju predstavimo osnovne definicije iz teorije grafov, ki jih potrebujemo v nadaljevanju in povemo še nekaj o kodah v grafih. V naslednjem poglavju definiramo diskriminatorne kode, podamo nekaj primerov in dokažemo spodnjo in zgornjo mejo za moč minimalne diskriminatorne kode izražene glede na število atributov. V tretjem poglavju pokažemo povezavo med diskriminatornimi in identifikacijskimi kodami v hiperkockah. V četrtem poglavju obravnavamo diskriminatorne kode v drevesih in opišemo algoritem linearne časovne zahtevnosti glede na število vozlišč drevesa, ki za dano drevo poišče minimalno diskriminatorno kodo v drevesu in njegovo delovanje prikažemo na primeru. V zadnjem poglavju podamo za vnaprej podano število atributov konstrukcijo dvodelnih ravninskih grafov brez dvojčkov, ki imajo največje število posameznikov in pokažemo povezavo z ravninskimi triangulacijami.
Ključne besede: identifikacijska koda, diskriminatorna koda, dvodelni graf, posameznik, atribut, hiperkocka, drevo, algoritem, ravninski graf
Objavljeno v DKUM: 22.10.2010; Ogledov: 2959; Prenosov: 237
Celotno besedilo (626,67 KB)