Usporedba pohlepnih algoritama za bojanje grafova

završni rad

• Naslov (engleski): Greedy algorithms comparison for graph coloring
• Autor: Antonio Kutnjak
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Josip Žubrinić (član povjerenstva)
• Član povjerenstva: Vlatko Crnković (č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

Ovaj rad opisuje dva algoritma bojanja grafova, SLF i SL, njihovu implementaciju,
složenost i optimalnost. Prvo su opisani općeniti pojmovi koji se susreću u teoriji
grafova i ideja pohlepnog algoritma bojanja. Nakon toga su kratko opisani algoritmi
FF i LF koji su baza za glavne algoritme ovog rada. Slijedi detaljan opis algoritama
SLF i SL, njihova implementacija i složenost. Usporedba algoritama je napravljena
na DIMACS grafovima gdje je analizirana optimalnost i potrebno vrijeme izvod̄enja.
Kratko su opisani korišteni razvojni okvir Qt koji je korišten pri izradi vizualizacije
i programski jezik C++ u kojem su implementirani svi algoritmi spomenuti u ovom
radu.

Sažetak (engleski)

This thesis describes two graph coloring algorithms, SLF and SL, their implementation, complexity and optimality. Firstly, general concepts that are encountered in graph theory and the idea of a greedy coloring algorithm are described. After that, the FF and LF algorithms, which are the basis for the main algorithms of this thesis, are briefly described. This is followed by a detailed description of the SLF and SL algorithms, their implementation and complexity. The comparison of the algorithms is made on DIMACS graphs where optimality and the required execution time are analyzed. The Qt framework used in the development of the visualization and the C++ programming language in which all the algorithms mentioned in this thesis are implemented
are briefly described.

• Ključne riječi: diskretna matematika; teorija grafova; bojanje grafova; pohlepni algoritmi; Qt; C++
• Ključne riječi (engleski): discrete mathematics; graph theory; graph coloring; greedy algorithms; Qt; C++
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:926359
• 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:15:54