prikaz prve stranice dokumenta Algoritmi u teoriji grafova
  Download
PDF 216.41 KB
master's thesis
Algoritmi u teoriji grafova
Zagreb: University of Zagreb, Faculty of Science, 2022. urn:nbn:hr:217:542252
Buljubašić, Nena
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Buljubašić, N. (2022). Algoritmi u teoriji grafova (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:542252

Buljubašić, Nena. "Algoritmi u teoriji grafova." Master's thesis, University of Zagreb, Faculty of Science, 2022. https://urn.nsk.hr/urn:nbn:hr:217:542252

Buljubašić, Nena. "Algoritmi u teoriji grafova." Master's thesis, University of Zagreb, Faculty of Science, 2022. https://urn.nsk.hr/urn:nbn:hr:217:542252

Buljubašić, N. (2022). 'Algoritmi u teoriji grafova', Master's thesis, University of Zagreb, Faculty of Science, accessed 29 November 2024, https://urn.nsk.hr/urn:nbn:hr:217:542252

Buljubašić N. Algoritmi u teoriji grafova [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2022 [cited 2024 November 29] Available at: https://urn.nsk.hr/urn:nbn:hr:217:542252

N. Buljubašić, "Algoritmi u teoriji grafova", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2022. Available at: https://urn.nsk.hr/urn:nbn:hr:217:542252

Metadata
TitleAlgoritmi u teoriji grafova
Title (english)Algorithms in graph theory
AuthorNena Buljubašić
MentorSlaven Kožić (mentor)
Committee memberSlaven Kožić (predsjednik povjerenstva)
Committee memberRobert Manger (član povjerenstva)
Committee memberZlatko Drmač (član povjerenstva)
Committee memberGoran Muić (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2022-12-01, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:542252
Study programmeTitle: Computer Science and Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2022-12-14 13:14:03