ЛКШ-2022. Спецкурс. Устойчивое паросочетание. Алгоритм Гэйла-Шепли.

Обычно в олимпиадных задачах требуется найти максимальное паросочетание в двудольном графе, то есть составить пары из объектов двух видов. При этом заданы возможные пары (рёбра двудольного графа), и все рёбра являются однозначными, то есть ни одно паросочетание не является лучше другого.
На практике, однако, возникают задачи, когда возможные рёбра в паросочетании неравнозначны. Например, если есть задача зачисления абитуриентов в вузы, то у абитуриентов есть предпочтения - какие вузы и образовательные программы им нравятся больше. Также и у вузов есть предпочтения, кого из абитуриентов они скорее хотят видеть. Возникает задача распределения абитуриентов по вузам так, чтобы абитуриенты и вузы были, по возможности, максимально довольными.
Такие паросочетания называются "совершенными", в некотором смысле это наилучшие возможные паросочетания. Однако, и совершенных паросочетаний может быть много. Например, можно построить в некотором смысле наилучшее для абитуриентов совершенное паросочетание, а можно построить наилучшее для вузов совершенное паросочетание. Эту задачу решает алгоритм Гэйла-Шепли, который будет изложен в данном спецкурсе.