Rješavanje kombinatornih problema pomoću tokova u mrežama

diplomski rad

• Autor: Juraj Šikonja
• Mentor: Robert Manger (mentor)
• Član povjerenstva: Robert Manger (predsjednik povjerenstva)
• Član povjerenstva: Filip Najman (član povjerenstva)
• Član povjerenstva: Maja Resman (član povjerenstva)
• Član povjerenstva: Marko Tadić (č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: 2017-07-18, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Tema ovog rada je zanimljivo područje rješavanja kombinatornih problema pomoću tokova u mrežama. U radu se najprije definiraju osnovni pojmovi i predstavljaju primjeri vezani za područja neusmjerenih i usmjerenih grafova, mreža i tokova u mrežama, kao što su bridovi, putevi, tokovi te kapacitet bridova. Nakon toga uvodi se centralni problem pronalaženja maksimalnog toka u danoj mreži. Potom dokazujemo da je problem ekvivalentan problemu minimalnog reza u danoj mreži čime dolazimo da najvažnijeg teorema tzv. Max-flow min-cut teorema. Nakon što uvedemo potrebne pojmove i zakonitosti, predstaviti ćemo dva poznatija algoritma koji se koriste za pronalaženje maksimalnog toka u danim mrežama: Ford-Fulkerson algoritam i algoritam Dinitz. Oba algoritma kreću od nekog toka koji onda povećavaju dok ne dođu do maksimalnog toka. Ford-Fulkerson algoritam to postiže pomoću proširenih puteva, dok Dinitzov algoritam to postiže pomoću sporednih mreža i tzv. blokirajućih tokova. Kako se dobar dio kombinatornih problema može prikazati i rješavati pomoću simplificirane verzije mreža sa 0-1 tokom, malo ćemo detaljnije analizirati složenost Dinitzovog algoritma za tu vrstu mreža. Potom ćemo prikazati i objasniti nekoliko primjena mrežnih tokova za rješavanje određenih kombinatornih problema: maksimalno uparivanje u bipartitinim grafovima, te probleme PERT usmjerenih grafova. Za kraj ćemo na dva praktična problema maksimalnog uparivanja u bipartitnim grafovima: Raspodajele radika i Speed dating, pokazati kako bi se oni riješili pomoću tokova u mrežama, pritom koristeći i testirajući efikasnost Dinitzovog i Ford-Fulkersonovog algoritma koji su predstavljeni u prethodnim poglavljima.

Sažetak (engleski)

The subject of this paper is the interesting topic of solving combinatorial problems using network flows. The paper first defines the basic concepts and presents examples related to the areas of undirected and directed graphs, networks and network flows, as edges, paths, flows and edge capacity. After that, we introduce the central problem of finding the maximum flow in the given network. We prove that the problem is equivalent to the problem of the minimum cut in the given network, so that we come to the most important Max-flow min-cut theorem. After introducing the necessary terms and principles, we will present two commonly used algorithms used to find the maximum flow in the given networks: Algorithms of Ford and Fulkerson and the Dinitz algorithm. Starting from a given flow, both algorithms, increase it until the maximum flow is reached. The Ford-Fulkerson algorithm achieves this by means of augmented paths, while Dinitz algorithm achieves this by means of auxiliary networks and “blocking flows”. As large share of combinatorial problems can be displayed and solved using a simplified version of networks with 0-1 flows, we will analyze the complexity of the Dinitz algorithm for that type of networks. Afterwards we will show and explain several application of network flows in solving selected combinatorial problems: Maximum matching in bipartite graphs and PERT digraph problems. Finally, we use two practical problems of maximum matching in bipartite graphs: Worker distribution and Speed dating, to show how they can be solved using network flows. Here we will rely and test efficiency of two algorithms presented in previous chapters Dinitz algorithms and algorithms of Ford and Fulkerson.

• Ključne riječi: kombinatorni problemi; tokovi u mrežama; maksimalni tok u mreži; minimalni rez u mreži; Max-flow min-cut teorem; Ford-Fulkerson algoritam; algoritam Dinitz
• Ključne riječi (engleski): combinatorial problems; network flows; maximum flow; minimum cut; Max-flow min-cut theorem; Algorithms of Ford and Fulkerson; Dinitz algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:155824
• 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: 2018-03-21 12:42:16