Problem maksimalnog sparivanja u bipartitnim grafovima uz pomoć maksimalnog protoka u transportnim mrežama

diplomski rad

• Naslov (engleski): Maximum bipartite matching problem via maximum flow in flow networks
• Autor: Zvonimir Spajić
• Mentor: Andrea Aglić-Aljinović (mentor)
• Član povjerenstva: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Tomislav Grgić (č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: 2014-07-07, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Elektrotehnika

Sažetak

Ovaj rad bavi se problemom pronalaska maksimalnog sparivanja bipartitnog grafa pomoću maksimalnog toka. U radu je dan opći prikaz bitnijih definicija vezanih uz grafove te mreže toka kao i način prikazivanja grafova na računalima. Sam problem pronalaska maksimalnog sparivanja bipartitnog grafa rješava se njegovom transformacijom u mrežu toka nad kojom se onda pronalazi maksimalan tok što je ujedno i vrijednost maksimalnog sparivanja. Maksimalan tok pronalazi se putem Ford Fulkersonovog algoritma, odnosno njegovom poboljšanom inačicom - Edmonds Karpovim algoritmom koji koristi algoritam pretrage prvo u širinu za pronalazak dodavajućih puteva u mreži čime se postiže bolja efikasnost algoritma.

Sažetak (engleski)

This diploma thesis describes the maximum bipartite matching problem via maximum flow. The thesis gives a description of some basic definitions about graphs and flow networks as well as description of the ways of representing graphs and flow networks on the computer. The problem of finding maximum bipartite matching is solved by transforming the bipartite graph into a flow network and then finding a maximum flow of the network, which , at the same time is the value of maximum bipartite matching as well. This is done by the Ford Fulkerson algorithm, more precisely, by it's enhanced version – Edmonds Karp algorithm, which uses the Breadth First Search to find augmenting paths, which as a result, increases algorithm efficiency.

• Ključne riječi: maksimalan tok sparivanje bipartitni graf transportne mreže
• Ključne riječi (engleski): maximum bipartite matching flow networks
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:118316
• Studijski program: Naziv: Informacijska i komunikacijska tehnologija; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka informacijske i komunikacijske tehnologije (mag. ing. inf. et comm. techn.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 11:53:15