| | 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 - 10 / 89
Na začetekNa prejšnjo stran123456789Na naslednjo stranNa konec
1.
Grafi z enolično γ-množico : na magistrskem študijskem programu Izobraževalna matematika - enopredmetna
Darina Cvetrežnik, 2023, magistrsko delo

Opis: V magistrskem delu podrobneje obravnavamo grafe z enolično γ-množico oziroma γ-enolične grafe. To so grafi, ki imajo natanko eno najmanjšo dominantno množico. Sprva zapišemo nekaj osnovnih definicij in trditev o grafih, nato posebej obravnavamo dve družini grafov, in sicer drevesa ter bločne grafe. Podrobneje opišemo dominantno množico in dominantno število grafa. Dokažemo nekaj potrebnih in nekaj zadostnih pogojev za grafe z natanko eno γ-množico. Nato se osredotočimo na drevesa. Predstavimo dve karakterizaciji γ-enoličnih dreves ter obe karakterizaciji posplošimo na γ-enolične bločne grafe. Nazadnje opišemo konstrukcijo γ-enoličnih grafov oziroma zapišemo štiri operacije, ki jih lahko uporabimo nad γ-enoličnimi grafi, da bo na novo dobljen graf ponovno γ-enoličen.
Ključne besede: dominantna množica, γ-enolični grafi, drevesa, bločni grafi.
Objavljeno v DKUM: 17.01.2024; Ogledov: 119; Prenosov: 13
.pdf Celotno besedilo (2,90 MB)

2.
Reševanje problemov z uporabo teorije grafov : na študijskem programu Predmetni učitelj
Katarina Verhnjak, 2023, magistrsko delo

Opis: Pogosto vprašanje pri poučevanju matematike je njena aplikativnost v vsakdanjem življenju. Četudi magistrsko delo ni pedagoške narave, je sestavljeno tako, da se bralec na začetku pouči o teoriji grafov, tekom dela pa to teorijo pretvori v realne probleme. Prvi del magistrskega dela je povzetek najbolj pomembnih definicij in izrekov, brez katerih je razumevanje jezika teorije grafov nemogoče. Prikazani so zgledi družin grafov in dve posebni kategoriji grafov - Eulerjevi in Hamiltonovi grafi. Sledi uporabnost dreves, predvsem je poudarek posvečen vpetim drevesom in problemu iskanja najmanjšega vpetega drevesa v grafih. S tem znanjem lahko namreč načrtujemo optimalna železniška ali namakalna omrežja. Sledi poglavje povezanosti, kjer lahko prevedemo teorijo na problem konstrukcije zanesljivega komunikacijskega omrežja. Nazadnje pa je zbranih nekaj poljudnih nalog iz sklopa razvedrilne matematike za širši razpon bralcev, kjer lahko preverijo razumevanje teorije, saj le z njimi dvomljivcem v matematično uporabnost podamo odgovor.
Ključne besede: aplikacije teorije grafov, Eulerjevi grafi, Hamiltonovi grafi, drevesa, povezanost
Objavljeno v DKUM: 26.04.2023; Ogledov: 380; Prenosov: 33
.pdf Celotno besedilo (3,21 MB)

3.
Vzorčenje soseščine v heterogenih grafih pri grafovskih nevronskih mrežah : magistrsko delo
Vid Keršič, 2022, magistrsko delo

Opis: Grafovske nevronske mreže so v zadnjem času eno izmed najbolj aktivnih področij raziskovanja globokega učenja. Uspešno so bile uporabljene pri problemih, kjer so podatki predstavljeni v obliki grafa, na primer pri analizi družbenih omrežij, napovedovanju prometa, razvoju zdravil itd. Kljub nekaterim zelo dobrim rezultatom pa ostaja še veliko odprtih izzivov pri uporabi nevronskih mrež na zelo velikih grafih, kjer smo omejeni z zmogljivostjo strojne opreme. V magistrskem delu naslavljamo problem uporabe grafovskih nevronskih mrež na obsežnih heterogenih grafih, kjer se med učenjem izvaja vzorčenje soseščine na vsaki plasti mreže, pri čemer se velikosti vzorca omejijo s hiperparametri. Heterogeni grafi vsebujejo več različnih tipov vozlišč in povezav, kar je pri vzorčenju soseščine koristno upoštevati in optimizirati vrednosti hiperparametrov za posamezne tipe povezav. Za reševanje tega problema predstavimo in analiziramo lasten algoritem, ki odpravi potrebo po časovno zahtevnem procesu obravnavanja in nastavljanja hiperparametrov za vse tipe vozlišč ter povezav. Prednosti algoritma z vidika časovne zahtevnosti in uspešnosti klasifikacije prikažemo na dveh grafih – akademskem grafu MAG240M, ki vsebuje več kot 240 milijonov vozlišč in nekaj manj kot 2 milijardi povezav, ter grafu znanja Freebase.
Ključne besede: umetna inteligenca, strojno učenje, heterogeni grafi, grafovske nevronske mreže
Objavljeno v DKUM: 20.10.2022; Ogledov: 440; Prenosov: 48
.pdf Celotno besedilo (1,59 MB)

