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

diplomski rad

• Naslov (engleski): Push-relabel algorithm for finding maximum flow
• Autor: Mario Zečić
• Mentor: Ivica Nakić (mentor)
• Član povjerenstva: Ivica Nakić (predsjednik povjerenstva)
• Član povjerenstva: Robert Manger (član povjerenstva)
• Član povjerenstva: Mladen Jurak (član povjerenstva)
• Član povjerenstva: Marko Radulović (č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: 2022-09-29, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: algoritam za pronalaženje maksimalnog toka; programski jezik Javascript
• Ključne riječi (engleski): algorithm for finding maximum flow; Javascript programming language
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:689244
• 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: 2022-11-11 10:41:36