693
правки
Изменения
→Анализ полученного алгоритмом паросочетания
Алгоритм Гейла-Шепли гарантирует, что будет найдено некоторое решение задачи. Но решений может быть более одного. Зададимся вопросом, какими свойствами обладает решение, найденное алгоритмом.
{{Лемма4
|id=lemma4
|about=Лемма 4 (man-optimality)
|statement=
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).
}}
{{Лемма5
|id=lemma5
|about=Лемма 5 (woman-pessimality)
|statement=
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наихудшее для женщин.
