20.500.12556/RUL-71851 Maksimalni pretoki na omrežjih diplomsko delo Maksimum flows in networks V diplomskem delu obravnavamo problem iskanja maksimalnega pretoka na omrežjih. Gre za problem, ki se v različnih oblikah pojavlja v raznih realnih situacijah. Nekatere takšne primere predstavimo tudi v diplomskem delu. Na začetku diplomskega dela predstavimo problem maksimalnega pretoka in pokažemo, da ima tak problem vedno optimalno rešitev. Vpeljemo pojem minimalnega reza in obravnavamo njegovo povezavo s problemom maksimalnega pretoka. V drugem delu diplomskega dela obravnavamo nekatere najbolj znane algoritme za iskanje maksimalnega pretoka. Najprej predstavimo Ford - Fulkersonov algoritem, nato pa se posvetimo predvsem Edmonds - Karpovemu in Goldberg - Tarjanovemu algoritmu. Pri vsakem izmed njiju analiziramo časovno zahtevnost, pomembne lastnosti in s pomočjo konkretnih primerov prikažemo njuno delovanje. In this diploma thesis the maximum flow problem is presented and investigated. Instances of this problem can in various practical situations. Some of these examples are presented in the thesis. The maximum flow problem is introduced and it is shown, that it always has an optimal solution. The concept of a minimal cut is defined and its connection to the maximum flow problem is investigated. In the second part of the diploma thesis some of the well known algorithms for searching the maximum flow are treated. First the Ford - Fulkerson algorithm is presented, than we concentrate mostly on the Edmonds - Karp algorithm and Goldberg - Tarjan algorithm. For each of these two algorithms the time complexity and the important characteristics are analyzed. Their operation is illustrated with a few concrete examples. maksimalen pretok minimalen rez Edmonds-Karpov algoritem Goldberg-Tarjanov algoritem časovna zahtevnost maximum flow true false false [A. Urh] Slovenski jezik Angleški jezik Diplomsko delo 2015-07-29 00:19:31 2015-07-29 00:19:31 2025-04-17 04:52:14 0000-00-00 00:00:00 2015 0 0 X, 61 str. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.1(043.2) 10636361 algoritmi_Urh.pdf algoritmi_Urh.pdf 1 6B505C29DA19ABF46F60370D3FB9B623 1b4dbf0da7cbf715f2f7aa9d1c1f56eaa34677f00a84497edf50d719f206cb7f 31dd8258-1aa7-11f0-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=204036 Pedagoška fakulteta 0 0 0