Guraj-Promijeni Visinu algoritam za pronalažanje maksimalnog protoka mreže

master's thesis

• Title (english): Push-relabel algorithm for finding maximum flow
• Author: Mario Zečić
• Mentor: Ivica Nakić (mentor)
• Committee member: Ivica Nakić (predsjednik povjerenstva)
• Committee member: Robert Manger (član povjerenstva)
• Committee member: Mladen Jurak (član povjerenstva)
• Committee member: Marko Radulović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2022-09-29, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

Glavni cilj ovog rada bio je prikazati guraj-promijeni visinu algoritam za pronalaženje maksimalnog toka. U prvom poglavlju iznijeli smo osnovne pojmove i rezultate vezane za sami problem maksimalnog toka te jedan primjer primjene algoritma za pronalaženje maksimalnog toka u problemu koji se na prvi pogled ne može tako rješiti. Zatim smo u drugom poglavlju, pomoću rezultata iz prvog poglavlja, prikazali guraj-promijeni visinu algoritam i dokazali neka njegova svojstva. U drugom poglavlju smo također prikazali i jednu moguću implementaciju tog algoritma koristeći programski jezik Javascript. Za kraj, u trećem poglavlju smo opisali tri različite varijante guraj-promijeni visinu algoritma te prikazali njihove implementacije, također koristeći programski jezik Javascript.

Abstract (english)

The main goal of this thesis was to present a push-relabel algorithm for finding maximum flow. In the first chapter, we presented basic terms and related results for the maximum flow problem itself and one example of the application of maximum flow in a problem that, at first glance, cannot be solved that way. Then we have, in the second chapter, with the help of the results from the first chapter, showed push-relabel algorithm and proved some of its properties. In the second chapter we also presented one possible implementation of that algorithm using the Javascript programming language. For the end, in the third chapter we described three different variants of the push-relabel algorithm and presented their implementations, also using the Javascript programming language.

• Keywords: algoritam za pronalaženje maksimalnog toka; programski jezik Javascript
• Keywords (english): algorithm for finding maximum flow; Javascript programming language
• Language: croatian
• URN:NBN: urn:nbn:hr:217:689244
• 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: 2022-11-11 10:41:36