Algoritmi u teoriji grafova

diplomski rad

• Naslov (engleski): Algorithms in graph theory
• Autor: Nena Buljubašić
• Mentor: Slaven Kožić (mentor)
• Član povjerenstva: Slaven Kožić (predsjednik povjerenstva)
• Član povjerenstva: Robert Manger (član povjerenstva)
• Član povjerenstva: Zlatko Drmač (član povjerenstva)
• Član povjerenstva: Goran Muić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2022-12-01, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Cilj ovog rada je opisati dio jedne grane matematike sa širokim rasponom primjena, teorije grafova. Preciznije, u radu proučavamo neke algoritme na grafovima koji svoju primjenu pronalaze u računarstvu. Prvo poglavlje rada posvećeno je osnovnim pojmovima u teoriji grafova koji su nam potrebni za daljnje razumijevanje tih algoritama. U drugom poglavlju proučavamo četiri različita algoritma za detekciju ciklusa u grafu. Valja spomenuti kako detekcija ciklusa ima istaknutu ulogu u računarstvu zbog svoje primjene na vezane liste. Opisani su Floydov, Brentov, Gosperov i Nivaschov algoritam, od kojih se najčešće koristi Floydov, poznat pod nazivom algoritam ”kornjače i zeca”. Treće poglavlje posvećeno je problemu pronalaska svih maksimalnih klika u grafu pomoću rekurzivnih algoritama. Opisan je Bron-Kerboschov algoritam i algoritam autora Akkoyunlua koji generiraju isto stablo pretraživanja, ali imaju drugačije postavljen pristup problemu.

Sažetak (engleski)

The goal of this thesis is to describe a part of one branch of mathematics with wide range of applications, the graph theory. More specifically, we study several graph algorithms which are used in computer science. In the first chapter of this thesis we present definitions of the basic graph theory notions which are necessary for understanding of the aforementioned algorithms. In the second chapter we consider four cycle detection algorithms. It is worth noting that cycle detection has a significant role in computer science due to its application to linked lists. The algorithms which are described are due to Floyd, Brent, Gosper and Nivasch, and, among them, the former is the most widely used and also known as ”tortoise and hare” algorithm. The third chapter is devoted to the problem of finding all maximal cliques in graph by using recursions. The algorithms described therein are Bron-Kerbosch’s and Akkoyunlu’s algorithm which both generate the same search tree but have different approach to problem.

• Ključne riječi: računarstvo; detekcija ciklusa u grafu; Floydov algoritam; Brentov algoritam; Gosperov algoritam; Nivaschov algoritam; algoritam ”kornjače i zeca”; Bron-Kerboschov algoritam; algoritam Akkoyunlua
• Ključne riječi (engleski): computer science; cycle detection algorithms; Floyd algorithm; Brent algorithm; Gosper algorithm; Nivasch algorithm; ”tortoise and hare” algorithm; Bron-Kerbosch’s algorithm; Akkoyunlu’s algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:542252
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2022-12-14 13:14:03