Sparivanja u grafovima

diplomski rad

• Autor: Anđelko Kolak
• Mentor: Dragutin Svrtan (mentor)
• Mentor: Marko Vrdoljak (mentor)
• Član povjerenstva: Marko Vrdoljak (predsjednik povjerenstva)
• Član povjerenstva: Mladen Jurak (član povjerenstva)
• Član povjerenstva: Saša Singer (član povjerenstva)
• Član povjerenstva: Miljenko Marušić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2015-09-25, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: sparivanje u grafovima; fundamentalni Bergeov teorem; savršeno sparivanje; Tutte-Bergeov teorem; Tutte-Bergova formula; algoritam APS; Egerváryjev algoritam; Edmondsov algoritam
• Ključne riječi (engleski): 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
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:825145
• Studijski program: Naziv: Teorijska matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Pristup korisnicima matične ustanove
• Datum i vrijeme pohrane: 2019-02-14 11:13:52