Algoritmi za problem toka kroz mrežu

diplomski rad

• Autor: Josipa Surić
• Mentor: Saša Singer (mentor)
• Član povjerenstva: Saša Singer (predsjednik povjerenstva)
• Član povjerenstva: Mladen Jurak (član povjerenstva)
• Član povjerenstva: Zvonimir Bujanović (član povjerenstva)
• Član povjerenstva: Robert 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 obrane: 2018-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: problem toka kroz mrežu; Ford-Fulkersonov algoritam; Edmonds-Karpov algoritam
• Ključne riječi (engleski): network flow problem; Ford-Fulkerson algorithm; Edmonds-Karp algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:588292
• 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: 2019-06-19 10:47:17