Изменения

Предположим <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> — устойчивая пара