20.500.12556/DKUM-61029 Algoritmi minimalnega vpetega drevesa v vsakdanjem življenju Minimum spanning tree algorithms in everyday life V zaključni projketni nalogi je opisano minimalno vpeto drevo in načini iskanja minimalnega vpetega drevesa v grafu. Predstavljeni in analizirani so trije algoritmi in sicer Primov, Kruskalov in Boruvkin algoritem. Podrobneje so predstavljene tudi programske implementacije teh treh algoritmov. V nadaljevanju je predstavljena praktična uporaba minimalnega vpetega drevesa v vsakdanjem življenju ter opis enega konkretnega primera – postavljanja vodovodnega omrežja. Za izbiro optimalnega algoritma so java programske implementacije algoritmov testirane na 408 testnih datotekah z grafi. Analizirana je odvisnost časovne zahtevnosti algoritma od števila povezav v grafu. Hkrati je predstavljena še primerjava časovne učinkovitosti vseh treh analiziranih algoritmov. The final project work describes the minimum spanning tree and a way to find the minimum spanning tree in the graph. Three different algorithms are presented and analyzed: Prim’s, Kruskal’s and Boruvka’s. Software implementation of each algorithm is also discussed. Furthermore, usage of the minimum spanning tree in everyday life is addressed through description of one practical problem regarding a water supply network and its solution. For making the best choice between the algorithms, three Java software implementations are tested on 408 graphs. Dependency of the time efficiency given the overall number of edges in the graph with the constant number of vertices is presented, together with comparison of time efficiencies for all three algorithms. minimalno vpeto drevo uporaba v vsakdanjem življenju primerjava algoritmov časovna zahtevnost minimum spanning tree comparison of different algorithms usage in everyday life time complexity true true false [M. Gajić] Slovenski jezik Angleški jezik Delo diplomskega projekta/projektno delo 2016-07-15 16:05:36 2017-03-22 13:58:04 2022-06-25 03:07:17 2019-07-11 12:06:32 2016 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 621.39 20406294 URN:SI:UM:DK:4XXPJGOL UN_Gajic_Marija_2016.pdf UN_Gajic_Marija_2016.pdf 1 D1643377CFADEC762E5A1416C57E8815 da2fb13533df49c92fde9826be485aab086b5e0483f57f469a726660c64c0039 ed9cfb7c-7c0c-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=97024 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0