prikaz prve stranice dokumenta Računalno ispitivanje izomorfnosti grafova
  Preuzmi
PDF 2.88 MB
diplomski rad
Računalno ispitivanje izomorfnosti grafova
Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2025. urn:nbn:hr:168:627205
Zubić, Lora
Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

Institucijski repozitorij: Repozitorij FER-a

Citirajte ovaj rad

Zubić, L. (2025). Računalno ispitivanje izomorfnosti grafova (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:168:627205

Zubić, Lora. "Računalno ispitivanje izomorfnosti grafova." Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2025. https://urn.nsk.hr/urn:nbn:hr:168:627205

Zubić, Lora. "Računalno ispitivanje izomorfnosti grafova." Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2025. https://urn.nsk.hr/urn:nbn:hr:168:627205

Zubić, L. (2025). 'Računalno ispitivanje izomorfnosti grafova', Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, citirano: 12.04.2025., https://urn.nsk.hr/urn:nbn:hr:168:627205

Zubić L. Računalno ispitivanje izomorfnosti grafova [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva; 2025 [pristupljeno 12.04.2025.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:627205

L. Zubić, "Računalno ispitivanje izomorfnosti grafova", Diplomski rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, Zagreb, 2025. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:627205

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:168:627205
Podaci o radu
NaslovRačunalno ispitivanje izomorfnosti grafova
Naslov (engleski)Computational graph isomorphism testing
AutorLora Zubić
MentorAnamari Nakić (mentor)
Član povjerenstvaAnamari Nakić (predsjednik povjerenstva)
Član povjerenstvaDomagoj Kovačević (član povjerenstva)
Član povjerenstvaLenka Mihoković (č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 obrane2025-02-26, Hrvatska
Sažetak
Tema ovog rada je algoritam koji rješava problem izomorfnosti grafova. Razvijena je mobilna aplikacija koja implementira algoritam za provjeru izomorfnosti grafova temeljen na izračunu certifikata grafa. Certifikat grafa je jedinstveni potpis koji omogućuje provjeru izomorfnosti između dva grafa. Postupak za izračun certifikata se dijeli na dva algoritma, jedan prilagođen stablima koji ima linearnu vremensku složenost i drugi za općenite grafove, čija je vremenska složenost neodređena.... Više Aplikacija omogućuje unos dvaju grafova s najviše osam vrhova, pri čemu se grafovi mogu unijeti grafički ili pomoću matrica susjedstva. Program bira odgovarajući algoritam za izračun certifikata, a zatim usporedbom certifikata dvaju grafova javlja korisniku jesu li oni izomorfni. U radu su popisani svi neizomorfni grafovi s pet vrhova i njihovi certifikati. Analizirana je i učinkovitost algoritama te rezultati pokazuju kako na vrijeme izvršavanja utječu veličina i struktura grafova. Sakrij dio sažetka
Sažetak (engleski)
The topic of this thesis is an algorithm that solves the problem of determining graph isomorphism. A mobile application was developed that implements an algorithm for graph isomorphism verification based on graph certificate calculation. Graph certificate is a unique signature that enables the verification of isomorphism between two graphs. The certificate calculation process is divided into two algorithms, one for trees, which has linear time complexity, and another for general... Više graphs, whose time complexity is undefined. The application allows the input of two graphs with up to eight vertices, which can be entered either graphically or using adjacency matrices. The program selects the appropriate algorithm for certificate calculation, compares the certificates of the two graphs and informs the user whether they are isomorphic. The paper also lists all non-isomorphic graphs with five vertices and their certificates. Additionally, the efficiency of the algorithms was analyzed and the results show that execution time is significantly influenced by the size and structure of the graphs. Sakrij dio sažetka
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:168:627205
Studijski programNaziv: 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 resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Javna napomena
Datum i vrijeme pohrane2025-03-12 11:20:58
accessibility

closePristupačnostrefresh

Ako želite spremiti trajne postavke, kliknite Spremi, ako ne - vaše će se postavke poništiti kad zatvorite preglednik.