Minimalna razapinjuća stabla u težinskim grafovima

undergraduate thesis

• Title (english): Minimum Spanning Trees in Weighted Graphs
• Author: Krunoslav Vukmanić
• Mentor: Andrea Aglić-Aljinović (mentor)
• Committee member: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Committee member: Mario Bukal (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2016-09-07, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Ovaj rad se bavi minimalnim razapinjajućim stablima u težinskim grafovima. Na početku rada su dane neke općenite definicije grafova kako bi se tematika približila stablima. Nakon toga slijedi definicija stabla, zajedno sa svojstvima i pripadajućim dokazima. Opisan je pojam razapinjajućeg stabla u grafu, te nakon toga i minimalno i maksimalno razapinjajuće stablo u težinskom grafu. U radu su opisana dva algoritma pronalaženja minimalnog razapinjajućeg stabla nekog grafa. Za oba algoritma je dan opis, dokazana ispravnost, pseudokod, analiza složenosti i primjer. Na kraju, napravio sam programsku implementaciju oba algoritma. U radu su priloženi bitni dijelovi programa za obavljanje algoritma, kao i izlazni rezultati.

Abstract (english)

This work deals with the minimum spanning trees of weighted graphs. In the beggining, there are some general graph definitions, to get thematically closer to tree graphs. After that, trees are defined, together with their characteristics and proofs. Spanning trees are defined, and after them, the minimum and maximum spanning trees are defined also. This work also describes two algorithms for finding a minimum spanning tree for a weighted graph. There is a description, proof of corectness, pseudocode, complexity analisys, and an example for both algorithms. In the end, I made software implementations for both algorithms. This work also includes vital parts of the program, as well as the output data.

• Keywords: minimalno razapinjajuće stablo; Kruskalov algoritam; Primov algoritam
• Keywords (english): minimum spanning tree; Kruskal's algorithm; Prim's algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:168:216626
• 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: 2018-02-06 14:28:16