47
правок
Изменения
→Анализ полученного алгоритмом паросочетания
|statement=
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).
|proof=
}}
|statement=
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наихудшее для женщин.
|proof=
# Предположим A-c (A, B — мужчины; с, d — женщины; A женат на d, B женат на c) — стабильная пара в паросочетании S', найденном алгоритмом Гейла-Шепли, но A не самый худший выбор для c.
# Тогда существует стабильная пара в паросочетании S, в которой c замужем за B, который менее привлекателен, чем A. Тогда пусть мужем d будет A в паросочетании S
# Получается A считает c более привлекательной, чем d. Соответсвенно A-c — нестабильная пара в паросочетании S.
}}
== Обобщения задачи ==
