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
