47
правок
Изменения
м
→Доказательство корректности
Нет неустойчивых пар.
|proof=
1. Предположим A-b (A, B - — мужчины; a, b - — женщины; A женат на a, B женат на b) - — нестабильная пара в паросочетнаии, найденном алгоритмом Гейла-Шепли
2. Рассмотрим два случая:
=> A находит a более привлекательной, чем b
=> A-b - — устойчивая пара
2.2. A делал предложение b
=> b находит B более привлекательным, чем A
=> A-b - — устойчивая пара
}}
=== Асимптотика алгоритма ===
