Sparivanja u bipartitnim grafovima

završni rad

• Naslov (engleski): Matchings in Bipartite Graphs
• Autor: Rea Vukasović
• Mentor: Andrea Aglić Aljinović (mentor)
• Član povjerenstva: Andrea Aglić Aljinović (predsjednik povjerenstva)
• Član povjerenstva: Josipa Pina Milišić (član povjerenstva)
• Član povjerenstva: Lana Horvat Dmitrović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2023-07-06, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Na početku rada je definiran pojam bipartitnog grafa. U nastavku su prikazani istaknutiji oblici bipartitnih grafova poput stabla i cikličkih grafova. U radu se zatim detaljnije analizira pojam sparivanja s naglaskom na pojmove savršenog i maksimalnog sparivanja. U kontekstu sparivanja bipartitnih grafova spominje se Kőnig- Egerváry teorem. Rad pokriva i pojam sustava izrazitih predstavnika i daje dokaz Hallovog teorema kao središnjeg teorema u kontekstu sparivanja bipartitnih grafova.

Sažetak (engleski)

At the beginning of the paper, the concept of a bipartite graph is defined. The following sections present prominent forms of bipartite graphs such as trees and cycles. The paper then provides a more detailed analysis of the concept of matching, with emphasis on the notions of perfect and maximal matching. In the context of matching in bipartite graphs, the Kőnig-Egerváry theorem is mentioned. The paper also covers the concept of systems of distinct representatives and provides a proof of Hall's theorem as a central theorem in the context of matching in bipartite graphs.

• Ključne riječi: bipartitni graf; sustav izrazitih predstavnika; sparivanja; Gale-Shapley algoritam; Hallov teorem
• Ključne riječi (engleski): bipartite graph; system of distinct representatives; matchings; Gale-Shapley algorithm; Hall's theorem
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:761915
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-10-11 10:59:47