Algoritmi za usmjerene grafove

završni rad

• Naslov (engleski): Algorithms for Directed Graphs
• Autor: Mateo Hrelja
• Mentor: Anamari Nakić (mentor)
• Član povjerenstva: Anamari Nakić (predsjednik povjerenstva)
• Član povjerenstva: Marina Furkes (član povjerenstva)
• Član povjerenstva: Filip 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 obrane: 2022-07-01, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

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.

Sažetak (engleski)

A directed graph is a mathematical model and data structure which formally consists of a set of vertices and a set of arcs between them. Directed graphs have a wide range of applications in computer science and mathematics, as well as in various other disciplines and industries. In this thesis, some fundamental properties for directed graphs were described, as well as algorithms used for testing directed graphs for these properties.
Acyclic directed graphs contain no cycles. Computationally, acyclicity is determined by constructing a topological vertex ordering. Johnson's algorithm was described, which finds all elementary cycles in a directed graph, if they exist. Eulerian directed graphs were described, as well as Hierholzer's algorithm which finds an Eulerian circuit in a directed graph, if it exists. The problem of traversing all the vertices or arcs in a given directed graph is a common occurrence in various attempts at finding a solution to problems modeled by directed graphs. In the thesis, the depth first search algorithm was described. This method was applied to the problem of finding strongly connected components in a directed graph. The classifications of directed graphs with a certain number of vertices is still an open problem. In this thesis, the terms directed graph isomorphism and isomorphic directed graphs were described, as well as the challenges which come with trying to classify them.

• Ključne riječi: Usmjereni graf; digraf
• Ključne riječi (engleski): Directed graph; digraph
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:362256
• Studijski program: Naziv: 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 resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-14 20:35:42