Algoritmi problema pretokov

Abstract
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.

Language: Slovenian pretok, omrežje pretokov, rezidualno omrežje, nenasičene poti, rezi, blokiranje poti, dinamična drevesa, metoda potiska in ponovnega označevanja, obilni graf Bachelor thesis/paper (mb11) FRI - Faculty of computer and information science 2018 377 335 (0 votes) Voting is allowed only to logged in users. AddThis uses cookies that require your consent. Edit consent...

## Secondary language

Language: English Network Flow Algorithms 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. flow, network flow, residual network, augmenting paths, cuts, blocking path, dynamic trees, push relabel method, abundance graph