47
правок
Изменения
→Основная задача
Очевидным образом по такому определению строится полный двудольный граф (левая доля — мужчины, правая — женщины), назовем его МЖ.
Рассмотрим некоторое [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE_%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%BC_%D0%BF%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B8_%D0%B8_%D0%B4%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D1%8F%D1%8E%D1%89%D0%B8%D1%85_%D1%86%D0%B5%D0%BF%D1%8F%D1%85#matching_def паросочетание] в МЖ. Пара A — -b называется неустойчивой (unstable pair), если:# В паросочетании есть пары A — -a и B — -b (A женат на a, B женат на b)
# A считает b привлекательней, чем a
# b считает A привлекательней, чем B
