| | 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 - 7 / 7
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
NEENAKOSTI VIZINGOVEGA TIPA ZA RAZLIČNE DOMINACIJSKE INVARIANTE
Vika 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: 11.09.2012; Ogledov: 1217; Prenosov: 162
.pdf Celotno besedilo (715,88 KB)

2.
NAJMANJŠA DOMINANTNA MNOŽICA KRALJIC
Tomaž 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: 23.11.2012; Ogledov: 1138; Prenosov: 108
.pdf Celotno besedilo (982,31 KB)

3.
Direktni produkti polnih grafov
Gaš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: 04.04.2013; Ogledov: 1652; Prenosov: 110
.pdf Celotno besedilo (466,86 KB)

4.
Hevristike za iskanje najmanjše dominantne množice
Blaž 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: 07.10.2014; Ogledov: 900; Prenosov: 88
.pdf Celotno besedilo (563,23 KB)

5.
On domination numbers of graph bundles
Blaž 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: 10.07.2015; Ogledov: 495; Prenosov: 53
URL Povezava na celotno besedilo

6.
Chromatic numbers of strong product of odd cycles
Janez Ž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: 10.07.2015; Ogledov: 450; Prenosov: 41
URL Povezava na celotno besedilo

7.
Alianse v grafih
Tina 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: 19.07.2016; Ogledov: 389; Prenosov: 51
.pdf Celotno besedilo (1,14 MB)

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