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

master's thesis

• Title (english): Maximum bipartite matching problem via maximum flow in flow networks
• Author: Zvonimir Spajić
• Mentor: Andrea Aglić-Aljinović (mentor)
• Committee member: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Committee member: Tomislav Grgić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2014-07-07, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Electrical Engineering

Abstract

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.

Abstract (english)

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.

• Keywords: maksimalan tok sparivanje bipartitni graf transportne mreže
• Keywords (english): maximum bipartite matching flow networks
• Language: croatian
• URN:NBN: urn:nbn:hr:168:118316
• Study programme: Title: Information and Communication Technology; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka informacijske i komunikacijske tehnologije (magistar/magistra inženjer/inženjerka informacijske i komunikacijske tehnologije)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 11:53:15