693
правки
Изменения
→Анализ полученного алгоритмом паросочетания
Из всех возможных решений алгоритмом Гейла-Шепли будет найдено решение, наилучшее для мужчин (каждый мужчина получает в жены женщину, наилучшую из всех возможных при условии корректности решения).
|proof=
Если женщина <tex>a</tex> вычёркивается из списка предпочтений мужчины <tex>A</tex>, то ни одно устойчивое паросочетание не будет содержать пары <tex>\langle A, a\rangle</tex>.
}}
Пусть <tex>A</tex>, <tex>B</tex> — мужчины; <tex>c</tex>, <tex>d</tex> — женщины; <tex>A</tex> женат на <tex>d</tex>, <tex>B</tex> женат на <tex>c</tex>.
Предположим, <tex>\langle A, c\rangle</tex> — стабильная пара в паросочетании <tex>S'</tex>, найденном алгоритмом Гейла-Шепли, но <tex>A</tex> не самый худший выбор для <tex>c</tex>. Тогда существует стабильная пара в паросочетании <tex>S</tex>, в которой <tex>c</tex> замужем за <tex>B</tex>, который менее привлекателен, чем <tex>A</tex>. Тогда пусть мужем <tex>d</tex> будет <tex>A</tex> в паросочетании <tex>S</tex>. Получается <tex>A</tex> считает <tex>c</tex> более привлекательной, чем <tex>d</tex>. Соответственно <tex>\langle A, c\rangle</tex> {{---}} нестабильная пара в паросочетании <tex>S</tex>.
}}
