| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 7 / 7
First pagePrevious page1Next pageLast page
1.
Število kromatične stabilnosti povezav
Tjaša Kos, 2020, master's thesis

Abstract: 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$.
Keywords: število kromatične stabilnosti povezav, kromatično število, dvodelni grafi, kartezični produkt grafov, grafi Mycielskega, neenakost tipa Nordhaus-Gaddum, vezano kromatično število
Published: 29.10.2020; Views: 150; Downloads: 16
.pdf Full text (2,21 MB)

2.
Matematične uganke v teoriji grafov
Maja Javornik, 2019, master's thesis

Abstract: 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.
Keywords: Kitajski prstani, Hanojski stolpi, Hamiltonovi grafi, Eulerjevi grafi, ravninski grafi
Published: 23.01.2020; Views: 437; Downloads: 51
.pdf Full text (3,34 MB)

3.
Igra policajev in roparjev na grafih
Tina Bastašić, 2019, master's thesis

Abstract: 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.
Keywords: igra policajev in roparjev, varnostno število grafa, policaj-zmaga grafi, odstranljivi grafi, mostovni grafi
Published: 05.11.2019; Views: 477; Downloads: 63
.pdf Full text (318,60 KB)

4.
Contributions to the Study of Contemporary Domination Invariants of Graphs
2019, doctoral dissertation

Abstract: This doctoral dissertation is devoted to contemporary domination concepts, such as the Grundy domination, the convex domination, the isometric domination and the total domination. Our main focus is to study their structure and algorithmic properties. Four Grundy domination invariants are presented, namely the Grundy domination number, the Grundy total domination number, the Z-Grundy domination number, and the L-Grundy domination number. Some bounds and properties of Grundy domination invariants are proven. All four Grundy domination parameters are studied on trees, bipartite distance-hereditary graphs, split graphs, interval graphs, Sierpi\'nski graphs, Kneser graphs and $P_4$-tidy graphs. Graphs with equal total domination number and Grundy total domination number are investigated. Convex domination and isometric domination are studied on (weak) dominating pair graphs. For the chordal dominating pair graphs we present a polynomial algorithm to compute the convex domination number, and prove the NP-completeness of the corresponding decision problem for the chordal weak dominating pair graphs. For the isometric domination number of weak dominating pair graphs an efficient algorithm is presented. Total domination is studied on the Cartesian product of graphs. We dedicate ourselves to graphs for which the equality holds in Ho's theorem, which states that the total domination number of the Cartesian product of any two graphs without isolated vertices is at least one half of the product of their total domination numbers.
Keywords: Grundy domination, Grundy total domination, Z-Grundy domination, L-Grundy domination, convex domination, isometric domination, total domination, trees, split graphs, interval graphs, Sierpi\'nski graphs, Kneser graphs, modular decomposition, dominating pair graphs, Cartesian product
Published: 23.10.2019; Views: 503; Downloads: 11
.pdf Full text (764,69 KB)
This document has many files! More...

5.
Neodvisna dominacija na grafih
Nina Črešnjevec, 2018, master's thesis

Abstract: V magistrskem delu obravnavamo različne tipe dominacij in sicer dominantno število, neodvisnostno število, neodvisno dominantno število in zgornje dominantno število. Neodvisno dominantno število je raziskano na različnih družinah grafov kot tudi na različnih grafovskih produktih. V prvem delu magistrske naloge smo navedli vse pojme, trditve, izreke, ki jih potrebujemo za razumevanje glavnega problema magistrske naloge. Predstavimo tudi različne razrede grafov in različne dominacije v grafih. V drugem poglavju obravnavamo različne meje neodvisnega dominantnega števila. Predstavljene so splošne meje, ki veljajo na različnih družinah grafov in meje, ki veljajo za dvodelne grafe. Tretje poglavje pa se nanaša na neodvisno dominantno število krepkega, korenskega in kartezičnega produkta. Za nekatere od teh produktov smo prikazali tudi rezultate o neodvisnostnem številu in dominantnem številu.
Keywords: dominantno število, neodvisno dominantno število, neodvisnostno število, dominantno popolni grafi, dobro pokriti grafi, grafovski produkti
Published: 13.07.2018; Views: 463; Downloads: 68
.pdf Full text (1,30 MB)

