Algorithms in graph theory

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.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