Задача о больницах и резидентах: различия между версиями

Обозначим за A множество допустимых пар в <math>I</math>, L = |A|. ''Назначение'' M является подмножеством A. Если <math>(r_i, h_j) \in M</math>, то говорят, что резидент <math>r_i</math> ''назначен'' больнице <math>h_j</math>, а больница <math>h_j</math> – резиденту <math>r_i</math>. Для каждого <math>q \in R \cup H</math> множество назначенных q в M обозначается M(q). Если <math>r_i \in R</math> и <math>M(r_i) = \empty</math>, то считается, что <math>r_i</math> ''не назначен'', в противном случае <math>r_i</math> назначен. Аналогично, любая больница <math>h_j \in H</math> является ''недоукомплектованной'', ''полной'' или ''переукомплектованной'', если <math>|M(h_j)|</math> меньше, равна или больше <math>c_j</math>, соответственно.

''Паросочетанием'' M называется назначение, такое, что <math>|M(r_i)| \le 1</math> для каждого <math>r_i \in R</math> и <math>|M(h_j)| \le c_j</math> для каждого <math>h_j \in H</math> (т. е. ни один резидент не назначен в неподходящую больницу, каждый резидент назначен не более чем в одну больницу и ни одна больница не переукомплектована). Для удобства обозначений, если даны паросочетание M и резидент <math>r_i \in R</math> такой, что <math>M(r_i) \ne \empty</math>, то в случаях, когда это не вызывает двусмысленности, обозначение <math>M(r_i)</math> также используется для обозначения единственного члена <math>M(r_i)</math>.