18
правок
Изменения
→Обобщения задачи: опечатка
Случай же, когда у нас есть <tex>N</tex> мужчин и <tex>M</tex> женщин (<tex>N \neq M</tex>) легко сводится к описанной выше задаче. Рассмотрим <tex>M > N</tex> (<tex>M < N</tex> аналогично). Добавим <tex>M - N</tex> фиктивных мужчин, которые являются ''наименее привлекательными'' с точки зрения каждой из женщин. Тогда если в найденном алгоритмом Гейла-Шепли паросочетании некоторая женщина будет замужем за таким фиктивным мужчиной, это будет де-факто означать, что она осталась не замужем.
Также интересна задача о выборе учебного заведения: вместо множества мужчин введем множество университетов, а вместо множества женщин — множество кандидатов, подающих заявления на поступление. Причем в каждом университете есть квота на количество студентов, которое университет может принять. Задача очевидно сводится к основной добавлением <tex>(K-1)</tex> "филиалов" для каждого университета (<tex>K</tex> — квота). И добавлением фиктивного увниерситета университета (поступление в который означает, что кандидату придется попробовать поступить через год).
== Применения в реальной жизни ==
