| | 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 - 3 / 3
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
GEODETSKO IN OVOJNIŠKO ŠTEVILO PRODUKTOV GRAFOV
Jasna Mrkonjić, 2010, diplomsko delo

Opis: Diplomsko delo obravnava geodetsko in ovojniško število standardnih produktov grafov s poudarkom na kartezičnem in krepkem produktu. V prvem delu so zapisane osnovne definicije s področja teorije grafov, ki se uporabljajo v nadaljevanju. V naslednjem poglavju si pogledamo grafe, za katere je geodetsko število enako ali za ena manjše od števila vozlišč ter enako za ovojniško število. Sledi poglavje v katerem se osredotočimo na geodetsko in ovojniško število v kartezičnem produktu grafov in si pogledamo robne množice. Zadnji del diplomske naloge je namenjen geodetskemu in ovojniškemu številu v krepkem produktu grafov, kjer so podane meje za obe števili in natančne vrednosti za določene tipe grafov.
Ključne besede: konveksnost, ovojnica, geodetska množica grafa, geodetsko število, ovojniško število, poln graf, cikel, produkt grafov, kartezični produkt grafov, krepki produkt grafov, robne množice
Objavljeno: 15.12.2010; Ogledov: 1935; Prenosov: 98
.pdf Celotno besedilo (754,64 KB)

2.
Lower bounds for domination and total domination number of direct products graphs
Gašper Mekiš, 2009

Opis: An exact lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: ▫$gamma(times_{i=1}^t K_{n_i} ge t+1$▫, ▫$t ge 3$▫. Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: ▫$gamma(G times H) ge gamma(G) + gamma(H) - 1$▫. Infinite families of graphs that attain the bound are presented. For these graphs it also holds ▫$gamma_t(G times H) = gamma(G) + gamma(H) - 1$▫. Some additional parallels with the total domination number are made.
Ključne besede: matematika, teorija grafov, dominacijska množica, dominacijsko število, celotna dominacijska množica, celotno dominacijsko število, direktni produkt grafov, poln graf, mathematics, graph theory, dominating set, domination number, total dominating set, total domination number, direct product graphs, complete graphs
Objavljeno: 10.07.2015; Ogledov: 369; Prenosov: 20
URL Povezava na celotno besedilo

3.
b-barvanja regularnih grafov in grafovskih produktov
Mojca Premzl, 2016, magistrsko delo

Opis: Dobro barvanje vozlišč grafa $G$, v katerem v vsakem barvnem razredu obstaja vsaj eno tako vozlišče, ki ima vsaj enega soseda v vsakem drugem barvnem razredu, je b-barvanje grafa $G$. Največje naravno število $k$, za katerega graf premore b-barvanje s $k$ različnimi barvami, imenujemo b-kromatično število grafa in ga označimo s $varphi(G)$. V magistrskem delu bomo predstavili definicijo b-barvanja in podali natančne vrednosti b-kromatičnega števila za poti, cikle, polne grafe, neodvisne množice in polne dvodelne grafe. Dokazali bomo, da je določanje b-kromatičnega števila NP-poln problem, kar ima za posledico dejstvo, da lahko b-kromatično število natančno določimo le nekaterim družinam grafov. Že iz same definicije b-barvanja sledi, da je $chi(G) leq varphi(G) leq Delta(G)+1$. Podali bomo še nekaj zgornjih mej b-kromatičnega števila, ki veljajo za poljubne grafe. Med njimi izpostavimo predvsem $m$-stopnjo grafa $m(G)$; to je največje tako število $m$, za katerega graf $G$ vsebuje vsaj $m$ vozlišč stopnje vsaj $m-1$. Natančno vrednost b-kromatičnega števila lahko med drugim določimo tudi poljubnemu drevesu, in to v polinomskem času. V poglavju o regularnih grafih bomo obravnavali predvsem pogoje, ki jim mora zadoščati $d$-regularen graf, da bo njegovo b-kromatično število enako zgornji meji, to je $d+1$. Eden izmed pogojev je, da ima graf zadostno število vozlišč, in sicer vsaj $2d^3$. Dokazali bomo tudi, da je v $d$-regularnem grafu $varphi(G)=d+1$, če je ožina grafa $g(G) geq 6$ oz. če je $g(G)geq 5$ in graf bodisi ne vsebuje nobenega cikla dolžine $6$ bodisi je $d leq 6$. Nekateri $d$-regularni grafi lahko imajo kljub velikemu $d$ majhno b-kromatično število (npr. dvodelni graf $K_{d,d}$). Dokazali bomo, da velikost b-kromatičnega števila $d$-regularnih grafov, ki ne vsebujejo nobenega $4$-cikla, linearno narašča z velikostjo $d$. Za regularne grafe, ki ne vsebujejo nobenega $4$-cikla in imajo $mathrm{diam}(G) geq 6$, prav tako velja, da je $varphi(G)=d+1$. Enako velja tudi za vse regularne grafe, ki ne vsebujejo nobenega $4$-cikla, njihova vozliščna povezanost pa je $kappa(G) leq frac{d+1}{2}$. Nazadnje bomo dokazali še, da obstajajo le štirje kubični grafi, za katere je $varphi(G) leq d$, eden izmed njih je Petersenov graf. V zadnjem poglavju bomo obravnavali b-barvanja grafovskih produktov, in sicer kartezičnega, krepkega, leksikografskega in direktnega. V primeru kartezičnega in direktnega produkta je b-kromatično število navzdol omejeno z $max left{varphi(G), varphi(H) right}$, v primeru krepkega in leksikografskega produkta pa je spodnja meja enaka $varphi(G) cdot varphi(H)$. Za vsak produkt posebej bomo podali še zgornjo mejo b-kromatičnega števila. Določili bomo še nekatere natančne vrednosti b-kromatičnega števila grafovskih produktov, pri čemer bodo posamezni faktorji enaki potem, ciklom, zvezdam, v nekaterih primerih pa bo eden izmed faktorjev celo poljuben graf.
Ključne besede: b-barvanje, b-kromatično število, NP-poln problem, regularni graf, kartezični produkt, krepki produkt, leksikografski produkt, direktni produkt.
Objavljeno: 14.10.2016; Ogledov: 483; Prenosov: 46
.pdf Celotno besedilo (1,97 MB)

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