47
правок
Изменения
→Обобщения задачи
== Обобщения задачи ==
Интересно, что данная задача не всегда имеет решение, если допустить однополые пары (устойчивого паросочетания может не быть). (см. [[https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%81%D0%BE%D1%81%D0%B5%D0%B4%D1%8F%D1%85_%D0%BF%D0%BE_%D0%BA%D0%BE%D0%BC%D0%BD%D0%B0%D1%82%D0%B5|Задача_о_соседях_по_комнате Задача о соседях по комнате]])
Случай же, когда у нас есть <tex>N</tex> мужчин и <tex>M</tex> женщин (<tex>N \neq M</tex>) легко сводится к описанной выше задаче. Рассмотрим <tex>M > N</tex> (<tex>M < N</tex> аналогично). Добавим <tex>M - N</tex> фиктивных мужчин, которые являются наименее привлекательными с точки зрения каждой из женщин. Тогда если в найденном алгоритмом Гейла-Шепли паросочетании некоторая женщина будет замужем за таким фиктивным мужчиной, это будет де-факто означать, что она осталась не замужем.
