| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:Pakirno barvanje grafa : na študijskem programu 2. stopnje Matematika
Avtorji:Ličina, Tomaž (Avtor)
Dravec, Tanja (Mentor) Več o mentorju... Novo okno
Datoteke:.pdf MAG_Licina_Tomaz_2021.pdf (613,60 KB)
MD5: 4AC055439DE1223C1E09402EDCF287F0
 
.zip MAG_Licina_Tomaz_2021.zip (1,76 MB)
MD5: 1D50D94A65E68A27402910AE0C01BCFD
 
Jezik:Slovenski jezik
Vrsta gradiva:Magistrsko delo/naloga (mb22)
Tipologija:2.09 - Magistrsko delo
Organizacija:FNM - Fakulteta za naravoslovje in matematiko
Opis: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.
Ključne besede:barvanje grafov, pakirno barvanje grafov, drevesa, grafi Mycielskega, kartezični produkt grafov, klično število, neodvisnostno število, vozliščno pokritje
Leto izida:2021
Kraj izvedbe:Maribor
Založnik:[T. Ličina]
Št. strani:45 str.
Izvor:Maribor
UDK:519.174(043.2)
COBISS_ID:90325763 Novo okno
Število ogledov:71
Število prenosov:8
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:FNM
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Licence

Licenca:CC BY-NC-ND 4.0, Creative Commons Priznanje avtorstva-Nekomercialno-Brez predelav 4.0 Mednarodna
Povezava:http://creativecommons.org/licenses/by-nc-nd/4.0/deed.sl
Opis:Najbolj omejujoča licenca Creative Commons. Uporabniki lahko prenesejo in delijo delo v nekomercialne namene in ga ne smejo uporabiti za nobene druge namene.
Začetek licenciranja:09.11.2021

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Packing coloring of graphs
Opis:Packing coloring of a graph is a proper vertex coloring, where two different vertices with the same color i, are at a distance greater than i. The packing chromatic number of a graph is the smallest number of colors needed to color a graph with such a coloring. In this masters thesis we study the packing chromatic number of certain families of graphs and the relationship between the packing chromatic number and other graph invariants. We investigate the relationship between the clique, the chromatic and the packing chromatic number. In the first part we study the packing chromatic number of basic families of graphs, such as trees, Cartesian products of graphs and on Mycielskian graphs. In the next part we look at graphs with small packing chromatic numbers and show that the problem of checking if a graph is $4$-packing chromatic colorable is NP-hard. In the third part we investigate the relationship between the packing chromatic number and three other graph invariants, the independance number, the smallest vertex cover of a graph and the maximal vertex degree of a graph. In the last part we present the relationship between the clique number, the chromatic number and the packing chromatic number. We present triples (a,b,c) for which there is a graph G with the clique number a, the chromatic number b and the packing chromatic number c.
Ključne besede:graph coloring, packing coloring of graphs, trees, Mycielskian construction, Cartesian products of graphs, clique number, independance number, vertex cover


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici