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

master's thesis

• Author: Tomislav Bujanović
• Mentor: Robert Manger (mentor)
• Committee member: Robert Manger (predsjednik povjerenstva)
• Committee member: Luka Grubišić (član povjerenstva)
• Committee member: Matija Kazalicki (član povjerenstva)
• Committee member: Marcela Hanzer (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2017-09-26, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: problem maksimalnog toka minimalne cijene u mreži; algoritam s poništavanjem negativnih ciklusa; algoritam s traženjem najkraćih puteva; primal-dual algoritam
• Keywords (english): minimum cost flow problem; the cycle-canceling algorithm; the successive shortest path algorithm; the primal-dual algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:217:608924
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2017-12-20 12:10:42