Algoritmi za problem maksimalnog protoka u transportnoj mreži

diplomski rad

• Naslov (engleski): Algorithms for Finding the Maximum Flow in Network Flow
• Autor: Matej Jengić
• Mentor: Andrea Aglić-Aljinović (mentor)
• Član povjerenstva: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Ana Žgaljić Keko (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2015-07-06, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Problem maksimalnog protoka pripada matematičkoj grani koju nazivamo teorija grafova, a ona pak diskretnoj matematici. To je jedan od osnovnih problema kombinatorne optimizacije, sa širokim spektrom primjene u stvarnom svijetu. Tako je u ovom radu predočen koncept transportne mreže i protoka kroz nju. Prikazani su najznačajniji algoritmi za pronalaženje maksimalne vrijednosti protoka u danoj mreži.
Zadnji dio rada vezan je za programsku implementaciju konkretnog zadatka tj. implementaciju Ford-Fulkersonovog algoritma. Kao što dio tog zadatka i nalaže napravljena je aplikacija sa pripadajućom programskom potporom. Predstavljen je izgled konačnog programa, kao i kratke upute za rad s programom.

Sažetak (engleski)

The maximum flow problem belongs to a branch of mathematics called graph theory, which in turn belongs to discrete mathematics. It's one of the basic problems of combinatorial optimization, with a wide spectrum of applications in the real world. That's why, in this paper, a concept of a transport network and the flow through it is presented. Most important algorithms for finding the maximum value of flow in a given networks are shown.
Last part of the paper is related to a software implementation of the assignment - implementation of the Ford-Fulkerson algorithm. As per the given assignment, an application with it's belonging software support is made. The design of the software and short instructions on working with it are presented.

• Ključne riječi: Transportna mreža; tok; max-flow min-cut; Ford-Fulkersonov algoritam; maksimalni protok; pretraga u širinu (BFS); C#
• Ključne riječi (engleski): Transportation network; flow; max-flow min-cut; Ford-Fulkerson algorithm; maximum flow; breadth-first search (BFS); C#
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:984336
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 09:26:30