1. Graf deliteljev niča komutativnega kolobarjaEva Petauer, 2025, master's thesis Abstract: Graf deliteljev niča $\Gamma(R)$ komutativnega kolobarja $R$ povezuje teorijo kolobarjev s teorijo grafov. Vozlišča grafa deliteljev niča so neničelni delitelji niča, povezava med vozliščema $x$ in $y$ pa obstaja, kadar je $xy=0$. Cilj naloge je raziskati, kako lastnosti kolobarja (noetherskost, artinskost, lokalnost, končnost) vplivajo na strukturo grafa deliteljev niča ter obratno, katere informacije o kolobarju lahko razberemo iz grafa deliteljev niča.
Vsak graf na vsaj treh vozliščih lahko predstavimo kot graf deliteljev niča nekega kolobarja, za grafe na več kot treh vozliščih pa to ne drži. Velja, da je vsak graf deliteljev niča nekega komutativnega kolobarja povezan in da ima premer manjši od štiri. Če vsebuje cikel, je dolžina najkrajšega cikla manjša ali enaka sedem. Če obravnavamo komutativne artinske kolobarje, katerih graf deliteljev niča vsebuje cikel, je dolžina najkrajšega cikla manjša ali enaka štiri. V grafu deliteljev niča obstaja vozlišče, ki je povezano z vsakim drugim vozliščem natanko takrat, ko je bodisi $R \cong \mathbb{Z}_2 \times A$, pri čemer je $A$ cel kolobar bodisi je $Z_0(R)$ anihilatorski ideal. Obravnavamo še polne grafe in pokažemo, da če je $\Gamma(R)$ polni graf, potem je bodisi $R \cong \mathbb{Z}_2 \times \mathbb{Z}_2$ bodisi je $R$ lokalni kolobar. Na koncu še dokažemo, da je graf deliteljev niča z več kot tremi vozlišči graf zvezda natanko takrat, ko je $R \cong \mathbb{Z}_2 \times F$, pri čemer je $F$ končno polje. Velja tudi, da ima graf zvezda $p^n$ vozlišč, pri čemer je $p$ neko praštevilo in $n \in \mathbb{N}_0$ in obratno, vsak graf zvezda velikosti $p^n$ je lahko graf deliteljev niča.
Keywords: komutativen kolobar, delitelj niča, graf deliteljev niča
Published in DKUM: 08.10.2025; Views: 0; Downloads: 12
 Full text (1,16 MB) |
