Задача об устойчивом бракосочетании. Пусть В — множе¬ство из п юношей, a G — множество из п девушек. Каждый юноша оценивает девушек числами от 1 до n, и каждая девушка оценивает юношей числами от 1 до п. Паросочетанием называется взаимно однозначное соответствие между юношами и девушками. Паросочетание устойчиво, если для любых двух юношей b1 и b2 и соответствующих им в этом паросочетании девушек g1 и g2 выполняются следующие два условия:
1) либо b1 оценивает g1 выше, чем g2, либо g2 оцениваеяет b2 выше,чем b1 ;
2) либо b2 оценивает g2 выше, чем g1, либо g1 оценивает b1 выше, чем  b2 .
Докажите, что устойчивое паросочетание всегда существует, и напишите алгоритм для нахождения одного из таких паросочетаний.


Кто ни будь знает где можно достать описание этой задачи или что  угодно связанное с ней !!!!
Сам просмотрел кучу книг но увы не нашел ничего связочного с этой задачей :(


Это сообщение отредактировал(а) mur88 - 26.3.2008, 01:48

http://en.wikipedia.org/wiki/Stable_marriage_problem