prikaz prve stranice dokumenta Ispitivanje svojstva planarnosti grafa
Rad nije dostupan
završni rad
Ispitivanje svojstva planarnosti grafa
Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2022. urn:nbn:hr:168:114001
Mišak, Simona
Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

Institucijski repozitorij: Repozitorij FER-a

Citirajte ovaj rad

Mišak, S. (2022). Ispitivanje svojstva planarnosti grafa (Završni rad). Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:168:114001

Mišak, Simona. "Ispitivanje svojstva planarnosti grafa." Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2022. https://urn.nsk.hr/urn:nbn:hr:168:114001

Mišak, Simona. "Ispitivanje svojstva planarnosti grafa." Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2022. https://urn.nsk.hr/urn:nbn:hr:168:114001

Mišak, S. (2022). 'Ispitivanje svojstva planarnosti grafa', Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, citirano: 18.11.2024., https://urn.nsk.hr/urn:nbn:hr:168:114001

Mišak S. Ispitivanje svojstva planarnosti grafa [Završni rad]. Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva; 2022 [pristupljeno 18.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:114001

S. Mišak, "Ispitivanje svojstva planarnosti grafa", Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, Zagreb, 2022. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:114001

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:168:114001
Podaci o radu
NaslovIspitivanje svojstva planarnosti grafa
Naslov (engleski)Planarity Testing
AutorSimona Mišak
MentorAnamari Nakić (mentor)
Član povjerenstvaAnamari Nakić (predsjednik povjerenstva)
Član povjerenstvaMarina Furkes (član povjerenstva)
Član povjerenstvaFilip Martinović (č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 obrane2022-07-01, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		TEHNIČKE ZNANOSTI
Računarstvo
Sažetak
Graf je planaran ako se može smjestiti u ravninu bez presijecanja bridova, tj. tako da se dva brida geometrijski ne sijeku niti u jednoj točki, osim eventualno u vrhu s kojim su oba incidentni. Ispitivanje planarnosti grafa je ponekad težak računarski problem. Postoje brojni algoritmi te metode koje se bave tim problemom. Metode se razlikuju ovisno o osnovnoj jedinici dodavanja u ravninski prikaz. Tako postoje metoda dodavanja puta, vrha te brida. Boyer-Myrvold algoritam, jedan od najpoznatijih i najčešće korištenih algoritama, implementira metodu dodavanja brida. Taj je algoritam uz pomoć Boost biblioteke implementiran u aplikaciji u sklopu ovog rada. Ta aplikacija ispituje planarnost zadanog grafa te klasificira sve planarne grafove za zadani broj vrhova n, gdje je n=1, 2, 3, 4, 5.
Sažetak (engleski)
The graph is planar if it can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Testing the properties of planar graphs is often a difficult computing problem. There are many algorithms and methods that deal with this problem. These methods differ based on the unit of addition in the planar embedding and so there exist path addition, vertex addition and edge addition method. The Boyer-Myrvold algorithm, one of the most popular and most frequently used algorithms, uses the latter one. It is implemented in Boost library, that is used in the application developed for this paper. This application tests whether the given graph is planar. It also classifies all planar graphs for n number of vertices, where n=1, 2, 3, 4, 5.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:168:114001
Studijski programNaziv: Računarstvo
Vrsta studija: sveučilišni
Stupanj studija: preddiplomski
Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaZatvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Javna napomena
Datum i vrijeme pohrane2023-01-14 21:14:05