prikaz prve stranice dokumenta Matematičke i računalne metode za ispitivanje izomorfnosti grafova i klasifikaciju grafova
No public access
master's thesis
Matematičke i računalne metode za ispitivanje izomorfnosti grafova i klasifikaciju grafova
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2020. urn:nbn:hr:168:894202
Vesel, Ivan
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Vesel, I. (2020). Matematičke i računalne metode za ispitivanje izomorfnosti grafova i klasifikaciju grafova (Master's thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:894202

Vesel, Ivan. "Matematičke i računalne metode za ispitivanje izomorfnosti grafova i klasifikaciju grafova." Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2020. https://urn.nsk.hr/urn:nbn:hr:168:894202

Vesel, Ivan. "Matematičke i računalne metode za ispitivanje izomorfnosti grafova i klasifikaciju grafova." Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2020. https://urn.nsk.hr/urn:nbn:hr:168:894202

Vesel, I. (2020). 'Matematičke i računalne metode za ispitivanje izomorfnosti grafova i klasifikaciju grafova', Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 18 November 2024, https://urn.nsk.hr/urn:nbn:hr:168:894202

Vesel I. Matematičke i računalne metode za ispitivanje izomorfnosti grafova i klasifikaciju grafova [Master's thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2020 [cited 2024 November 18] Available at: https://urn.nsk.hr/urn:nbn:hr:168:894202

I. Vesel, "Matematičke i računalne metode za ispitivanje izomorfnosti grafova i klasifikaciju grafova", Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2020. Available at: https://urn.nsk.hr/urn:nbn:hr:168:894202

Metadata
TitleMatematičke i računalne metode za ispitivanje izomorfnosti grafova i klasifikaciju grafova
Title (english)Mathematical and Computational Methods for Graph Isomorphism Testing and Graph Classification
AuthorIvan Vesel
MentorAnamari Nakić (mentor)
Committee memberAnamari Nakić (predsjednik povjerenstva)
Committee memberLana Horvat Dmitrović (član povjerenstva)
Committee memberAna Žgaljić Keko (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2020-07-15, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:894202
Study programmeTitle: Computing
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
Type of resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2023-01-13 09:22:48