Matematičke i računalne metode za ispitivanje izomorfnosti grafova i klasifikaciju grafova

diplomski rad

• Naslov (engleski): Mathematical and Computational Methods for Graph Isomorphism Testing and Graph Classification
• Autor: Ivan Vesel
• Mentor: Anamari Nakić (mentor)
• Član povjerenstva: Anamari Nakić (predsjednik povjerenstva)
• Član povjerenstva: Lana Horvat Dmitrović (član povjerenstva)
• Član povjerenstva: Ana Žgaljić Keko (č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: 2020-07-15, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

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.

Sažetak (engleski)

The problem of graph isomorphism is concerned with determining whether two given graphs are isomorphic. This difficult mathematical-computational problem is closely related to the problem of graph classification. The problem of graph classification deals with counting all non-isomorphic graphs with a given number of vertices. This difficult problem is a challenge for many researchers and has only been partially solved, and the solution combines computer methods and methods of mathematical proof. In this thesis, the basic concepts and results of graph theory are discussed. Basic mathematical techniques are presented by which it can be proved that two given graphs are isomorphic. The described mathematical techniques are applied to the problem of classification of graphs with 1, 2, 3, 4 and 5 vertices. The method of canonical labeling of graphs is described, and used for computational examination of whether two given graphs are isomorphic. This method is implemented in the Java programming language for graphs with arbitrary number of vertices. The obtained software solution was expanded and a program for computational classification of graphs with six vertices
was developed.

• Ključne riječi: izomorfizam; klasifikacija grafova; grafovi
• Ključne riječi (engleski): isomorphism; graph classification; graphs
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:894202
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 09:22:48