Naslov
Ispitivanje svojstva planarnosti grafa
(Planarity Testing)

Autori
Mišak, Simona

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

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
30.06

Godina
2022

Stranica
34

Mentor
Nakić, Anamari

Ključne riječi
teorija grafova ; planaran graf ; algoritmi za ispitivanje planarnosti grafa
(graph theory ; planar graph ; planarity testing algorithms)

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.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA