Minimalna razapinjuća stabla u težinskim grafovima

završni rad

• Naslov (engleski): Minimum Spanning Trees in Weighted Graphs
• Autor: Krunoslav Vukmanić
• Mentor: Andrea Aglić-Aljinović (mentor)
• Član povjerenstva: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Mario Bukal (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2016-09-07, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: minimalno razapinjajuće stablo; Kruskalov algoritam; Primov algoritam
• Ključne riječi (engleski): minimum spanning tree; Kruskal's algorithm; Prim's algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:216626
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 14:28:16