20.500.12556/RUL-100178 Algoritmi problema pretokov Network Flow Algorithms Predpostavimo, da je naš namen prenesti nek material od izvora do ponora preko vozlišč. Na naši poti imamo povezave, ki imajo maksimalno kapaciteto. Naš cilj je ugotoviti, največ koliko materiala lahko prenesemo od izvora do ponora, brez da bi kršili kapacitetne omejitve. Reševanje tega problema je bilo sprva možno s splošnimi tehnikami linearnega programiranja, kasneje pa so se začeli razvijati številni drugi algoritmi. Nekateri izmed njih uporabljajo pristope in metode, ki so zanimivi s teoretičnega vidika, drugi pa so primernejši za uporabo v praksi. Cilji diplomskega dela so predstavitev glavnih idej teh algoritmov, njihova analiza in prikaz nekaterih praktičnih primerov. Želimo ugotoviti, kateri algoritem je trenutno najhitrejši. Let us assume that it is our intention to transfer material from source to sink through the nodes of a graph. Each edge has a certain capacity. Our goal is to determine how much material can be transferred from the source to the sink without violating the capacity limit. Initially basic linear programming techniques were used to solve this problem, but later many other algorithms were discovered. Some of them use approaches and methods that are interesting from a theoretical point of view, while others are more suitable for practical use. The aims of the thesis are the presentation of these algorithms, their analysis and the display of basic examples. We want to figure out which algorithm is currently the fastest in solving this problem. pretok omrežje pretokov rezidualno omrežje nenasičene poti rezi blokiranje poti dinamična drevesa metoda potiska in ponovnega označevanja obilni graf flow network flow residual network augmenting paths cuts blocking path dynamic trees push relabel method abundance graph true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2018-03-12 12:10:02 2018-03-12 12:10:07 2022-08-24 17:22:10 0000-00-00 00:00:00 2018 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 19781 Ajdic_Gregor_-_Algoritmi_problema_pretokov.pdf Ajdic_Gregor_-_Algoritmi_problema_pretokov.pdf 1 67523AE68668CA3C5E306C1A7E96796D 6df59788749170944b124a95c4a096f703b4888da73aefc3c671e96b74a1412b b0035cdc-a1b4-11eb-a523-00155dcfd717 20.500.12556/rul/10665afa-f19f-426c-a956-b3b3417cad35 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=109860 Fakulteta za računalništvo in informatiko 0 0 0