693
правки
Изменения
Нет описания правки
{{Задача
|definition=
Найти полное устойчивое паросочетание между элементами двух множеств размера <tex>n</tex>, имеющими свои предпочтения.}}
{{Определение
|definition =
Пара <tex>\langle A, b\rangle</tex> называется '''неустойчивой''' (англ. ''unstable pair''), если:
# В паросочетании есть пары <tex>\langle A, a\rangle</tex> и <tex>\langle B, b\rangle</tex> (<tex>A</tex> женат на <tex>a</tex>, <tex>B</tex> женат на <tex>b</tex>);
# <tex>A</tex> предпочитает <tex>b</tex> элементу <tex>a</tex>;
# <tex>b</tex> предпочитает <tex>A</tex> элементу <tex>B</tex>.
}}
{{Определение
|definition='''Устойчивое паросочетание''' (англ. ''stable matching'') — [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| паросочетание]] без неустойчивых пар.
}}
== Основная задача ==
Рассмотрим некоторое [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| паросочетание]]
в МЖ.
== Алгоритм Гейла-Шепли ==