4.
Nekaj metričnih lastnosti grafovskih produktov
Gregor Rus, 2022, doktorska disertacija

Opis: Doktorska disertacija obravnava koncepta množice vozlišč v splošni legi v grafih in l-razdaljno-uravnoteženost grafov. Oba koncepta sta bila v tej obliki vpeljana nedavno, splošna lega leta 2018 v članku avtorjev Manuela in Klavžarja, l-razdaljna uravnoteženost pa v doktorski diseratciji Freliha leta 2014. V disertaciji so predstavljeni novi rezultati, ki so večinoma povezani z različnimi grafovskimi produkti. Dokazana je točna vrednost gp-števila v kartezičnem produktu poljubnega števila poti, natančneje, da velja $\gp(P^{\cp,n}) = 2^{2^{n-1}}$. Dokazana je točna vrednost gp-števila v produktu poti in cikla in produkta dveh ciklov. Dokazana je tudi točna vrednost gp-števila v nekaterih Kneserjevih grafih. V razdelku, ki se ukvarja z l-razdaljno-uravnoteženostjo, je pokazan pogoj, kdaj je leksikografski produkt grafov $G[H]$ $\ell$-razdaljno-uravnotežen za poljuben $\ell \in \{3,\ldots,\diam(G)\}$. Prav tako je dokazano, kdaj je $\ell$-razdaljno-uravnotežen korona produkt. Določimo pa tudi pogoj, kdaj je $\ell$-razdaljno uravnotežen kartezični produkt $G\cp K_n.$
Ključne besede: teorija grafov, množica vozlišč v splošni legi, gp-število, grafovski produkti, poti, cikli, razdaljno-uravnoteženi grafi, l-razdaljno-uravnoteženi grafi
Objavljeno v DKUM: 07.10.2022; Ogledov: 587; Prenosov: 46
.pdf Celotno besedilo (965,92 KB)

5.
Pakirno barvanje grafa : na študijskem programu 2. stopnje Matematika
Tomaž Ličina, 2021, magistrsko delo

Opis: Pakirno barvanje grafe je dobro barvanje vozlišč, pri katerem sta poljubni dve vozlišči z isto barvo i na razdalji večji kot i. Pakirno kromatično število je najmanjše število barv, ki jih potrebujemo za tako barvanje grafa. V magistrskem delu obravnavamo pakirno kromatično število nekaterih družin grafov in zvezo pakirnega kromatičnega števila z drugimi grafovskimi invariantami. Podrobneje obravnavamo zvezo med kličnim, kromatičnim in pakirnim kromatičnim številom. V prvem delu proučujemo pakirno kromatično število na osnovnih družinah grafov, na drevesih, kartezičnih produktih grafov in na grafih Mycielskega. V naslednjem delu obravnavamo grafe z majhnimi pakirnimi kromatičnimi števili in pokažemo, da je preveriti, ali ima graf pakirno kromatično število enako 4, NP-težek problem. V tretjem delu prikažemo zvezo pakirnega kromatičnega števila z neodvisnostnim številom grafa, najmanjšim vozliščnim pokritjem grafa in maksimalno stopnjo v grafu. V zadnjem delu raziskujemo zvezo med kličnim, kromatičnim in pakirnim kromatičnim številom. Poiščemo trojice naravnih števil (a,b,c) za katere obstaja graf G s kličnim številom a, kromatičnim številom b in pakirnim kromatičnim številom c.
Ključne besede: barvanje grafov, pakirno barvanje grafov, drevesa, grafi Mycielskega, kartezični produkt grafov, klično število, neodvisnostno število, vozliščno pokritje
Objavljeno v DKUM: 12.01.2022; Ogledov: 624; Prenosov: 50
.pdf Celotno besedilo (613,60 KB)
Gradivo ima več datotek! Več...