6.
Integrirani avtoregresijski modeli s premikajočimi sredinami za napovedovanje porabe električne energije
Matic Tajnik, 2016, master's thesis

Abstract: Magistrsko delo obravnava primerjavo pristopov različnih tehnik k napovedovanju porabe električne energije. Delo je razdeljeno na pet poglavij. V prvem poglavju so predstavljene tehnike modeliranja, ki so potrebne za razumevanje opravljenih analiz in nadaljnih primerjav, to so: večstopenjska linearna regresija, metoda podpornih vektorjev, naključni gozd in mehka logika. Pregledu metod modeliranja sledi poglavje, kjer so predstavljeni indeksi kakovosti modelov. Razdeljeni so v pet podpoglavij: napake, determinacijski koeficient, popravljen determinacijski koeficient, statistični F-test in informacijski kriteriji. V tretjem poglavju so podrobno predstavljeni in razčlenjeni integrirani avtoregresijski modeli premikajoče sredine (ARIMA). Naprej je predstavljena avtokorelacija in njene funkcije, sledi definicija stacionarnosti in diferenciranja časovne vrste, predstavljeni so sezonski ARIMA modeli, na koncu sledijo koraki Box-Jenkins metodologije za izgradnjo ARIMA modelov. V četrtem poglavju je povzeta uporaba taksonomije, izdelana je razširitev taksonomije napovedovanja v elektrogospodarstvu, predstavljena je obdelana literatura in prikaz taksonomskih enot, ki so bile vsebovane v njej. Poleg taksonomskih enot so za obravnavano literaturo predstavljeni grafi primerjav tehnik modeliranja. V zadnjem poglavju so predstavljeni izračuni in primerjava rezultatov natančnosti modelov za napovedovanje. Najprej je predstavljena lastna časovna vrsta, sledi konstrukcija ARIMA modela po Box-Jenkins metodologiji in kasneje še modelov AutoARIMA (funkcija, ki samostojno določi parametre modela), multiple linearne regresije (MLR) in metode podpornih vektorjev (SVM). Na koncu poglavja so prikazane analize primerjav med modeli glede na dolžino in odmik učnega obdobja. Primerjani so tudi modeli za 12 urno napovedovanje.
Keywords: napovedovanje, linearna regresija, naključni gozd, podporni vektorji, ARIMA modeli, taksonomija, mehka logika, informacijski kriteriji.
Published: 07.02.2017; Views: 1836; Downloads: 249
.pdf Full text (4,58 MB)

7.
Optimalna dodelitev frekvenčnih kanalov v brezžičnih omrežjih
Janez Dolšak, 2016, master's thesis

Abstract: Magistrsko delo obravnava problem dodeljevanja frekvenčnih kanalov v brezžičnih omrežjih. Na začetku je predstavljen izvor problema in njegovo teoretično ozadje. Sledi opis osnovnih pojmov iz teorije grafov, ki so potrebni za nadaljnje razumevanje tega dela. Problem je predstavljen z matematičnim modelom iz teorije grafov, ki je soroden problemom barvanja vozlišč grafa. Opisane so metode za reševanje problemov barvanja vozlišč grafa: linearno programiranje in njegova posplošitev semidefinitno programiranje ter nadalje kombinatorični algoritmi, aproksimacijski algoritmi in hevristični algoritmi. Opisan je alternativni pristop k problemu dodeljevanja frekvenčnih kanalov s področja teorije iger. Teorija iger obravnava modele, kjer igralci med seboj sodelujejo za dosego skupnega cilja, ali pa med seboj tekmujejo za dosego lastnega cilja. Zadnja poglavja so namenjena empiričnemu delu raziskovanja problema. Najprej je opisan matematični model dodeljevanja frekvenčnih kanalov iz teorije telekomunikacij. Sledita mu dve družini optimizacijskih primerov na podlagi konkretnih podatkov. Empirični del zaključujejo rezultati optimizacije ter njihova analiza. V vseh optimizacijskih primerih je bila dosežena izboljšava v učinkovitosti brezžičnega omrežja.
Keywords: dodeljevanje frekvenčnih kanalov, teorija grafov, operacijske raziskave, matematično programiranje, teorija iger.
Published: 16.09.2016; Views: 850; Downloads: 103
.pdf Full text (1,09 MB)

Search done in 0.22 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica