20.500.12556/RUL-172126 Popularna prirejanja delo diplomskega seminarja Popular matchings V diplomski nalogi predstavimo stabilna in popularna prirejanja v grafih s strogo funkcijo preferenc, nekatere njihove lastnosti in povezave med tema dvema vrstama prirejanj. Podamo tudi opis delovanja in dokaz pravilnosti treh algoritmov na dvodelnih grafih s strogo funkcijo preferenc: Gale-Shapleyjevega algoritma za iskanje stabilnega prirejanja, algoritma za iskanje največjega popularnega prirejanja in algoritma za iskanje prirejanja, ki je popularno med prirejanji vsaj tolikšne velikosti, kot je samo. Dokažemo tudi, da so velikosti prirejanj, ki jih vrnejo algoritmi, navzdol omejene glede na največje prirejanje grafa. In this thesis we present stable and popular matchings in graphs with a strict preference function, some of their properties, and the connections between these two types of matchings. We also provide a step-by-step description and a proof of correctness for three algorithms for bipartite graphs with strict preferences: the Gale-Shapley algorithm for computing a stable matching, an algorithm for computing a maximum-size popular matching, and an algorithm for computing a matching that is popular among all matchings of at least the same size. We also prove that the sizes of the matchings returned by the algorithms are bounded from below in relation to the maximum matching of the graph. popularna prirejanja stabilna prirejanja največja popularno prirejanja seznam preferenc Gale-Shapleyjev algoritem dvodelni grafi popular matchings stable matchings maximum-size popular matchings preference list Gale-Shapley algorithm bipartite graphs true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2025-09-06 08:15:09 2025-09-06 08:15:11 2025-10-06 03:51:47 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 152690 248035331 18925.pdf 18925.pdf 1 AAB6DC01F49D1C055992360DA9F096C2 c7712779fe362cfcdf5d485d3f4ba4cd8b6dfc498c8503c783a3e1302ab652e9 b0f20d74-8ae8-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=215926 Fakulteta za matematiko in fiziko 0 0 0