19
правок
Изменения
→Основная задача
Очевидным образом по такому определению строится полный двудольный граф (левая доля - мужчины, правая - женщины), назовем его МЖ.
Рассмотрим некоторое паросочетание в МЖ. Пара Ab A-b называется неустойчивой, если:# В паросочетании есть пары Aa A-a и Bb B-b (A женат на a, B женат на b)
# A считает b привлекательней, чем a
# b считает A привлекательней, чем B
