Sparivanja u grafovima

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

[img] 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)
Supervisor: Svrtan, Dragutin
Date: 2015
Number of Pages: 31
Subjects: NATURAL SCIENCES > Mathematics
Divisions: Faculty of Science > Department of Mathematics
Depositing User: Iva Prah
Date Deposited: 20 Oct 2015 11:07
Last Modified: 18 Aug 2016 07:31
URI: http://digre.pmf.unizg.hr/id/eprint/4286

Actions (login required)

View Item View Item