Sparivanja u bipartitnom grafu i primjene

diplomski rad

• Naslov (engleski): Matching in Bipartite Graphs and Applications
• Autor: Mario Šaško
• 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: 2021-09-23, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Ovaj rad bavi se svojstvima sparivanja u bipartitnim grafovima i njihovim primjenama. Uvodno se definira bipartitan graf, daje algoritam za provjeru bipartitnosti grafa i navode se osnovni oblici sparivanja. U glavnom dijelu se pomnije obrađuju sparivanja u bipartitnim grafovima i pokazuju se neke primjene. Potom se analiziraju Mađarski i Hopcroft-Karpov algoritam kao učinkoviti algoritmi za pronalazak savršenih sparivanja i sparivanja maksimalne kardinalnosti u bipartitnom grafu. Na kraju se povezuju maskimalna sparivanja s problemom parkiranja i s molekulskim strukturama vinilnih polimera.

Sažetak (engleski)

This thesis focuses on the properties of matchings in bipartite graphs and their applications. The introduction defines a bipartite graph, provides an algorithm for checking whether a given graph is bipartite, and lists the basic types of matchings. The main part explains matchings in bipartite graphs in more detail and shows some of the applications. Then, the Hungarian and Hopcroft-Karp algorithms are analyzed as efficient algorithms for finding perfect matchings and maximum cardinality matchings in a bipartite graph. Finally, maximal matchings are associated with the parking problem and with the molecular structures of vinyl polymers.

• Ključne riječi: sparivanja u bipartitnom grafu; sparivanja u grafu; Mađarski algoritam; Hopcroft-Karpov algoritam
• Ključne riječi (engleski): matchings in bipartite graphs; matchings in graphs; Hungarian method; Hopcroft-Karp algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:763392
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 13:54:27