Primjena neuralnih mreža na bojanje grafova

undergraduate thesis

• Title (english): Neural networks applied on graph coloring
• Author: Matija Roginić
• Mentor: Mario Osvin Pavčević (mentor)
• Committee member: Mario Osvin Pavčević (predsjednik povjerenstva)
• Committee member: Kristijan Kilassa Kvaternik (član povjerenstva)
• Committee member: Matija Livaić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2023-06-30, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: neuralna mreža; graf; kromatski broj; model; NP-potpun
• Keywords (english): neural network; graph; chromatic number; model; NP-complete
• Language: croatian
• URN:NBN: urn:nbn:hr:168:313189
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-07-13 10:31:21