prikaz prve stranice dokumenta Goldberg-Tarjanov algoritam za pronalaženje maksimalnog protoka mreže
  Download
PDF 1.34 MB
undergraduate thesis
Goldberg-Tarjanov algoritam za pronalaženje maksimalnog protoka mreže
Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2020. urn:nbn:hr:200:318884
Matković, Dominik
Josip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek
Department of Software Engineering
Chair of Visual Computing

Institutional repository: Faculty of Electrical Engineering, Computer Science and Information Technology Osijek

Cite this document

Matković, D. (2020). Goldberg-Tarjanov algoritam za pronalaženje maksimalnog protoka mreže (Undergraduate thesis). Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek. Retrieved from https://urn.nsk.hr/urn:nbn:hr:200:318884

Matković, Dominik. "Goldberg-Tarjanov algoritam za pronalaženje maksimalnog protoka mreže." Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2020. https://urn.nsk.hr/urn:nbn:hr:200:318884

Matković, Dominik. "Goldberg-Tarjanov algoritam za pronalaženje maksimalnog protoka mreže." Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, 2020. https://urn.nsk.hr/urn:nbn:hr:200:318884

Matković, D. (2020). 'Goldberg-Tarjanov algoritam za pronalaženje maksimalnog protoka mreže', Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, accessed 29 April 2024, https://urn.nsk.hr/urn:nbn:hr:200:318884

Matković D. Goldberg-Tarjanov algoritam za pronalaženje maksimalnog protoka mreže [Undergraduate thesis]. Osijek: Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek; 2020 [cited 2024 April 29] Available at: https://urn.nsk.hr/urn:nbn:hr:200:318884

D. Matković, "Goldberg-Tarjanov algoritam za pronalaženje maksimalnog protoka mreže", Undergraduate thesis, Josip Juraj Strossmayer University of Osijek, Faculty of Electrical Engineering, Computer Science and Information Technology Osijek, Osijek, 2020. Available at: https://urn.nsk.hr/urn:nbn:hr:200:318884

Metadata
TitleGoldberg-Tarjanov algoritam za pronalaženje maksimalnog protoka mreže
Title (english)Goldberg-Tarjan's maximum flow algorithm
AuthorDominik Matković
MentorAlfonzo Baumgartner (mentor)
Committee memberAlfonzo Baumgartner (predsjednik povjerenstva)
Committee memberZdravko Krpić (član povjerenstva)
Committee memberIrena Galić (član povjerenstva)
GranterJosip Juraj Strossmayer University of Osijek
Faculty of Electrical Engineering, Computer Science and Information Technology Osijek
(Department of Software Engineering)
(Chair of Visual Computing)
Osijek
Defense date and country2020-09-29, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Data Processing
Abstract
Ovaj završni rad bavi se općim Goldberg-Tarjan algoritmom i problemom maksimalnog toka. Cilj problema maksimalnog toka je pronaći najveći mogući protok kroz protočnu mrežu. Postoje više algoritama koji se bave tim problemom no ovaj rad obrađuje opći Goldberg-Tarjan algoritam. Algoritam se sastoji 4 operacije guraj, promjena visine, preljev toka i inicijalizacija. Guraj gura višak protoka između točaka, promjeni visinu mijenja visinu točaka kada guranje nije moguće, preljev toka se vrši na točkama s viškom protoka te vrši operacije guraj i promjeni visinu dok preljev toka na toj točki nije nula i inicijalizacija postavlja visinu početne točke na visinu jednaku broju točaka i postavlja višak protoka na toj točki na ∞. Algoritam je implementiran u C# programskom jeziku.
Abstract (english)
This bachelor's thesis deals with the generic Goldberg-Tarjan algorithm and with the maximum flow problem. The goal of the maximum flow problem is to find the biggest flow through the flow through the flow network. There exist many algorithms that deal with the maximum flow problem but this thesis is concerned with the generic Goldberg-Tarjan Algorithm. The algorithm contains 4 operations push, relabel, flow excess and initialization. Push pushes excess flow in between edges, relabel changes the height of the edges when pushing isn't possible, flow excess is done on edges which have excess flow and it uses push and relabel until the excess flow is gone and finally initialization sets the height of the start edge to the numbers od total number of edges and its excess flow to ∞. The algorithm is implemented in the C# programming language.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:200:318884
Study programmeTitle: Undergraduate University Study Programme in Computer Engineering
Study programme type: university
Study level: undergraduate
Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2020-11-13 13:54:03