Algoritmi za traženje maksimalnog toka minimalne cijene u mreži

diplomski rad

• Autor: Tomislav Bujanović
• Mentor: Robert Manger (mentor)
• Član povjerenstva: Robert Manger (predsjednik povjerenstva)
• Član povjerenstva: Luka Grubišić (član povjerenstva)
• Član povjerenstva: Matija Kazalicki (član povjerenstva)
• Član povjerenstva: Marcela Hanzer (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2017-09-26, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu proučavali smo problem maksimalnog toka minimalne cijene u mreži. Radi se o poznatom problemu u području teorije grafova, a kao što smo i pokazali, ima široku primjenu i u svakodnevnom životu. Kako bismo istražili teoretsku pozadinu ovog problema, uveli smo pojmove potencijala i reduciranih cijena. To nam je omogućilo da dokažemo nekoliko rezultata u pogledu optimalnih uvjeta za rješenje problema, a koji su nam poslužili kao osnova za dokazivanje točnosti danih algoritama. Pokazali smo da teorija maksimalnog toka minimalne cijene povezuje neke poznate rezultate iz teorije maksimalnog toka i pronalaska najkraćih puteva u mreži. Najveći dio ovog rada odnosi se na tri algoritma: algoritam s poništavanjem negativnih ciklusa, algoritam s traženjem najkraćih puteva i primal-dual algoritam. Pokazali smo nekoliko svojstava tih algoritama te analizirali njihove vremenske složenosti. Testiranjem na skupu podataka koji je uključivao mreže različitih broja vrhova i bridova potvrdili smo pretpostavku da primal-dual algoritam ima najbolje performanse od sva tri prikazana algoritma.

Sažetak (engleski)

In this work we study the minimum cost flow problem. This problem is well known in graph theory and has wide applications in everyday life. In order to explore the theoretical background of the problem, we introduced the notions of potentials and reduced costs. This enabled us to prove several results regarding optimality conditions for the problem solution, which served as a basis for showing the correctness of algorithms that solve the problem. The theory of the minimum cost flow problem combines several well known facts from the theory of the maximum flow and the shortest path problems. Large part of this work is focused on three algorithms: the cycle-canceling algorithm, the successive shortest path algorithm and the primal-dual algorithm. We presented a number of properties of these algorithms and analyzed their time complexities. Testing on a dataset that included graphs of varying sizes and densities has confirmed our assumption that the primal-dual algorithm has the best performance among the presented algorithms for solving the minimum cost flow problem.

• Ključne riječi: problem maksimalnog toka minimalne cijene u mreži; algoritam s poništavanjem negativnih ciklusa; algoritam s traženjem najkraćih puteva; primal-dual algoritam
• Ključne riječi (engleski): minimum cost flow problem; the cycle-canceling algorithm; the successive shortest path algorithm; the primal-dual algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:608924
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2017-12-20 12:10:42