Guraj-Promijeni Visinu algoritam za pronalažanje maksimalnog protoka mreže
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...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Master Thesis |
| Language: | Croatian |
| Published: |
Sveučilište u Zagrebu. Prirodoslovno-matematički fakultet. Matematički odsjek.
2022
|
| Subjects: | |
| Online Access: | https://zir.nsk.hr/islandora/object/pmf:11266 https://urn.nsk.hr/urn:nbn:hr:217:689244 https://repozitorij.unizg.hr/islandora/object/pmf:11266 https://repozitorij.unizg.hr/islandora/object/pmf:11266/datastream/PDF |
| Summary: | 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. 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. |
|---|