From Hall's theorem to the Gale-Shapley algorithm - matching theory and its applicatons

Celem pracy jest zaprezentowanie najważniejszych wyników dotyczących skojarzeń i możliwości ich zastosowania. Pierwsza część pracy dotyczy skojarzeń w grafach. Omówione zostają skojarzenia największe, całkowite oraz doskonałe, przedstawiono związek między skojarzeniem największym a ścieżkami rozszerzającymi. Opisane zostaje twierdzenie Halla charakteryzujące skojarzenia całkowite w grafach dwudzielnych oraz algorytm wyszukiwania skojarzenia całkowitego w grafie dwudzielnym. Omówiono skojarzenia doskonałe w grafach prostych i zaprezentowano twierdzenie Tutte'a charakteryzujące te skojarzenia. Opisano również algorytm Witzgalla i Zahna wyszukiwania skojarzenia największego w grafie prostym. Druga część pracy dotyczy spojrzenia na zagadnienie pod kątem modelowania rynku. Przedstawiony zostaje problem rekrutacji kandydatów na uczelnie wyższe, zdefiniowane zostają skojarzenia racjonalne, stabilne i optymalne. Przedstawiono algorytm Gale'a-Shapleya oraz omówiono jego własności. Na zakończenie zaprezentowane zostają przykłady działania programów w języku C++ realizujących opisane algorytmy, programy te dołączone są do pracy.

The aim of the paper is to present the main results of matching theory and its applications. The first part is dedicated to matchings in graph theory. Maximum matchings, perfect matchings and matchings of a set A in biparture graphs are discussed, a relation between augmenting paths and maximum matchings is shown. The paper contains Hall's theorem which describes matchings of A in biparture graphs and a proof gives an algorithm to find a matching of A in a biparture graph. Perfect matchings and Tutte's theorem are considered. There is also presented Witzgall-Zahn algorithm to find a maximum matching in a simple graph. The second part of the paper describes matchings from an economic point of view. The college admissions problem and the marriage problem are presented. Individually rational outcomes, stable outcomes and optimal outcomes are defined. There is also described the Gale-Shapley algorithm and its properties. Finally, there are presented programs written in C++ language which implement the algorithms described in the paper. The programs are attached to the work.