Algoritmi za usmjerene grafove

undergraduate thesis

• Title (english): Algorithms for Directed Graphs
• Author: Mateo Hrelja
• Mentor: Anamari Nakić (mentor)
• Committee member: Anamari Nakić (predsjednik povjerenstva)
• Committee member: Marina Furkes (član povjerenstva)
• Committee member: Filip Martinović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2022-07-01, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: Usmjereni graf; digraf
• Keywords (english): Directed graph; digraph
• Language: croatian
• URN:NBN: urn:nbn:hr:168:362256
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-14 20:35:42