Решение

Естественный подход к подобным задачам — предположить, что утверждение лож- но, и попытаться прийти к противоречию. Что будет означать ложность исходной предпосылки в данном случае? Что существует некоторое устойчивое паросоче- тание M, в котором хороший мужчина m находится в паре с плохой женщиной w.

Теперь нужно понять, как выглядят остальные пары из M. Всего есть к хороших мужчин и к хороших женщин. Может ли при этом каждая хорошая женщина нахо- диться в паре с хорошим мужчиной в этом паросочетании M? Нет: один из хороших мужчин (а именно m) уже выбрал плохую женщину, поэтому осталось всего к - 1 других хороших мужчин. Следовательно, даже если все остальные находятся в паре с хорошими женщинами, все равно остается некоторая плохая женщина, которая находится в паре с плохим мужчиной.

Обозначим ее w'. Теперь в M легко выявляется неустойчивость: возьмем пару (m, w'). Каждый из ее участников хорош, но находится в паре с плохим партнером. Получается, что каждый из участников потенциальной пары m и w' предпочитает другого своему текущему партнеру, а следовательно, пара (m, w') создает неустой- чивость. Это противоречит исходному допущению об устойчивости M, что и тре- бовалось доказать. ■

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Решение:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
  13. Убеждения и решения