6.
KARTEZIČNI PRODUKT GRAFOV
Iris Merkač, 2009, diplomsko delo

Opis: Diplomsko delo je sestavljeno iz treh poglavij. V prvem poglavju predstavimo osnovne pojme teorije grafov in podamo definicije ter osnovne lastnosti kartezičnega produkta dveh ali večih grafov. V naslednjem poglavju podamo definiciji hiperkocke in delne kocke, ter spoznamo da so hiperkocke najpreprostejši razred kartezičnega produkta. Nato se posvetimo Djoković-Winklerjevi relaciji Θ, za katero ugotovimo, da je definirana na množici povezav grafa in da je bistvenega pomena za kartezični produkt. Poglavje zaključimo s preprostim algoritmom prepoznavanja hiperkock. V zadnjem poglavju definiramo Hammingove grafe in delne Hammingove grafe. Opazimo tudi, da so hiperkocke edini dvodelni Hammingovi grafi. V nadaljevanju raziščemo kanonično vložitev grafov v kartezični produkt dveh ali večih kvocientnih grafov, katere dobimo iz ekvivalenčnih razredov tranzitivne ovojnice relacije Θ. Nato dokažemo Graham-Winklerjev izrek, ki pove, da je kanonična vložitev izometrija. Ker je izračunavanje tranzitivne ovojnice relacije Θ bistveno pri izračunavanju kanonične vložitve, na koncu podamo algoritem, ki izračuna tranzitivno ovojnico relacije Θ.
Ključne besede: kartezični produkt, hiperkocke, delne kocke, Hammingovi grafi, relacija Θ, kvocientni graf, kanonična vložitev
Objavljeno v DKUM: 27.01.2021; Ogledov: 1033; Prenosov: 78
.pdf Celotno besedilo (411,17 KB)

7.
Nekatere s pakiranji povezane lastnosti grafov
Dragana Božović, 2020, doktorska disertacija

Opis: V disertaciji se ukvarjamo z različnimi problemi, povezanimi s pakiranji. Disertacija je sestavljena iz štirih delov. Prvi del je namenjen grafom, ki imajo enolično pakirno množico največje moči. Najprej predstavimo nekatere lastnosti teh grafov. Nato podamo še dve karakterizaciji dreves z enolično pakirno množico. V drugem delu vpeljemo pojem dimenzije incidenčnosti, ki je neposredno povezana z 2-pakirnim številom grafa, in določimo formulo za njen izračun. Dokažemo, da je problem iskanja incidenčne dimenzije grafa v splošnem NP-poln. Tretji del namenimo pakirnemu kromatičnemu številu leksikografskega produkta grafov. Določimo njegovo spodnjo in zgornjo mejo ter izboljšano zgornjo mejo za primer, ko je prvi faktor v produktu izomorfen poti. V zadnjem delu se posvetimo učinkoviti odprti dominaciji produktov digrafov. Okarakteriziramo učinkovito odprto dominirane direktne in leksikografske produkte digrafov. Pri kartezičnem produktu okarakteriziramo tiste, kjer je prvi faktor usmerjena pot, usmerjen cikel ali zvezda z enim izvorom. Predstavimo tudi karakterizacijo učinkovito odprto dominiranega krepkega produkta, katerega temeljni graf obeh faktorjev je monocikličen graf.
Ključne besede: pakirna množica, enolično največje pakiranje, dimenzija incidenčnosti, generator incidenčnosti, pakirno kromatično število, leksikografski produkt grafov, učinkovita odprta dominacija, usmerjeni grafi, produkti usmerjenih grafov
Objavljeno v DKUM: 27.11.2020; Ogledov: 1313; Prenosov: 165
.pdf Celotno besedilo (753,30 KB)

8.
Število kromatične stabilnosti povezav
Tjaša Kos, 2020, magistrsko delo

