Search the digital library catalog

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: 880; Downloads: 64
Full text (613,60 KB)
This document has many files! More...

Abstract: Diplomsko delo je sestavljeno iz treh poglavij. V prvem poglavju predstavimo osnovne pojme teorije grafov in podamo definicije ter osnovne lastnosti kartezičnega produkta dveh ali večih grafov. V naslednjem poglavju podamo definiciji hiperkocke in delne kocke, ter spoznamo da so hiperkocke najpreprostejši razred kartezičnega produkta. Nato se posvetimo Djoković-Winklerjevi relaciji Θ, za katero ugotovimo, da je definirana na množici povezav grafa in da je bistvenega pomena za kartezični produkt. Poglavje zaključimo s preprostim algoritmom prepoznavanja hiperkock. V zadnjem poglavju definiramo Hammingove grafe in delne Hammingove grafe. Opazimo tudi, da so hiperkocke edini dvodelni Hammingovi grafi. V nadaljevanju raziščemo kanonično vložitev grafov v kartezični produkt dveh ali večih kvocientnih grafov, katere dobimo iz ekvivalenčnih razredov tranzitivne ovojnice relacije Θ. Nato dokažemo Graham-Winklerjev izrek, ki pove, da je kanonična vložitev izometrija. Ker je izračunavanje tranzitivne ovojnice relacije Θ bistveno pri izračunavanju kanonične vložitve, na koncu podamo algoritem, ki izračuna tranzitivno ovojnico relacije Θ.
Keywords: kartezični produkt, hiperkocke, delne kocke, Hammingovi grafi, relacija Θ, kvocientni graf, kanonična vložitev
Published in DKUM: 27.01.2021; Views: 1308; Downloads: 96
Full text (411,17 KB)

Abstract: V magistrskem delu bomo predstavili igro barvanja vozlišč grafa in igralno kromatično število grafa. Podrobneje si bomo pogledali igro barvanja vozlišč grafa na kartezičnih, direktnih in leksikografskih produktih nekaterih družin grafov. Pri kartezičnih produktih K_2 \square P_n, n \in \NN, K_2 \square C_n, n \geq 3, K_2 \square K_n, n \in \NN, in toroidnih grafih, ki jih dobimo s kartezičnim produktom dveh ciklov, C_{2m} \square C_n, m\geq 3, n \geq 7, bomo predstavili in pokazali natančne vrednosti igralnih kromatičnih števil le-teh. Predstavili bomo tudi igralna kromatična števila naslednjih direktnih produktov: K_{1,n} \times K_{1,m}, m,n \in \NN, K_{m,n} \times K_{a,b}, a,b,n \geq 2, m \in \NN, P_n \times K_{1,m}, m \geq 3, n \geq 2, in P_2 \times W_n, n \geq 3, P_2 \times C_n, n \geq 3. Nazadnje bomo predstavili še igralna kromatična števila naslednjih leksikografskih produktov: P_2 \circ P_n, n \geq 2, P_2 \circ K_{1,n}, n \in \NN, in P_2 \circ W_n, n \geq 8.
Keywords: igralno kromatično število, kartezični produkt, direktni produkt, leksikografski produkt
Published in DKUM: 15.02.2019; Views: 1332; Downloads: 112
Full text (541,63 KB)

Abstract: Diplomsko delo obravnava družine 2m-regularnih grafov in m-regularnih dvodelnih grafov, ki se dekomponirajo v izomorfne kopije drevesa T z m povezavami. Obravnavana je k-terica r1,..., rk z vsoto i=1 do k ri = m. Za drevo T s takim k-barvanjem po povezavah z r i povezavami barve i, da ima vsaka pot v T eno ali dve povezavi iste barve, je predstavljen rezultat, da se vsak kartezični produkt grafov G1,...,Gk, kjerje Gi 2ri-regularen graf za 1 <= i <= k, dekomponira v kopije drevesa T.
Keywords: dekompozicijski izrek, dobro barvanje, drevesa, kartezični produkt
Published in DKUM: 11.11.2016; Views: 1335; Downloads: 67
Full text (514,84 KB)

Abstract: 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.
Keywords: b-barvanje, b-kromatično število, NP-poln problem, regularni graf, kartezični produkt, krepki produkt, leksikografski produkt, direktni produkt.
Published in DKUM: 14.10.2016; Views: 1487; Downloads: 104
Full text (1,97 MB)