# Sparivanja u grafovima

Kolak, Anđelko (2015) Sparivanja u grafovima. Diploma thesis, Faculty of Science > Department of Mathematics.

 PDF Restricted to Registered users only Language: Croatian Download (1MB) | Request a copy

## Abstract

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.

Item Type: Thesis (Diploma thesis) Svrtan, Dragutin 2015 31 NATURAL SCIENCES > Mathematics Faculty of Science > Department of Mathematics Iva Prah 20 Oct 2015 11:07 18 Aug 2016 07:31 http://digre.pmf.unizg.hr/id/eprint/4286