Algoritmi za problem toka kroz mrežu

master's thesis

• Author: Josipa Surić
• Mentor: Saša Singer (mentor)
• Committee member: Saša Singer (predsjednik povjerenstva)
• Committee member: Mladen Jurak (član povjerenstva)
• Committee member: Zvonimir Bujanović (član povjerenstva)
• Committee member: Robert Manger (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2018-09-26, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: problem toka kroz mrežu; Ford-Fulkersonov algoritam; Edmonds-Karpov algoritam
• Keywords (english): network flow problem; Ford-Fulkerson algorithm; Edmonds-Karp algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:217:588292
• 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: 2019-06-19 10:47:17