Neki algoritmi za određivanje ciklusa u grafu

undergraduate thesis

• Title (english): Some Algorithms for Determining Cycles in a Graph
• Author: Hrvoje Biloš
• Mentor: Mario Krnić (mentor)
• Committee member: Mario Krnić (predsjednik povjerenstva)
• Committee member: Tomislav Burić (član povjerenstva)
• Committee member: Lenka Mihoković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2024-06-27, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Ovaj završni rad bavi se problematikom određivanja ciklusa u jednostavnom grafu. U prvom
dijelu rada objašnjeni su osnovni pojmovi vezani uz grafove, uključujući definiciju
jednostavnog grafa, matrice susjedstva i ciklusa. U središnjem dijelu rada predstavljena su
dva algoritma za pronalaženje svih ciklusa u grafu: algoritam pretraživanja u dubinu (Depth
First Search - DFS) i algoritam kombinacije ciklusa. Za svaki od ovih algoritama detaljno je
opisan način rada te su prikazani pseudokod i programske implementacije. Prikazani su i
konkretni primjeri koji ilustriraju primjenu ovih algoritama na različitim grafovima, čime je
demonstrirana njihova učinkovitost i primjenjivost u praksi.

Abstract (english)

This thesis addresses the problem of detecting cycles in a simple graph. The first part of the
thesis explains basic concepts related to graphs, including the definition of a simple graph,
adjacency matrix, and cycles. The central part of the thesis presents two algorithms for
finding all cycles in a graph: the Depth First Search (DFS) algorithm and the cycle
combination algorithm. Each algorithm is thoroughly explained, including their operational
mechanisms, pseudocode, and software implementations. Concrete examples are provided
to illustrate the application of these algorithms to different graphs, demonstrating their
efficiency and practical applicability.

• Keywords: DFS; ciklus u grafu; teorija grafova; algoritam
• Keywords (english): DFS; cycle in a graph; graph theory; algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:168:277576
• 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: 2024-10-12 20:06:44