1. Računanje Wienerjevega indeksa uteženega grafa z združevanjem ?*-razredovSimon Brezovnik, 2018, magistrsko delo Opis: Wienerjev indeks igra pomembno vlogo pri poznavanju kemijskih in fizikalnih lastnosti različnih spojin. Predstavlja vsoto razdalj med vsemi neurejenimi pari vozlišč znotraj grafa. Uteženi graf je graf skupaj s funkcijo, ki vsakemu vozlišču predpiše realno število, imenovano utež. Magistrsko delo obravnava računanje Wienerjevega indeksa uteženega grafa s pomočjo reduciranja na posebno skupino grafov, tj. kvocientne grafe in nadaljnje redukcije kvocientnih grafov na enostavnejše grafe. V prvem delu predstavimo nekaj osnovnih definicij in ugotovitev teorije grafov. Zapišemo osnovno definicijo Wienerjevega indeksa in njegovo razširitev na utežene grafe. Spoznamo Djoković-Winklerjevo relacijo in njeno tranzitivno zaprtje. Ob koncu prvega dela spoznamo definicijo delne kocke in zapišemo njeno novo karakterizacijo. Osrednji del magistrske naloge podaja novi metodi za izračun Wienerjevega indeksa nekaterih uteženih grafov. Glavni izrek povezuje izračun Wienerjevega indeksa uteženega grafa z vsoto Wienerjevih indeksov uteženih kvocientnih grafov prvotnega grafa po vseh Θ^∗-razredih, kjer Θ^∗ predstavlja tranzitivno zaprtje Djoković-Winklerjeve relacije. V zadnjem delu predstavimo uporabo zgoraj omenjenega izreka na posebni družini grafov G_n, na benzenoidnih sistemih ter na linearnih fenilenih F_n.
Ključne besede: Wienerjev indeks, delna kocka, uteženi graf, kvocientni graf, Djoković-Winklerjeva relacija, tranzitivno zaprtje
Objavljeno v DKUM: 24.09.2018; Ogledov: 1145; Prenosov: 144
 Celotno besedilo (1,00 MB) |
2. Lattice embeddings of treesWilfried Imrich, Matjaž Kovše, 2009, izvirni znanstveni članek Opis: Predstavljen je algoritem časovno linearne zahtevnosti, ki na izometričen način vloži dano drevo ▫$T$▫ v celoštevilsko mrežo najmanjše možne dimenzije in omogoča izračun mrežnih koordinat vozlišč drevesa ▫$T$▫ v optimalnem času.
Ključne besede: matematika, teorija grafov, drevo, izometrična vložitev, mrežna vložitev, delna kocka, mathematics, graph theory, lattice embedding, isometric embedding, partial cube, tree
Objavljeno v DKUM: 10.07.2015; Ogledov: 1003; Prenosov: 168
 Povezava na celotno besedilo |
3. Partial cubes are distance graphsMelita Gorše Pihler, Janez Žerovnik, 2008, objavljeni znanstveni prispevek na konferenci 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: 1432; Prenosov: 159
Povezava na celotno besedilo |
4. Characterizing almost-median graphsBoštjan Brešar, 2007, izvirni znanstveni članek Opis: Skoraj medianski grafi in semi-medianski grafi sta dve naravni posplošitvi dobro znanega razreda medianskih grafov. V članku dokažemo, da je semi-medianski graf skoraj medianski, če in samo če ne vsebuje konveksnega cikla dolžine večje kot štiri.
Ključne besede: matematika, teorija grafov, medianski graf, konveksen cikel, delna kocka, mathematics, graf theory, median graph, convex cycle, partial cube
Objavljeno v DKUM: 10.07.2015; Ogledov: 1281; Prenosov: 104
Povezava na celotno besedilo |
5. Partial cubes are distance graphsMelita Gorše Pihler, Janez Žerovnik, 2005 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 |
6. On cubic and edge-critical isometric subgraphs of hypercubesC. Paul Bonnington, Sandi Klavžar, Alenka Lipovec, 2002 Opis: Predstavljene so vse kubične delne kocke do 30 točk in vse po povezavah kritične delne kocke do 14 točk. Seznama sta bila potrjena z računalniškim iskanjem. Konstruirane so tudi netrivialne kubične delne kocke na 36, 42 in 48 točkah.
Ključne besede: matematika, teorija grafov, delna kocka, hiperkocka, kubični graf, računalniško iskanje, mathematics, graph theory, partial cube, hypercube, cubic graph, computer searching
Objavljeno v DKUM: 10.07.2015; Ogledov: 1207; Prenosov: 39
Povezava na celotno besedilo |
