Primjena neuralnih mreža na bojanje grafova

završni rad

• Naslov (engleski): Neural networks applied on graph coloring
• Autor: Matija Roginić
• 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

Početni problem bio je razvijanje neuralne mreže za određivanje kromatskog broja
grafa. Odlučili smo se za konvolucijsku neuralnu mrežu zato što prema literaturi daje
najbolje rezultate za ovakav problem. Na raspolaganju smo imali bazu od 1000 grafova
koje smo podijelili u tri skupa (za učenje, provjeru i testiranje). Mrežu smo istrenirali
te zatim provjerili njene performanse na skupu za testiranje. Došli smo do rezultata da
u 80% slučajeva ona točno predviđa kromatski broj. Zatim smo napravili usporedbu
s manjim skupom podataka gdje smo iz početnog skupa uzeli prvo 500, a zatim i
250 grafova te na njima proveli isti postupak i došli do zaključka da u našem slučaju
veličina skupa podataka ne igra značajnu ulogu.

Sažetak (engleski)

Our problem was developing a neural network for determining a chromatic number
of a graph. We have decided on a convolutional neural network, because, according to
the literature, it gives the best result for a problem like ours. On disposal, we have a
database with 100 graphs, and we split them into three sets (for training, validation and
testing). We train our network and check its performance on a training set. The result
was, that in 80% of cases, it correctly predicts a chromatic number. Then we make a
comparison with a smaller dataset where we take 500 and 250 graphs from the original
dataset and repeat the same procedure. The conclusion was that, in our case, the size
of a dataset does not have a significant role.

• Ključne riječi: neuralna mreža; graf; kromatski broj; model; NP-potpun
• Ključne riječi (engleski): neural network; graph; chromatic number; model; NP-complete
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:313189
• 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:31:21