magistrsko delo
Anže Jeromel (Avtor), Danilo Korže (Mentor), Aleksander Vesel (Komentor)

Povzetek

V magistrski nalogi so opisani grafi Sierpińskega in njihove posplošitve, (d, n)-pakirno barvanje grafov ter računsko iskanje (d, n)-pakirnih kromatičnih števil. Razvili smo algoritem za generiranje grafov Sierpińskega z osnovo 4 ter implementirali štiri metode barvanja grafov. Našli smo točna (d, n)-pakirna kromatična števila za različne kombinacije (d, n) pri grafih stopnje 2, pri grafih višjih stopenj pa njihove zgornje meje. Prav tako smo našli točna (1, 1)-pakirna kromatična števila dveh izbranih posplošenih grafov Sierpińskega do vključno stopnje 5.

Ključne besede

Sierpiński;pakirno barvanje;pakirno kromatično število;magistrske naloge;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.09 - Magistrsko delo
Organizacija: UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Založnik: A. Jeromel
UDK: 004.94:004.83(043.2)
COBISS: 22488342 Povezava se bo odprla v novem oknu
Št. ogledov: 762
Št. prenosov: 64
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: (d, n)-packing coloring of generalized Sierpiński graphs
Sekundarni povzetek: In our work we describe Sierpiński graphs, their generalizations, (d, n)-packing coloring of graphs and computing their (d, n)-packing chromatic numbers. We developed an algorithm that generates Sierpinski graphs with base 4 and implemented four methods for coloring graphs. We found the exact (d, n)-packing chromatic numbers for different combinations of (d, n) for graphs of dimension 2, and found their upper bounds for graphs of higher dimensions. We also found the exact (1, 1)-packing chromatic numbers for two generalized Sierpiński graphs up to and including dimension 5.
Sekundarne ključne besede: Sierpiński;packing coloring;packing chromatic number;
URN: URN:SI:UM:DK:GOCCARB2
Vrsta dela (COBISS): Magistrsko delo/naloga
Komentar na gradivo: Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Strani: VI, 47 str.
ID: 11136214