1. Super dominantno število grafaTajda Remic, 2024, magistrsko delo Opis: Množica $D$ vozlišč grafa $G$ je super dominantna množica, če za vsako vozlišče $v \in V(G)-D$ obstaja vozlišče $u \in D$, ki je sosednje z $v$ in velja, da je $v$ edini sosed od $u$ v $V(G)-D$. Velikost najmanjše super dominantne množice grafa $G$ je super dominantno število grafa $G$, ki ga označujemo z $\gamma_{sp}(G)$.
V magistrskem delu raziskujemo lastnosti super dominantnega števila. V ta namen najprej predstavimo osnovne pojme na grafih, predstavimo nekaj pomembnih družin grafov in veliko različnih grafovskih invariant, ki so povezane s super dominantnim številom.
V drugem delu pričnemo z raziskovanjem super dominantnih množic. Najprej izračunamo super dominantno število za nekaj pomembnih družin grafov in dokažemo, da za vsak povezan graf na vsaj dveh vozliščih velja: $\frac{n}{2} \leq \gamma_{sp}(G)\leq |V(G)|-1$. Nato super dominantno število raziskujemo na drevesih. Dokažemo boljšo zgornjo mejo super dominantnega števila dreves in se ukvarjamo z grafi, ki to mejo dosežejo. Na koncu super dominantno število dreves navzgor omejimo še z $2$-dominantnim številom grafa. V zadnjem delu magistrske naloge predstavimo zvezo super dominantnega števila z mnogimi grafovskimi invariantami, kot so velikost največjega prirejanja, neodvisnostno število in mnoge druge.
Ključne besede: super dominantno število, super dominantna množica, drevo, neodvisnostno število, dominantno število, prirejanje
Objavljeno v DKUM: 11.06.2024; Ogledov: 153; Prenosov: 33
 Celotno besedilo (6,92 MB) |
2. Grafi z enolično γ-množico : na magistrskem študijskem programu Izobraževalna matematika - enopredmetnaDarina 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: 442; Prenosov: 42
Celotno besedilo (2,90 MB) |
3. Grafi, ki dosežejo enakost v vizingovi domnevi : magistrsko deloAnamarija Lakner, 2022, magistrsko delo Opis: Vizing je leta 1968 postavil domnevo, da je dominantno število kartezičnega produkta dveh grafov večje ali enako produktu njunih dominantnih števil. V magistrskem delu obravnavamo družine grafov, ki v tej domnevi dosežejo enakost.
V prvem delu magistrske naloge smo navedli pojme in trditve, ki jih potrebujemo za razumevanje glavnega problema naloge.
Drugo poglavje se nanaša na različne meje dominantnega števila kartezičnega produkta dveh grafov in družine grafov, ki zadoščajo Vizingovi domnevi.
V tretjem poglavju obravnavamo družine grafov, ki pod določenimi pogoji dosežejo enakost v Vizingovi domnevi, ter znane rezultate podamo v tabeli.
Ključne besede: dominantno število, dominantna množica, Vizingova domneva, enakost v Vizingovi domnevi
Objavljeno v DKUM: 28.10.2022; Ogledov: 573; Prenosov: 49
Celotno besedilo (568,89 KB) |
4. Alianse v grafihTina Zupanc, 2016, magistrsko delo Opis: V magistrskem delu so predstavljene alianse v grafih, s temeljitejšo študijo pa se osredotočimo na obrambne in napadalne alianse. Definicije proučevanih pojmov so podprte s primeri in razlago, predvsem pa se v posameznih podpoglavjih posvečamo lastnostim alians. V nekaterih družinah grafov podamo natančne vrednosti obrambnih in napadalnih števil, ki sta definirani kot moč najmanjše alianse v grafu, v splošnih grafih pa moči alians navzdol in navzgor omejimo.
Poglavji o obrambnih in napadalnih aliansah razširimo z definicijami globalnih alians, k-alians in globalnih k-alians ter podamo vrednosti, ki določajo natančno moč omenjenih množic ali predstavljajo spodnjo ter zgornjo mejo.
V zadnjem delu magistrske naloge so omenjene močne alianse, za katere velja, da so hkrati obrambne in napadalne alianse. Zadnji razmislek je posvečen varnim množicam, ki so boljša aproksimacija realnih situacij v primerjavi z obrambnimi aliansami.
Ključne besede: aliansa, obrambna aliansa, napadalna aliansa, globalna obrambna aliansa, globalna napadalna aliansa, k-aliansa, dominantna množica
Objavljeno v DKUM: 19.07.2016; Ogledov: 1165; Prenosov: 153
Celotno besedilo (1,14 MB) |
5. Chromatic numbers of strong product of odd cyclesJanez Žerovnik, 2002, objavljeni znanstveni prispevek na konferenci Opis: The problem of determining the chromatic numbers of the strong product of cycles is considered. A construction is given proving ▫$chi(G) = 2^p + 1$▫ for a product of ▫$p$▫ odd cycles of lengths at least ▫$2^p + 1$▫. Several consequences are discussed. In particular it is proved that the strong product of ▫$p$▫ factors has chromatic number at most ▫$2^p + 1$▫ provided that each factor admits the homomorphism to sufficiently long odd cycle ▫$C_{m_i}, ; m_i ge 2^p + 1$▫.
Ključne besede: matematika, teorija grafov, krepki produkt grafov, kromatično število, lih cikel, minimalna neodvisna dominantna množica, mathematics, graph theory, strong product, chromatic number, odd cycle, minimal independent dominating set
Objavljeno v DKUM: 10.07.2015; Ogledov: 1653; Prenosov: 84
 Povezava na celotno besedilo |
6. On domination numbers of graph bundlesBlaž Zmazek, Janez Žerovnik, 2005 Opis: Let ▫$gamma(G)$▫ be the domination number of a graph ▫$G$▫. It is shown that for any ▫$k ge 0$▫ there exists a Cartesian graph bundle ▫$B Box_varphi F$▫ such that ▫$gamma(B Box_varphi F) = gamma(B)gamma(F) - 2k$▫. The domination numbers of Cartesian bundles of two cycles are determined exactly when the fibre graph is a triangle or a square. A statement similar to Vizing's conjecture on strong graph bundles is shown not to be true by proving the inequality ▫$gamma(B boxtimes_varphi F) le gamma(B)gamma(F)$▫ for strong graph bundles. Examples of graphs ▫$B$▫ and ▫$F$▫ with ▫$gamma(B boxtimes_varphi F) < gamma(B)gamma(F)$▫ are given.
Ključne besede: matematika, teorija grafov, kartezični produkt grafov, dominantno število, dominantna množica, grafovski sveženj, mathematics, graph theory, graph bundle, dominating set, domination number, Cartesian product
Objavljeno v DKUM: 10.07.2015; Ogledov: 1616; Prenosov: 98
Povezava na celotno besedilo |
7. Hevristike za iskanje najmanjše dominantne množiceBlaž Kajser, 2014, magistrsko delo Opis: V problemu iskanja najmanjše dominantne množice imamo podan graf G, za katerega moramo poiskati najmanjšo podmnožico vozlišč, za katero velja, da predstavlja dominantno množico. V splošnem je problem NP-poln, zato za iskanje najmanjše dominantne množice uporabimo hevristike.
Magistrsko delo je sestavljeno iz štirih poglavij. V prvem poglavju so povzete osnovne definicije iz teorije grafov, ki jih v nadaljevanju potrebujemo za razumevanje magistrskega dela. Prav tako so v prvem poglavju definirane posebne družine grafov. V drugem poglavju sledi definicija dominantne množice in dokaz, da je odločitveni problem dominantne množice NP-poln problem. Predstavljene so tudi že znane zgornje in spodnje meje dominacijskega števila posameznih grafov. V naslednjem poglavju so predstavljene posamezne hevristike in njihova implementacija na problemu iskanja najmanjše dominantne množice v grafu. V zadnjem, četrtem poglavju pa so predstavljeni rezultati testiranja prej opisanih hevristik za problem najmanjše dominantne množice na kartezičnih, direktnih in krepkih produktih poti in ciklov.
Ključne besede: teorija grafov, dominantna množica, dominacijsko število, NP-poln problem, hevristike
Objavljeno v DKUM: 07.10.2014; Ogledov: 2225; Prenosov: 199
Celotno besedilo (563,23 KB) |
8. Direktni produkti polnih grafovGašper Mekiš, 2013, doktorska disertacija Opis: Prvi del disertacije je posvečen neodvisnim dominantnim množicam direktnega produkta štirih polnih grafov. Eksplicitno so opisane T1-množice, tj. množice, kjer se poljubni par vozlišč ujema na natanko enem mestu. Glavni rezultat tega dela reče, da direktni produkt štirih polnih grafov premore idomatsko particijo na T1-množice natanko tedaj, ko sta reda vsaj dveh faktorjev deljiva s 3.
V nadaljevanju postane osrednja tema dominantno in polno dominantno število direktnega produkta končno mnogo polnih grafov. Za slednje grafe je podana spodnja meja, ki je točna, če so faktorji dovolj veliki v primerjavi s številom faktorjev. Najsplošnejši rezultat tega dela je spodnja meja za dominantno (in polno dominantno) število direktnega produkta poljubnih dveh grafov, ki je izražena z dominatnima številoma faktorjev. Opisane so neskončne družine grafov, ki zavzamejo enakost.
Zadnji del je posvečen mavrični povezanosti direktnega produkta. Podana je zgornja meja za mavrično povezanost direktnega produkta dveh grafov v odvisnosti od mavrične povezanosti faktorjev in še dveh podobnih invariant dobljenih s pomočjo lihih ciklov. Izkaže se, da so ravno polni grafi izjema omenjene meje. Za produkt dveh polnih grafov je dana točna vrednost (krepke) mavrične povezanosti. Kot dodatek so na koncu podani tudi nekateri rezultati glede ostalih treh standardnih grafovskih produktov.
Ključne besede: direktni produkt grafov, dominantna množica, dominantno število, idomatska particija, krepka mavrična povezanost, neodvisna množica, mavrična povezanost, polna dominantna množica, polni graf, polno dominantno število
Objavljeno v DKUM: 04.04.2013; Ogledov: 3284; Prenosov: 183
Celotno besedilo (466,86 KB) |
9. NAJMANJŠA DOMINANTNA MNOŽICA KRALJICTomaž Bahč, 2012, diplomsko delo Opis: Delo je razdeljeno na tri poglavja. V prvem poglavju so predstavljeni osnovni pojmi iz teorije grafov in algoritmičnih pristopov, ki so potrebni za razumevanje drugega in tretjega poglavja. V drugem poglavju je predstavljen Problem najmanjše dominantne množice kraljic. V tem poglavju sta predstavljena dva pristopa k reševanju tega problema in sicer sestopanje ter dinamično programiranje. V tretjem poglavju je predstavljena implementacija obeh pristopov iz drugega poglavja v programskem jeziku C++. Implementacija je v celoti objavljena kot priloga na zgoščenki.
Ključne besede: dominantna množica, najmanjša dominantna množica kraljic, sestopanje, dinamično programiranje
Objavljeno v DKUM: 23.11.2012; Ogledov: 2099; Prenosov: 179
Celotno besedilo (982,31 KB) |
10. NEENAKOSTI VIZINGOVEGA TIPA ZA RAZLIČNE DOMINACIJSKE INVARIANTEVika Koban, 2012, diplomsko delo Opis: Dominacija na grafih je intenzivno raziskovana veja v teoriji grafov. Leta 1963 je Vizing postavil domnevo, da je dominantno število kartezičnega produkta dveh grafov kvečjemu večje od produkta njunih dominantih števil. Mnogo delnih rezultatov je bilo dokazanih, vendar pa je le-ta še vedno eden izmed največjih odprtih problemov v študiju dominacije na grafih. V tem diplomskem delu so v ospredju obravnavani najbolj znani izreki Vizingovega tipa za različne dominacijske invariante.
Na začetku predstavimo nekaj dejstev o dominaciji na kartezičnem produktu. Opišemo znan Clark-Suenov rezultat Vizingovega tipa in t.i. razstavljive grafe, za katere Vizingova domneva drži.
Drugi del se nanaša na pet dominacijskih invariant; totalno, celoštevilsko, zgornjo, deljeno dominantno število in dominacijo po parih. Predstavljeni so izreki Vizingovega tipa za posamezne dominacijske parametre, kot na primer izrek za deljeno-dominantno število, Ho-jev izrek o totalnem dominantnem številu in izrek Vizingovega tipa za zgornje dominantno število.
Ključne besede: dominantna množica, dominantno število, Vizingova domneva, dominacijske invariante
Objavljeno v DKUM: 11.09.2012; Ogledov: 2126; Prenosov: 254
Celotno besedilo (715,88 KB) |
