prikaz prve stranice dokumenta Sparivanja u bipartitnom grafu i primjene
No public access
master's thesis
Sparivanja u bipartitnom grafu i primjene
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2021. urn:nbn:hr:168:763392
Šaško, Mario
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Šaško, M. (2021). Sparivanja u bipartitnom grafu i primjene (Master's thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:763392

Šaško, Mario. "Sparivanja u bipartitnom grafu i primjene." Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2021. https://urn.nsk.hr/urn:nbn:hr:168:763392

Šaško, Mario. "Sparivanja u bipartitnom grafu i primjene." Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2021. https://urn.nsk.hr/urn:nbn:hr:168:763392

Šaško, M. (2021). 'Sparivanja u bipartitnom grafu i primjene', Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 02 December 2024, https://urn.nsk.hr/urn:nbn:hr:168:763392

Šaško M. Sparivanja u bipartitnom grafu i primjene [Master's thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2021 [cited 2024 December 02] Available at: https://urn.nsk.hr/urn:nbn:hr:168:763392

M. Šaško, "Sparivanja u bipartitnom grafu i primjene", Master's thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2021. Available at: https://urn.nsk.hr/urn:nbn:hr:168:763392

Metadata
TitleSparivanja u bipartitnom grafu i primjene
Title (english)Matching in Bipartite Graphs and Applications
AuthorMario Šaško
MentorAndrea Aglić Aljinović (mentor)
Committee memberAndrea Aglić Aljinović (predsjednik povjerenstva)
Committee memberJosipa Pina Milišić (član povjerenstva)
Committee memberLana Horvat Dmitrović (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2021-09-23, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:763392
Study programmeTitle: Computing
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
Type of resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2023-01-13 13:54:27