Naslov
Matematičke i računalne metode za ispitivanje izomorfnosti grafova i klasifikaciju grafova
(Mathematical and Computational Methods for Graph Isomorphism Testing and Graph Classification)

Autori
Vesel, Ivan

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, diplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
15.07

Godina
2020

Stranica
39

Mentor
Nakić, Anamari

Ključne riječi
izomorfizam ; klasifikacija grafova ; grafovi ;
(isomorphism ; graph classification ; graphs ;)

Sažetak
Problem izomorfizma grafova bavi se određivanjem jesu li dva zadana grafa izomorfna. Ovaj težak matematičko-računarski problem usko je vezan uz problem klasifikacije grafova. Problem klasifikacije grafova bavi se prebrajanjem svih neizomorfnih grafova sa zadanim brojem vrhova. Ovaj težak problem predstavlja izazov brojnim istraživačima i samo je djelomično riješen, a pri rješavanju se kombiniraju računalna metoda i metoda matematičkog dokaza. U ovom radu obradeni su osnovni pojmovi i rezultati teorije grafova. Predstavljene su osnovne matematičke tehnike pomoću kojih se može dokazati da su dva zadana grafa izomorfna. Opisane matematičke tehnike primijenjene su na problem klasifikacije grafova s 1, 2, 3, 4 i 5 vrhova. Obrađena je metoda kanonskog labeliranja grafova koja služi za računalno ispitivanje jesu li dva zadana grafa izomorfna. Navedena metoda računalno je implementirana u programskom jeziku Java za grafove s proizvoljnim brojem vrhova. Dobiveno programsko rješenje je prošireno i izrađen je program za računalnu klasifikaciju grafova sa šest vrhova.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA