Matching in Bipartite Graphs and Applications

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.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