| | 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 - 10 / 13
First pagePrevious page12Next pageLast page
1.
Pakirno barvanje grafa : na študijskem programu 2. stopnje Matematika
Tomaž Ličina, 2021, master's thesis

Abstract: 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.
Keywords: barvanje grafov, pakirno barvanje grafov, drevesa, grafi Mycielskega, kartezični produkt grafov, klično število, neodvisnostno število, vozliščno pokritje
Published in DKUM: 12.01.2022; Views: 197; Downloads: 16
.pdf Full text (613,60 KB)
This document has many files! More...

2.
Š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 in DKUM: 29.10.2020; Views: 326; Downloads: 35
.pdf Full text (2,21 MB)

3.
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 in DKUM: 23.01.2020; Views: 704; Downloads: 70
.pdf Full text (3,34 MB)

4.
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 in DKUM: 05.11.2019; Views: 716; Downloads: 77
.pdf Full text (318,60 KB)

5.
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 in DKUM: 23.10.2019; Views: 782; Downloads: 11
.pdf Full text (764,69 KB)
This document has many files! More...

6.
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 in DKUM: 13.07.2018; Views: 619; Downloads: 93
.pdf Full text (1,30 MB)

7.
Ljubljana-Leoben graph theory seminar : Maribor, 13.-15. September, 2017. Book of abstracts
2017, other monographs and other completed works

Abstract: The booklet contains the abstracts of the talks given at the 30th Ljubljana-Leoben Graph Theory Seminar that was held at the Faculty of Natural Sciences and Mathematics in Maribor between 13-15 September, 2017. The seminar attracted more than 30 participants from eight countries, all of which are researchers in different areas of graph theory. The topics of the talks encompass a wide range of contemporary graph theory research, notably, various types of graph colorings (b-coloring, packing coloring, edge colorings), graph domination (rainbow domination, Grundy domination, graph security), distinguishing problems, algebraic graph theory, graph algorithms, chemical graph theory, coverings, matchings and also some classical extremal problems. Beside the abstracts of the four invited speakers (Csilla Bujtás, Premysl Holub, Jakub Przybyło, Zsolt Tuza), the booklet contains also the abstracts of 18 contributed talks given at the event.
Keywords: mathematics, discrete mathematics, graph theory, Ljubljana-Leoben seminar, Maribor, Slovenia
Published in DKUM: 08.12.2017; Views: 840; Downloads: 121
.pdf Full text (457,62 KB)
This document has many files! More...

8.
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 in DKUM: 07.02.2017; Views: 2222; Downloads: 288
.pdf Full text (4,58 MB)

9.
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 in DKUM: 16.09.2016; Views: 1039; Downloads: 117
.pdf Full text (1,09 MB)

10.
Bucolic complexes
Boštjan Brešar, Jérémie Chalopin, Victor Chepoi, Tanja Dravec, Damian Osajda, 2013, original scientific article

Abstract: Vpeljemo in obravnavamo bukolične kompleksne, skupno posplošitev sistoličnih in CAT(0) kubnih kompleksov. Definirani so kot enostavno povezani kompleksi prizem, ki zadoščajo določenim lokalnim kombinatornim pogojem. Raziskujemo različne pristope k bukoličnim kompleksom: gledamo jih iz vidika teorije grafov in topološkega vidika kot tudi iz perspektive geometrijske teorije grup. Tako med drugim okarakteriziramo bukolične komplekse preko nekih lastnosti njihovih 2-skeletov in 1-skeletov (ki jim pravimo bukolični grafi), s čimer posplošimo več prej znanih rezultatov. Prav tako dokažemo, da so lokalno končni bukolični kompleksi kontraktibilni in da zadoščajo nekim lastnostim tipa nepozitivnih ukrivljenosti.
Keywords: CAT(0) kubni in sistolični kompleksi, medianski in mostovni grafi, zastražena amalgamacija, kartezični produkt, kompleksi prizem, retrakti, fiksne točke, asferičnost, CAT(0) cubical and systolic complexes, median and bridged graphs, gated amalgamation, Cartesian product, prism complexes, retracts, fixed points, asphericity
Published in DKUM: 10.07.2015; Views: 839; Downloads: 19
URL Link to full text

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