Примеры
Для демонстрации этих определений будут рассмотрены два очень простых при- мера задачи устойчивых паросочетаний.
Для начала допустим, что имеется множество из двух мужчин {m, m’ } и множе- ство из двух женщин {w, w’ }. Списки предпочтений выглядят так:
- m предпочитает w женщине w’;
- m’ предпочитает w женщине w’;
- w предпочитает m мужчине m’;
- w’ предпочитает m мужчине m’.
Если рассматривать этот набор списков предпочтений на интуитивном уров- не, он представляет ситуацию полного согласия: мужчины сходятся во мнениях относительно порядка женщин, а женщины — относительно порядка мужчин.
В такой ситуации существует уникальное устойчивое паросочетание, состоящее из пар (m, w) и (m’, w’). Другое идеальное паросочетание, состоящее из пар (m’, w) и (m, w’), не является устойчивым, потому что пара (m, w) образует неустойчивость по отношению к этому паросочетанию. (Как m, так и w предпочли бы бросить своих партнеров и образовать новую пару.)
В следующем примере ситуация немного усложняется. Предположим, действу- ют следующие предпочтения:
- m предпочитает w женщине w’;
- m’ предпочитает w’ женщине w;
- w предпочитает m’ мужчине m;
- w’ предпочитает m мужчине m’.
Что же происходит на этот раз? Предпочтения двух мужчин противоположны (они ставят на первое место разных женщин); то же самое можно сказать и о пред- почтениях двух женщин. Однако предпочтения мужчин полностью противоречат предпочтениям женщин.
Однако паросочетание из пар (m’, w) и (m, w’ ) тоже устойчиво, так как обе женщины довольны, насколько это возможно. Запомните этот важный момент, прежде чем двигаться дальше, — в заданной ситуации может существовать более одного устойчивого паросочетания.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу