Sparivanja u grafovima

master's thesis

• Author: Anđelko Kolak
• Mentor: Dragutin Svrtan (mentor)
• Mentor: Marko Vrdoljak (mentor)
• Committee member: Marko Vrdoljak (predsjednik povjerenstva)
• Committee member: Mladen Jurak (član povjerenstva)
• Committee member: Saša Singer (član povjerenstva)
• Committee member: Miljenko Marušić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2015-09-25, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom diplomskom radu iznijeli smo neke osnovne rezultate o sparivanjima u grafovima. Prvo poglavlje započeli smo definicijama, a zatim smo dokazali fundamentalni Bergeov teorem koji daje vezu između maksimalnosti sparivanja i uvećavajućih putova u grafu. Nakon toga obrađeni su nužni i dovoljni uvjeti da bi u bipartitnom grafu postojalo savršeno sparivanje. Osim toga, željeli smo opisati nužne i dovoljne uvjete da bi u općenitom grafu postojalo savršeno sparivanje. Stoga smo u idućem odjeljku iskazali definiciju barijere na općenitom grafu. Ovdje je dokazan Tutte-Bergeov teorem koji govori kako svaki graf ima barijeru. Iz njega slijedi i Tutte-Bergova formula koja nam daje broj bridova u najvećem sparivanju grafa. U konačnici su navedeni nužni i dovoljni uvjeti da bi u općenitom grafu postojalo savršeno sparivanje, tj. dokazan je Tutteov teorem. U prvom poglavlju još smo prikazali vezu između najvećeg sparivanja i minimalnog bridovnog pokrivača u grafu. Upoznali smo se i s problemom f -faktora, te smo vidjeli kako se problem f -faktora može svesti na problem savršenog sparivanja. Cilj drugog poglavlja bio je predstaviti algoritam koji pronalazi najveće sparivanje u bilo kojem grafu. Započeli smo s opisom algoritma APS (Augmenting Path Search) koji pronalazi uvećavajući put u bipartitnom grafu. Na spomenutom algoritmu temelji se Egervaryjev algoritam koji pronalazi najveće sparivanje u bipartitnom grafu. U radu je obrađen i ovaj algoritam. Kako bi mogli prijeći na općeniti graf iskazali smo definicije cvijeta i cvjetnjaka. Tada smo opisali dorađeni algoritam APS koji pronalazi uvećavajući put u općenitom grafu. Nakon toga, mogli smo predstaviti poopćenje Egerváryjevog algoritma, takozvani Edmondsov algoritam, koji pronalazi najveće sparivanje u općenitom grafu.

Abstract (english)

This thesis exposes some basic results regarding matching in graphs. The first chapter introduces definitions followed by a proof of fundamental Berge’s Theorem, which shows the link between maximum matching and augmenting paths in graphs. The following step reveals necessary and sufficient conditions for the existence of perfect matching in a bipartite graph. However, the goal was to present necessary and sufficient conditions for any graph. Therefore, the concept of a barrier was defined in an arbitrary graph. At this point the Tutte-Berge Theorem was proved according to which every graph has a barrier. Tutte-Berge Formula gives also the number of edges in maximum matching in a graph. Finally, the necessary and sufficient conditions were listed for the existence of perfect matching in an arbitrary graph, i. e. the Tutte’s Theorem was proved. The first chapter also shows the link between the maximum matching and minimum covering in graphs. The f-factor problem was introduced and it was described how this problem can be reduced to the problem of perfect matching. The aim of the second chapter was to present the algorithm which finds maximum matching in an arbitrary graph. First we have described the Augmenting Path Search (APS) algorithm which finds an augmenting path in a bipartite graph. After describing the APS algorithm it was possible to make progress towards the Egerváry’s Algorithm which finds the maximum matching in a bipartite graph. In order to bring into the discussion the arbitrary aspect of graphs, the concept of blossom and flowers was introduced. Then the generalized APS algorithm was exposed as capable of finding the augmenting path in any graph. This is followed by an improvement of the Egerváry’s Algorithm, so called Edmonds’ Algorithm, which finds the maximum matching in an arbitrary graph.

• Keywords: sparivanje u grafovima; fundamentalni Bergeov teorem; savršeno sparivanje; Tutte-Bergeov teorem; Tutte-Bergova formula; algoritam APS; Egerváryjev algoritam; Edmondsov algoritam
• Keywords (english): matching in graphs; fundamental Berge's Theorem; perfect matching; Tutte-Berge Theorem; Tutte-Berge Formula; Augmenting Path Search algorithm; APS algorithm; Egerváry’s Algorithm; Edmonds’ Algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:217:825145
• Study programme: Title: Pure Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Access restricted to students and staff of home institution
• Created on: 2019-02-14 11:13:52