Algoritmi za traženje minimalnog razapinjućeg stabla u grafu

undergraduate thesis

• Title (english): Algorithms for Search of Minimal Spanning Tree
• Author: Šimun Smolčec
• Mentor: Siniša Srbljić (mentor)
• Committee member: Siniša Srbljić (predsjednik povjerenstva)
• Committee member: Adrian Satja Kurdija (član povjerenstva)
• Committee member: Iva Jurković (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2020-08-27, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U ovom radu objašnjen je problem pronalaska minimalnog razapinjućeg stabla. Također su i objašnjena tri algoritma: Boruvkin, Primov i Kruskalov. Sva tri algoritma izvedena su u programskom jeziku Pyhton. Napravljen je generator primjera koji pazi da generirani grafovi budu povezani kako bi ih mogli obraditi pomoću algoritama razapinjućeg stabla. Sva tri prethodno navedena algoritma testirana su na grafovima različite veličine i gustoće. Na dobivenim rezultatima analizirane su njihove prednosti i mane. Algoritmi su također testirani i na jednom problemu iz stvarnog života, a to je kako povezati muzeje u užem centru Zagreba optičkom mrežom najmanje cijene.

Abstract (english)

In this paper, the problem of finding minimum spanning tree is explained. Three algorithms that were explained were Boruvka’s, Prim’s and Kruskal’s. All three algorithms were programmed in Python. An example generator has been created so that the generated graphs were all connected graphs so that the algorithms could process them to find minimum spanning tree. All three previously mentioned algorithms were tested on graphs of different size and density. The results were analysed to find the advantages and disadvantages of each algorithm. In the end, a real-life example of connecting Museums in the city of Zagreb with optical network of minimal cost was tested with all three algorithms.

• Keywords: povezani graf; minimalno razapinjuće stablo; algoritmi
• Keywords (english): connected graph; minimum spanning tree; algorithms
• Language: croatian
• URN:NBN: urn:nbn:hr:168:202360
• 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: 2023-01-13 13:48:43