Neural networks applied on graph coloring

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.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