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

Čampa, Marcel (avtor), 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.

• Jezik: Slovenski jezik
• Ključne besede: pretok, potisni-povišaj, graf, omrežje, maksimalni pretok, optimizacija
• Vrsta gradiva: Delo diplomskega seminarja/zaključno seminarsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2018
• PID: 20.500.12556/RUL-105087
• UDK: 519.8
• COBISS.SI-ID: 18475609
• Datum objave v RUL: 25.10.2018

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Push-relabel algorithm for maximum flow problem

Izvleček

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.

• Ključne besede: flow, push-relabel, graph, network, maximum flow, optimization