Izbrane teme sodobne fizike in matematike

Popularna prirejanja

Ta članek obravnava različna prirejanja v grafih in njihove lastnosti. Najprej se osredotoči na največja in stabilna prirejanja v dvodelnih grafih z utežmi, nato pa se kot kompromis med tema dvema konceptoma uvede popularna prirejanja. Predstavi tudi Gale-Shapleyjev algoritem za iskanje stabilnih prirejanj in algoritem za iskanje največjih popularnih prirejanj v dvodelnih grafih z utežmi.

This article discusses various matchings in graphs and their properties. It first focuses on maximum and stable matchings in weighted bipartite graphs, and then introduce popular matchings, a compromise between these two concepts. The article also presents the Gale-Shapley algorithm for computing a stable matching and an algorithm for computing a largest popular matching in weighted bipartite graphs.

avtor: Anja Rupnik
številka: 1
letnik: 12

PDF (0.3 Mb)

Vsi članki iz te številke

© 2017 Fakulteta za matematiko in fiziko Univerze v Ljubljani

Obiskovalci lahko berejo, brskajo in/ali prenesejo članke za osebno in nekomercialno uporabo. Vsebine je prepovedano reproducirati, spreminjati, prilagajati, objavljati, ali prodajati brez pisnega soglasja avtorja članka in nosilca avtorskih pravic v citatu.

Readers may view, browse, and/or download material for temporary copying purposes only, provided these uses are for noncommercial personal purposes. This material may not be further reproduced, distributed, modified, adapted, published, or sold in whole or part, without prior written permission from the author and copyright owner as cited.