Изменения
→Доказательство корректности
{{Определение
|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'') — [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| паросочетание]] без неустойчивых пар.
Рассмотрим некоторое [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях| паросочетание]]
в МЖ.
== Алгоритм Гейла-Шепли ==
=== Описание в псевдокоде ===
Время работы алгоритма {{---}} <tex>O(n^2)</tex>, так как количество итераций цикла <tex>\mathrm {while}</tex> не превосходит <tex>O(n^2)</tex>, где <tex>n</tex> равно размеру каждого из данных множеств.
|proof=
Предположим <tex>\langle A, b\rangle</tex> (где <tex>A</tex>, <tex>B</tex> — мужчины; <tex>a</tex>, <tex>b</tex> — женщины; <tex>A</tex> женат на <tex>a</tex>, <tex>B</tex> женат на <tex>b</tex>) — нестабильная пара в паросочетании, найденном алгоритмом Гейла-Шепли. Возможны два случая:
# <tex>A</tex> не делал предложения предложение <tex>b</tex>. Значит, <tex>A</tex> находит <tex>a</tex> более привлекательной, чем <tex>b</tex>. Но чтобы рассматриваемая пара была неустойчивой, необходимо, чтобы <tex>b</tex> для <tex>A</tex> была более привлекательна, чем <tex>a</tex>. Следовательно, <tex>\langle A, b\rangle</tex> — устойчивая пара.
# <tex>A</tex> делал предложение <tex>b</tex>. Тогда был такой момент, когда <tex>b</tex> отказала <tex>A</tex>, значит, <tex>b</tex> находит <tex>B</tex> более привлекательным, чем <tex>A</tex>. Снова получается, что <tex>\langle A, b\rangle</tex> — устойчивая пара.
