693
правки
Изменения
→Доказательство корректности
Все мужчины и женщины будут заняты.
|proof=
Предположим, что некоторый мужчина, Ян, (<tex>A</tex>) не женат по завершении алгоритма. Тогда некоторая женщина, Антонина (<tex>a</tex>) не замужем. По [[#observation2|наблюдению 2]], Антонине никто <tex>a</tex> не делал предложенияполучала предложений. Но Ян <tex>A</tex> сделал предложения всем женщинам, т.к. он остался не женат. Получаем противоречие. Таким образом, все мужчины заняты. Аналогичные утверждения можно повторить и отталкиваясь от тогорассуждения применяем для женщин. Пусть какая-то женщина не замужем. Значит, что есть мужчина, который остался не занята некоторая девушкаженат. Но мы доказали, поэтому предложение доказаночто по завершении алгоритма все мужчины заняты. Снова пришли к противоречию.
}}
После завершения алгоритма не будет неустойчивых пар.
|proof=
Предположим <tex>A</tex>-<tex>b</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> \Rightarrow</tex> <tex>A</tex> находит <tex>a</tex> ''более привлекательной'', чем <tex>b</tex> <tex> \Rightarrow</tex> <tex>A</tex>-<tex>b</tex> — устойчивая пара
# <tex>A</tex> делал предложения <tex>b</tex> <tex> \Rightarrow</tex> <tex>b</tex> отказала <tex>A</tex> (сразу или на одной из последующих итераций) <tex> \Rightarrow</tex> <tex>b</tex> находит <tex>B</tex> ''более привлекательным'', чем <tex>A</tex> <tex> \Rightarrow</tex> <tex>A</tex>-<tex>b</tex> — устойчивая пара
