prikaz prve stranice dokumenta Algoritmi za problem toka kroz mrežu
  Preuzmi
PDF 232.04 KB
diplomski rad
Algoritmi za problem toka kroz mrežu
Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2018. urn:nbn:hr:217:588292
Surić, Josipa
Sveučilište u Zagrebu
Prirodoslovno-matematički fakultet
Matematički odsjek

Institucijski repozitorij: Repozitorij Prirodoslovno-matematičkog fakulteta

Citirajte ovaj rad

Surić, J. (2018). Algoritmi za problem toka kroz mrežu (Diplomski rad). Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:217:588292

Surić, Josipa. "Algoritmi za problem toka kroz mrežu." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2018. https://urn.nsk.hr/urn:nbn:hr:217:588292

Surić, Josipa. "Algoritmi za problem toka kroz mrežu." Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, 2018. https://urn.nsk.hr/urn:nbn:hr:217:588292

Surić, J. (2018). 'Algoritmi za problem toka kroz mrežu', Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, citirano: 23.12.2024., https://urn.nsk.hr/urn:nbn:hr:217:588292

Surić J. Algoritmi za problem toka kroz mrežu [Diplomski rad]. Zagreb: Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet; 2018 [pristupljeno 23.12.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:588292

J. Surić, "Algoritmi za problem toka kroz mrežu", Diplomski rad, Sveučilište u Zagrebu, Prirodoslovno-matematički fakultet, Zagreb, 2018. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:217:588292

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:217:588292
Podaci o radu
NaslovAlgoritmi za problem toka kroz mrežu
AutorJosipa Surić
MentorSaša Singer (mentor)
Član povjerenstvaSaša Singer (predsjednik povjerenstva)
Član povjerenstvaMladen Jurak (član povjerenstva)
Član povjerenstvaZvonimir Bujanović (član povjerenstva)
Član povjerenstvaRobert Manger (č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 obrane2018-09-26, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
U ovom radu govorimo o problemu toka kroz mrežu. Najprije definiramo neke osnovne pojmove koji su nam potrebni za daljnje razmatranje problema. Potom opisujemo Ford-Fulkersonov algoritam, koji je jedan od najznačajnijih algoritama za rješavanje problema toka kroz mrežu. Analiziramo složenost algoritma te na primjeru pokazujemo kako se može izračunati maksimalan tok kroz mrežu pomoću ovog algoritma. Prije same analize, navodimo teorem maksimalnog toka, odnosno, minimalnog reza, koji govori o odnosu ta dva problema. Nakon Ford-Fulkersonovog algoritma, opisujemo Edmonds-Karpov algoritam, koji je, zapravo, jedno poboljšanje Ford-Fulkersonovog algoritma. Zatim uvodimo neka proširenja problema toka kroz mrežu, poput cirkulacija sa zahtjevima i cirkulacija sa zahtjevima i donjim granicama. Navedena proširenja poslužit će nam kod rješavanja problema provođenja nadzora i određivanja rasporeda letenja. Problem provođenja nadzora i problem određivanja rasporeda letenja samo su neke od primjena problema toka kroz mrežu.
Sažetak (engleski)
In this paper we talk about the network flow problem. First of all, we define some of the basic terms needed for the future analysis of the problem. Then we describe the Ford-Fulkerson algorithm, which is one of the most important algorithms for solving the network flow problem. We analyse the complexity of the Ford-Fulkerson algorithm and also demonstrate by example how to compute the maximum flow by using this algorithm. Before the complexity analysis, we first talk about Max-Flow/Min-Cut Theorem, that talks about the relationship between maximum flow and minimum cut problems. After describing Ford-Fulkerson’s algorithm, we describe the Edmonds-Karp algorithm, which is, actually, one of improvements of the Ford-Fulkerson algorithm. Finally, we introduce some extensions of the maximum flow problem, like circulations with demands and circulations with demands and lower bounds. Above mentioned extensions of the maximum flow will be used to solve the problem of survey design and airline scheduling. Survey design and airline scheduling are just some applications of the maximum flow problem.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:217:588292
Studijski programNaziv: 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 resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2019-06-19 10:47:17