Algoritem potisni-povišaj za iskanje maksimalnih pretokov : delo diplomskega seminarja

Čampa, Marcel (author), Cabello, Sergio (mentor)

Ideja dela je spoznati se z osnovnimi pojmi teorije grafov, kot so omrežje, pretok in maksimalni pretok ter predstaviti algoritem potisni-povišaj za iskanje maksimalnega pretoka v omrežju. Algoritem je tudi implementiran, pokazana pa je tudi njegova časovna zahtevnost in pravilnost delovanja. Uporabnost iskanja maksimalnih pretokov je ponazorjena z dvema primeroma iz vsakdanjega življenja.

• Language: Slovenian
• Keywords: pretok, potisni-povišaj, graf, omrežje, maksimalni pretok, optimizacija
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2018
• PID: 20.500.12556/RUL-105087
• UDC: 519.8
• COBISS.SI-ID: 18475609
• Publication date in RUL: 25.10.2018

Secondary language

• Language: English
• Title: Push-relabel algorithm for maximum flow problem

Abstract

The idea of this work is to get used to basic concepts of graph theory, e.g. network, flow and maximum flow. The core is an explanation of push-relabel algorithm for finding maximum flow through a network. The algorithm is also implemented and its time complexity and correctness are proven. It is also shown with two examples how one can use maximum flows in real life.

• Keywords: flow, push-relabel, graph, network, maximum flow, optimization