Вопрос 41 из 42
Практика: доказательства и комбинаторные модели
Отложенное принятие: почему устойчивое назначение существует
От чтения к действию
А теперь — вы
Разберёмся в теме
Пусть две группы по n участников имеют строгие полные списки предпочтений по другой группе. Алгоритм Гейла–Шепли, где свободный предлагающий обращается к следующему ещё не отвергнувшему его участнику, заканчивается совершенным устойчивым паросочетанием. Устойчивость означает отсутствие неназначенной пары, оба участника которой предпочитают друг друга своим партнёрам.
Частые вопросы
Где найти подробное решение?
Перейдите по ссылке «Объяснение и примеры» над этим блоком. Там разобрана тема текущего вопроса.
Можно ли попробовать снова?
Да. После проверки можно изменить ответ. Переход к следующему вопросу не блокируется результатом, а личный счёт не сохраняется.