Opis: V magistrskem delu predstavimo število kromatične stabilnosti povezav grafa $G$. Najprej definiramo osnovne pojme teorije grafov in dokažemo nekaj lastnosti števila kromatične stabilnosti povezav. Opišemo grafe Mycielskega, njihovo konstrukcijo ter dokažemo, da je kromatično število grafa Mycielskega $M(G)$ za ena večje od kromatičnega števila grafa $G$. Nato se osredotočimo na število kromatične stabilnosti povezav posebnih družin grafov. Raziskujemo disjunktno unijo grafov, kartezični produkt, spoj grafov ter posebne družin grafov, ki jih dobimo s spojem nekaterih družin grafov. V nadaljevanju opišemo meje števila kromatične stabilnosti povezav. Dokažemo več spodnjih in zgornjih mej za $es_{\chi}(G)$. Osredotočimo se tudi na rezultate tipa Nordhaus-Gaddum in dokažemo zgornjo mejo za vsoto števila kromatične stabilnosti povezav grafa $G$ in njegovega komplementa $\overline{G}$. Nazadnje raziskujemo grafe z $es_{\chi}(G)=1$. Dokažemo, da je $es_{\chi}(G)=1$ natanko tedaj, ko je vezano kromatično število enako $1$. Še več, predstavimo več potrebnih pogojev za graf $G$ z $es_{\chi}(G)=1$.
Ključne besede: število kromatične stabilnosti povezav, kromatično število, dvodelni grafi, kartezični produkt grafov, grafi Mycielskega, neenakost tipa Nordhaus-Gaddum, vezano kromatično število
Objavljeno v DKUM: 29.10.2020; Ogledov: 706; Prenosov: 63
.pdf Celotno besedilo (2,21 MB)

9.
Matematične uganke v teoriji grafov
Maja Javornik, 2019, magistrsko delo

Opis: V magistrskem delu je predstavljenih več učencem zanimivih matemati\v cnih ugank. Najprej obravnavamo različne matematične uganke skozi zgodovino vse od magi\v cnih kvadratov do ugank novej\v sega \v casa kot je rubikova kocka. Nato se osredotočimo na teorijo grafov in predstavimo ikozaedersko igro, problem Köningsber\v ski mostov, problem prečkanja reke brez mostov in problem \v stirih konjev. Kot uvod v obravnavo kitajskih prstanov predstavimo legendo o stolpu iz Brahme in vpeljemo Hanojske stolpe. Doka\v zemo optimalno re\v sitev Hanojskega stolpa z $n \in{\mathbb{N}}_0$ diski. Med drugimi predstavimo variacijo Hanojskega stolpa, ki se imenuje zamenjevalni Hanojski stolp in predstavimo zgodovino kitajskih prstanov. Nazadnje problem kitajskih prstanov podrobneje raziščemo in doka\v zemo formulo za najhitrejšo rešitev problema.
Ključne besede: Kitajski prstani, Hanojski stolpi, Hamiltonovi grafi, Eulerjevi grafi, ravninski grafi
Objavljeno v DKUM: 23.01.2020; Ogledov: 1227; Prenosov: 189
.pdf Celotno besedilo (3,34 MB)

10.
Igra policajev in roparjev na grafih
Tina Bastašić, 2019, magistrsko delo

Opis: V magistrskem delu bomo predstavli igro policajev in roparjev na grafih, kjer se policaji in ropar premikajo po vozliščih grafa. Cilj policajev je, da eden izmed njih uspe priti na enako vozlišče kot ropar. Grafom, na katerih ima v igri z enim policajem policaj zmagovalno strategijo, pravimo policaj-zmaga grafi. Najmanjše število policajev, ki je potrebnih, da imajo zmagovalno strategijo na grafu G, imenujemo varnostno število grafa G. Poleg igre policajev in roparjev bomo predstavili še druge različice te igre. Varnostno število grafa bomo izračunali za nekatere preproste družine grafov in predstavili spodnje in zgornje meje varnostnega števila grafa. Nato bomo pokazali, kako varnostno število retraktov grafa vpliva na varnostno število originalnega grafa. Kot bomo videli, retrakti grafov igrajo pomembno vlogo pri karakterizaciji policaj-zmaga grafov. Dokažemo, da so policaj-zmaga grafi natanko odstranljivi grafi. Predstavimo tudi policaj-zmaga urejenost in policaj-zmaga strategijo. Na koncu še dokažemo, da so tudi mostovni grafi policaj-zmaga grafi.
Ključne besede: igra policajev in roparjev, varnostno število grafa, policaj-zmaga grafi, odstranljivi grafi, mostovni grafi
Objavljeno v DKUM: 05.11.2019; Ogledov: 1239; Prenosov: 95
.pdf Celotno besedilo (318,60 KB)

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