Analiza algoritama za traženje maksimalnog toka u grafu

završni rad

• Naslov (engleski): Analysis of Algorithms for Finding Maximum Flow in a Graph
• Autor: Lovro Bosnar
• Mentor: Tomislav Burić (mentor)
• Član povjerenstva: Tomislav Burić (predsjednik povjerenstva)
• Član povjerenstva: Anamari Nakić (član povjerenstva)
• Član povjerenstva: Ana Anušić (č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: 2017-07-10, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Cilj ovog rada bio je istražiti algoritam traženja maksimalnog toka u grafu, ali s različitim algoritmima traženja puta. Motivacija je bila potpunije upoznavanje maksimalnog toka i algoritama pretraživanja. U prvom dijelu je dana temeljna teorija grafova, objašnjen je specifičan graf – mreža te tok u mreži. U drugom dijelu je objašnjen algoritam za traženje maksimalnog toka. Specifično je obrađen Ford-Fulkersonov algoritam. Konačno u trećem dijelu prikazana je programska implementacija. Objašnjen je način prikaza grafa u računalu. Nakon svih potrebnih definicija analizirana su tri algoritma za traženje puta. Algoritam pretraživanja u širinu, algoritam pretraživanja u dubinu i Dijkstrin algoritam. Algoritmi su opisani matematički, pseudokodom te u dodatku se nalazi programska implementacija. Za svaki od algoritama navedene su iteracije i neke ključne karakteristike.

Sažetak (engleski)

Purpose of this paper was to study maximum flow algorithm with different path finding algorithms. Motivation was to learn more about maximum flow and path finding algorithms. The first part of this paper contains fundamentals of graph theory, theory behind specific graphs called networks and flow in network. The second part defines the core of this paper – Ford-Fulkerson maximum flow algorithm. Algorithm was described mathematically and with pseudo-code. The third part contains specifics of program implementation and analysis of maximum flow algorithm with different path finding algorithms. It was defined how to represent a graph in a computer. Chosen algorithms are: breadth first search, depth first search and Dijkstra's algorithm. Every path finding algoritam was described and for every algorithm the corresponding iterations were showed.

• Ključne riječi: graf; mreža; tok; Ford-Fulkersonov algoritam; pretraživanje u širinu; pretraživanje u dubinu; Dijkstrin algoritam
• Ključne riječi (engleski): graph; network; flow; Ford-Fulkerson algorithm; breadth first search; depth first search; Dijkstra's algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:431927
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-03-13 19:13:38