Naslov
Algoritmi za usmjerene grafove
(Algorithms for Directed Graphs)

Autori
Hrelja, Mateo

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

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
30.06

Godina
2022

Stranica
39

Mentor
Nakić, Anamari

Ključne riječi
Usmjereni graf ; digraf ;
(Directed graph ; digraph ;)

Sažetak
Usmjereni graf je matematički model i struktura podataka koji se formalno sastoji od skupa vrhova, te skupa lukova između njih. Usmjereni grafovi imaju široku primjenu unutar računarstva i matematike, ali i u raznim drugim znanstvenim disciplinama i industrijama. U ovom radu opisana su osnovna svojstva usmjerenih grafova te algoritmi za ispitivanje navedenih svojstava. Aciklični usmjereni graf nema ciklusa. Računalno ispitivanje svojstva acikličnosti provodi se konstrukcijom topološkog uređaja vrhova. Opisan je Johnsonov algoritam koji pronalazi sve elementarne cikluse u usmjerenom grafu, ukoliko oni postoje. U radu su opisani eulerovski usmjereni grafovi te Hierholzerov algoritam koji pronalazi eulerovsku stazu u usmjerenom grafu ukoliko ona postoji. U rješenjima raznovrsnih problema koji se modeliraju usmjerenim grafovima, često se pojavljuje problem obilaska svih vrhova ili lukova zadanog usmjerenog grafa. U ovom radu opisali smo algoritam za pretraživanje u dubinu. Opisana metoda primjenjena je na problem određivanja jako povezanih komponenti u usmjerenom grafu. Klasifikacija usmjerenih grafova sa zadnim brojem vrhova je još uvijek otvoren problem. U ovom radu definirali smo pojam izomorfnih usmjerenih grafova te opisali izazove klasifikacije neizomorfnih grafova.

Izvorni jezik
Hrvatski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA