Analiza mrežnih algoritama za traženje minimalnog razapinjajućeg stabla

master's thesis

• Title (english): Analysis of Network Algorithms for Finding Minimum Spanning Tree
• Author: Valentino Češnjaj
• Mentor: Tomislav Burić (mentor)
• Committee member: Tomislav Burić (predsjednik povjerenstva)
• Committee member: Neven Elezović (član povjerenstva)
• Committee member: Ognjen Dobrijević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2018-07-10, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Electrical Engineering

Abstract

U ovom radu cilj je bio analizirati algoritme za traženje minimalnog razapinjućeg stabla kao i pokazati princip njihovog rada. Pokušali smo vidjeti koje su sličnosti, a koje razlike u njihovom radu i kako gustoća grafa kojeg rješavaju utječe na vrijeme izvođenja algoritma.
U uvodnom dijelu smo objasnili temeljne pojmove iz teorije grafova i pojedine teoreme kako bi što bolje razumjeli pojam stabla minimalne težine u grafu. Nadalje smo vidjeli koju primjenu ta teorija grafova ima u realnom svijetu i na koji način modelirati probleme iz stvarnog života pomoću nje. Sljedeće poglavlje se više baziralo na stablima u grafu(minimalne težine) gdje smo se posebno koncentrirali na teorem o ciklusu i teorem o rezu koji se koriste u izvođenju algoritama za traženje minimalnog razapinjućeg stabla. Spomenuli smo i definirali protokol STP koji se takoreći temelji na logici minimalnog razapinjućeg stabla.
Na posljetku smo opisali same algoritme i analizirali njihov rad na istom grafu kako bi uvidjeli razlike i sličnosti u načinima njihovog izvođenja.

Abstract (english)

The purpose of this work was to analyze algorithms for searching minimum spanning tree and to show how they work. We tried to see which are the similarities and which are the differences in their steps of execution as the fact how they work in different time complexity for divers given graph density.
In introductory part, we explained the core terms of graph theory and some important theorems which can help us to better understand the meaning of minimum spanning tree. Further, we explain the application of graph theory field in real life situations and how can we model our problems. The next chapter was mostly based on trees in the graph(minimum weight) where we specially focused on the theorem about the cut and the theorem about a cycle. We also explained the protocol called STP which is mostly based on work of finding the minimum spanning tree in the network.
At the end, we describe the algorithms which are used to find the minimum spanning trees and saw how they work comparing it with each other.

• Keywords: graf; teorija grafova; minimalno razapinjuće stablo; Prim algoritam; Kruskal algoritam; Boruvka algoritam
• Keywords (english): graph; graph theory; minimum spanning tree; Prim's algorithm; Kruskal algorithm; Boruvka's algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:168:436154
• Study programme: Title: Information and Communication Technology; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka informacijske i komunikacijske tehnologije (magistar/magistra inženjer/inženjerka informacijske i komunikacijske tehnologije)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-13 19:44:07