2. Razširjanje in ojačano pronicanje v produktih grafovJaka Hedžet, 2025, doctoral dissertation Abstract: V doktorski disertaciji obravnavamo spreminjanje stanja vozlišč grafa po pravilu procesa, imenovanega $r$-ojačano pronicanje. Bolj podrobno se lotimo preučevanja tega procesa na standardnih grafovskih produktih in vpeljemo nov pojem, imenovan razširjanje, ki sestoji iz kombinacije pravil ojačanega pronicanja ter ničelne prisile oziroma $k$-prisile. Po uvodnih poglavjih je disertacija razdeljena na pet delov, znotraj katerih predstavimo rezultate na omenjeno temo.
V prvem delu obravnavamo proces pronicanja na kartezičnih mrežah, ki so kartezični produkti poti. Natančneje, določimo $3$-ojačitveno število pronicanja za kartezične mreže velikosti $3 \times n$ in $5 \times n$, kjer je $n$ poljubno naravno število. Dodatno omejimo vrednost $3$-ojačitvenega števila za kartezično mrežo velikosti $4\times n$ na dve možni vrednosti.
V drugem delu disertacije se usmerimo v preučevanje pronicanja na krepkih produktih grafov, in sicer za poljubno število faktorjev. Določimo vrednosti za prag $r$, pri katerih $r$-ojačitveno število produkta $k$ grafov zasede svojo trivialno spodnjo mejo, ki je enaka $r$. Nadalje postavimo dodatne pogoje za faktorje krepkega produkta, pri katerih ohranimo enako lastnost $r$-ojačitvenega števila za višji prag $r$. Posebej se lotimo tudi najmanjšega primera, ki ni zajet v teh rezultatih, to je produkt dveh faktorjev in prag $r=3$, kjer karakteriziramo tiste krepke produkte, katerih $3$-ojačitveno število je enako $3$. Raziskavo razširimo na neskončne grafe, kjer opazujemo obnašanje $r$-ojačitvenega števila na krepkih produktih dvosmernih neskončnih poti.
V tretjem delu se lotimo še zadnjega izmed treh standardnih komutativnih grafovskih produktov, to je direktnega produkta grafov. Določimo nekaj zgornjih mej za $r$-ojačitveno število direktnega produkta dveh grafov in karakteriziramo grafe, ki dosežejo dve zgornji meji v primeru praga $r=2$. Določimo tudi natančne vrednosti za $r$-ojačitveno število produkta dveh poti poljubnih dolžin in med drugim okarakteriziramo tiste direktne produkte grafov, katerih $2$-ojačitveno število je enako redu enega izmed faktorjev.
Četrti in zadnji del doktorske disertacije posvetimo vpeljavi in preučevanju pojma razširjanje. Posplošimo do sedaj znane rezultate iz procesov pronicanja in $k$-prisile ter zapolnimo nekatere vrzeli pri rezultatih o kartezičnih mrežah in dokažemo, da je problem razširjanja NP-težek. Z vidika razširjanja dodatno preučujemo kubične grafe brez krempljev, kjer določimo bodisi natančne vrednosti, bodisi meje za vse variante razširjevalnega števila, in drevesa, kjer predstavimo algoritem za iskanje najmanjše širitvene množice poljubnega drevesa.
Keywords: ojačano pronicanje, ojačitveno število pronicanja, razširjanje, kartezični produkt, direktni produkt, krepki produkt, mreža, kubični graf, drevo.
Published in DKUM: 06.10.2025; Views: 0; Downloads: 19
Full text (581,56 KB) |
3. Kockovni komplementi posplošenih Fibonaccijevih kock : na enovitem študijskem programu Predmetni učitelj, usmeritev izobraževalna matematikaAndrej Zobovič, 2025, master's thesis Abstract: V magistrskem delu preučujemo kockovne komplemente posplošenih Fibonaccijevih kock Q_h^C(f). Ti grafi nastanejo tako, da najprej iz hiperkocke Q_h odstranimo vsa vozlišča, ki vsebujejo niz f. Ce je G induciran podgraf od Q_h, potem je kockovni komplement grafa G graf, induciran z množico vozlišč grafa Q_h, ki niso v G. Kockovni komplement posplošene Fibonaccijeve kocke je tako podgraf od Q_h, induciran z množico vseh vozlišč, ki vsebujejo niz f. Osrednji del magistrskega dela je namenjen analizi povezanosti teh grafov. Z upoštevanjem struktur binarnih nizov, kot je parameter simetrije r(f) in podobnost začetka in konca niza π(f), podamo pogoje, pod katerimi so ti grafi povezani ali nepovezani. V nadaljevanju nas zanima tudi, kdaj ti grafi zadoščajo pogojem za delne kocke in medianske grafe, kar raziskujemo z uporabo teorije marjetičnih kock ter ustreznih karakterizacij.
Keywords: posplošena Fibonaccijeva kocka, Fibonaccijeva kocka, kockovni komplement, hiperkocka, binarni niz, delna kocka, medianski graf, graf, povezanost grafov, Hammingova razdalja
Published in DKUM: 19.06.2025; Views: 0; Downloads: 14
Full text (1,35 MB) |
4. Implementacija grafa raztrosa in grafa grupirane matrike v ogrodju NiaARM za vizualizacijo asociacijskih pravilMiha Bukovnik, 2024, undergraduate thesis Abstract: Podatkovno rudarjenje je ključnega pomena za pridobivanje dragocenih informacij iz velikih podatkovnih zbirk, s široko uporabo na različnih področjih. Rudarjenje asociacijskih pravil odkriva vzorce in povezave v podatkih, kar je izredno uporabno v telekomunikacijah, tržni analizi, upravljanju tveganj ter drugih področjih. Vizualizacija teh pravil z grafom raztrosa in grafom grupirane matrike omogoča boljše razumevanje in analizo pravil. Cilj diplomskega dela je implementacija omenjenih vizualizacijskih tehnik v ogrodju NiaARM, vključno s primerjalno analizo vizualizacij iz paketa arulesViz. Ugotovitve nakazujejo na uporabnost tako NiaARMa kot arulesViza s svojimi specifičnostmi. Medtem ko ogrodje NiaARM omogoča visoko stopnjo interaktivnosti in prilagodljivosti v vizualizaciji, pa paket arulesViz, z večjo podporo skupnosti in dodatnimi viri pomoči, ponuja hitrejše in zanesljivejše vizualizacije.
Keywords: asociacijska pravila, rudarjenje asociacijskih pravil, vizualizacijske tehnike, graf, NiaARM
Published in DKUM: 22.10.2024; Views: 0; Downloads: 40
Full text (1,71 MB) |
5. Distance formula for direct-co-direct product in the case of disconnected factorsAleksander Kelenc, Iztok Peterin, 2023, original scientific article Abstract: Direktni-ko-direktni produkt ▫$G\circledast H$▫ grafov ▫$G$▫ in ▫$H$▫ je graf na množizi vozlišč ▫$V(G)\times V(H)$▫. Vozlišči ▫$(g,h)$▫ in ▫$(g',h')$▫ sta sosednji, če je ▫$gg'\in E(G)$▫ in ▫$hh'\in E(H)$▫ ali ▫$gg'\notin E(G)$▫ in ▫$hh'\notin E(H)$▫. Naj bo največ eden izmed faktorjev ▫$G$▫ in ▫$H$▫ povezan. Pokažemo da je razdalja med dvema vozliščema v ▫$G\circledast H$▫ omejena s tri, razen v majhnem številu izjem. Vse izjeme so natančno popisane, kar prinese razdaljno formulo za ▫$G\circledast H$▫.
Keywords: direktni-ko-direktni produkt, razdalja, ekscentričnost, nepovezan graf, direct-co-direct product, distance, eccentricity, disconnected graphs
Published in DKUM: 21.05.2024; Views: 115; Downloads: 13
Full text (449,36 KB)
This document has many files! More... |
6. |
7. Analiza podatkov o prometnih tokovih in mobilnostiAjda Pretnar Žagar, Tomaž Hočevar, Tomaž Curk, 2021, published scientific conference contribution Abstract: Podatki o prometu nam lahko pomagajo odgovoriti na več vprašanj o mobilnosti ljudi. Opaženi vzorci razkrivajo, kako narod vozi, kaj počne med tednom in med konci tedna ter kako se navade ljudi spreminjajo čez leto. Tovrstne informacije nam pomagajo razumeti sedanje in prihodnje vedenje turistov ter omogočajo prilagoditev in vpliv na promet. Analizirali smo javno dostopen nabor podatkov števcev cestnega prometa v Sloveniji. Razvili smo računske metode za iskanje zanimivih vzorcev v prometu. Lokacije števcev prometa smo gručili glede na podobnosti v opazovanih prometnih profilih. Takšna avtomatizirana kvantitativna analiza velike količine podatkov je dragoceno orodje za odkrivanje zanimivih lastnosti v prometu. Odprti podatki števcev prometa v realnem času nudijo še globlji vpogled v mobilnost. Na podlagi opaženih korelacij med bližnjimi števci prometa smo ustvarili model cestnega omrežja. Z modelom smo analizirali prometni tok po cestnem omrežju in razvili metodo za štetje prometa v določeno izbrano regijo in iz nje.
Keywords: promet, števci, profil, graf, tok
Published in DKUM: 24.01.2024; Views: 301; Downloads: 12
Full text (24,52 MB)
This document has many files! More... |
8. Meje za mavrična dominantna števila : magistrsko deloKlavdija Zelko, 2023, master's thesis Abstract: Mavrično dominacijo na grafu $G$, z (neprazno) množico vozlišč in povezav ter množico s $k$ barvami, opišemo kot funkcijo $f$, ki vsako vozlišče označi s poljubno podmnožico barv tako, da imajo vsa tista vozlišča, ki jim je prirejena prazna množica, v svoji soseščini vseh $k$ barv. Funkciji $f$ tedaj pravimo $k$-mavrična dominantna funkcija grafa $G$. Vsota moči vseh oznak na vozliščih je vrednost $k$-mavrično dominantne funkcije. Najmanjša vrednost izmed vseh takih funkcij na grafu $G$ se imenuje $k$-mavrično dominantno število grafa $G$. V magistrskem delu podamo nekaj točnih vrednosti in zgornjih mej za $k$-mavrična dominantna števila. Večji poudarek damo na meje za 2- in 3-mavrično dominantna števila. Dokažemo dve splošni zgornji meji 2-mavrično dominantnega števila ter opišemo meje za 3-mavrično dominantna števila. Na koncu dela sledijo meje za $k$-mavrično dominantna števila, za katera je $k > 3$. V nekaterih primerih opišemo družine grafov, ki dosežejo enakost meje in jih dokažemo.
Keywords: graf, dominantno število, mavrična dominantna funkcija, mavrično dominantno število
Published in DKUM: 02.02.2023; Views: 766; Downloads: 59
Full text (3,91 MB) |
9. Grafični prikaz Kruskalovega algoritma v 3D prostoru : diplomsko deloJurij Cerar, 2022, undergraduate thesis Abstract: V diplomskem delu smo implementirali aplikacijo za demonstracijo Kruskalovega
algoritma nad oblaki točk LiDAR v 3D prostoru ter izmerili čas algoritma in čas
upodabljanja, kakor tudi pomnilniško zahtevnost algoritma. Poleg tega smo tudi
primerjali uporabo evklidske razdalje in intenzitete kot cene povezav. Zato smo ustvarili namizno aplikacijo, ki prebere točke LiDAR in jih izriše v 3D prostoru. Nato izvede Kruskalov algoritem nad temi točkami ter prikaže vmesne rezultate algoritma. Zaradi velikega števila začetnih povezav grafa smo uvedli aproksimacijo s pomočjo enakomerne mreže. Ugotovili smo da je uporaba intenzitete kot cene hitrejša od uporabe evklidske razdalje. Ugotovili smo tudi, da poraba pomnilnika narašča linearno glede na število vozlišč. Poleg tega smo preučili, kako nam gradnja minimalnega vpetega drevesa omogoča lažje preučevanje točk.
Keywords: Kruskalov algoritem, graf, format LAS, OpenGL
Published in DKUM: 21.12.2022; Views: 757; Downloads: 106
Full text (1,54 MB) |
10. Sodobne igre barvanj in sorodne igre na grafihDaša Štesl, 2022, doctoral dissertation Abstract: V doktorski disertaciji obravnavamo v zadnjih letih vpeljane variacije klasične igre barvanja in njim sorodne igre na grafih. Doktorsko delo sestoji iz štirih delov, znotraj katerih predstavimo nova spoznanja na omenjeno temo.
V prvem delu disertacije obravnavamo indicirano igro barvanja kartezičnih produktov grafov. Natančneje, določimo indicirano igralno kromatično število kartezičnih produktov grafov, katerih indicirano kromatično število znaša 3, s polnim dvodelnim grafom. Dodatno obravnavamo indicirano kromatično število kartezičnih produktov bločnih grafov in dreves ter indicirano kromatično število kartezičnega produkta dveh ciklov.
V drugem delu disertacije se posvetimo študiji štirih variacij neodvisnostne igre barvanja, ki so posebna oblika klasične igre barvanja, pri kateri igralca ne preideta na višjo raven, dokler ne izčrpata vseh možnosti za uporabo dane barve. Dobljene igralne invariante primerjamo med seboj in s klasičnim igralnim kromatičnim številom. Poleg tega ugotovimo, da neodvisnostno igralno kromatično število v razredu dreves ni omejeno.
V tretjem delu preučujemo vozliščno kritične grafe glede na klasično igralno kromatično število, glede na indicirano kromatično število in glede na A-neodvisnostno ter AB-neodvisnostno igralno kromatično število. Med drugim obravnavamo vprašanje povezanosti grafov, ki so kritični glede na omenjene igralne grafovske invariante, obnašanje dane igralne invariante ob odstranitvi poljubnega vozlišča iz igralno vozliščno kritičnega grafa ter karakteriziramo igralno vozliščno kritične grafe, ki imajo majhno vrednost pripadajoče invariante.
Zadnji del doktorske disertacije posvetimo neodvisni dominacijski igri s preprečevanjem. Določimo neodvisni dominantni števili s preprečevanjem za poti in cikle. Poleg tega postavimo meje za obe variaciji omenjene igre ter karakteriziramo (povezane) grafe, ki dosežejo dobljeni meji. Dodatno opozorimo na tesno povezavo med neodvisno dominacijsko igro s preprečevanjem in pakirno igro barvanja v grafih z diametrom 2.
Keywords: igra barvanja, indicirana igra barvanja, neodvisnostna igra barvanja, neodvisna dominacijska igra, pakirna igra barvanja, kartezični produkt, drevo, vozliščno kritičen graf
Published in DKUM: 25.10.2022; Views: 703; Downloads: 80
Full text (614,26 KB) |
