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

master's thesis

• Author: Juraj Šikonja
• Mentor: Robert Manger (mentor)
• Committee member: Robert Manger (predsjednik povjerenstva)
• Committee member: Filip Najman (član povjerenstva)
• Committee member: Maja Resman (član povjerenstva)
• Committee member: Marko Tadić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2017-07-18, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: 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
• Keywords (english): combinatorial problems; network flows; maximum flow; minimum cut; Max-flow min-cut theorem; Algorithms of Ford and Fulkerson; Dinitz algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:217:155824
• 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: 2018-03-21 12:42:16