Algoritmi za bojanje grafa s predobojanim vrhovima

završni rad

• Naslov (engleski): Algorithms For Graph Coloring with Some Precolored Vertices
• Autor: Filip Perković
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Kristijan Kilassa Kvaternik (član povjerenstva)
• Član povjerenstva: Matija Livaić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2023-06-30, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Algoritmi za bojanje grafa dodjeljuju svakom vrhu jednu boju na način da dva susjedna vrha nisu jednako obojani. Ovaj rad proučava algoritme iscrpne pretrage, pohlepne pretrage i DSatur te njihovu implementaciju i izvođenje, uz dodatan uvjet unaprijednog obojanja nasumično odabranih vrhova. Analizira prilagodbu algoritama na predobojanje i njegov utjecaj na broj boja kojom boje grafove.

Sažetak (engleski)

Algorithms for graph coloring assign such colors to vertices that no two neighboring ones will ever have the same color. This paper deals with the brute-force search, greedy search, and DSatur algorithms, their implementation and execution, with the added condition of coloring a number of randomly sampled vertices in advance. It analyses the adjustment of the algorithms to pre-coloring and its influence on the number of colors used.

• Ključne riječi: Bojanje grafova; algoritmi za bojanje grafova; predobojanje; iscrpna pretraga; pohlepna pretraga; DSatur; stupanj zasićenosti; teorija grafova
• Ključne riječi (engleski): Graph coloring; graph coloring algorithms; precoloring; brute-force search; greedy search; DSatur; degree of saturation; graph theory
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:118390
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-07-13 10:27:45