Теория графов находит применение в самых разных сферах человеческой жизни — от алгоритмов работы сервисов онлайн-знакомств до распределения вычислительных задач по серверам. В лекции Массачусетского технологического института (MIT) преподаватель Закари Абель подробно разбирает концепцию паросочетаний, уделяя особое внимание задаче о стабильном распределении и знаменитому алгоритму Гейла — Шепли. Этот математический подход не только описывает абстрактные структуры, но и активно применяется на практике, например, при ежегодном распределении выпускников медицинских вузов США по интернатурам.
🔗 Что такое паросочетания и где они применяются 0:12
Паросочетания (matchings) представляют собой один из наиболее фундаментальных и полезных инструментов в теории графов. Их основная задача заключается в том, чтобы связать объекты парами, гарантируя, что у каждого объекта будет ровно один партнер или не будет вовсе.
Формально в теории графов паросочетание определяется двумя эквивалентными способами:
- Паросочетание — это такой подграф $M$ исходного графа, в котором степень каждой вершины в $M$ не превышает 1.
- Паросочетание — это подмножество ребер графа, в котором никакие два выбранных ребра не имеют общих концевых вершин (эндпоинтов).
Для иллюстрации лектор приводит пример графа в форме галстука-бабочки с вершинами от $a$ до $h$. Если выбрать в нем ребра $be$ и $dg$, это будет корректным паросочетанием, поскольку они не пересекаются в вершинах. Однако попытка добавить к ним ребро $fd$ нарушит структуру: ребра $dg$ и $fd$ разделяют общую вершину $d$, что увеличит ее степень до 2, а это недопустимо.
[Image of a matching in a graph]
Локальное против глобального: максимальные и наибольшие паросочетания
В задачах оптимизации критически важно различать два похожих по звучанию, но принципиально разных понятия:
- Максимальное паросочетание (maximal matching) — это локальное свойство. Паросочетание называется максимальным, если к нему невозможно добавить ни одного нового ребра из исходного графа без нарушения правил. Найти его чрезвычайно просто: достаточно жадно добавлять случайные подходящие ребра одно за другим, пока этот процесс не зайдет в тупик.
- Наибольшее паросочетание (maximum matching) — это глобальное свойство. Паросочетание считается наибольшим, если во всем графе в принципе не существует другого паросочетания с большим количеством ребер.
Упомянутый пример с ребрами $be$ и $dg$ является максимальным (к нему нельзя ничего добавить), но не наибольшим. Студенты из аудитории предлагают альтернативный вариант из трех ребер: $ad$, $bg$ и $ce$. Данное паросочетание уже является наибольшим. Лектор доказывает это от противного: если бы существовало паросочетание большего размера, оно должно было бы содержать как минимум 4 ребра, то есть задействовать все 8 вершин графа. Но для включения вершин $a$ и $f$ нам пришлось бы провести ребра к центральной вершине $d$, так как это их единственный путь в граф. Использовать вершину $d$ дважды невозможно, что приводит к противоречию. При этом наибольшее паросочетание не обязательно уникально: замена ребра $ad$ на $fd$ даст другое паросочетание того же максимального размера.
Совершенные и двудольные паросочетания
Если паросочетание включает в себя абсолютно все вершины графа, оно называется совершенным (perfect matching). В таком сценарии абсолютно каждый элемент получает ровно одного партнера. Очевидно, что граф «галстук-бабочка» не имеет совершенного паросочетания, так как его максимальный размер ограничен тремя ребрами (шестью вершинами).
На практике паросочетания чаще всего ищут в двудольных графах (bipartite graphs), где вершины разделены на две группы, а ребра соединяют элементы только из разных групп. Примером может служить распределение задач по вычислительным серверам в крупных параллельных проектах, где каждый сервер может выполнять только одну задачу одновременно.
Важно помнить, что доли двудольного графа не обязательно должны быть равны по размеру. Лектор напоминает пример сравнения студентов Гарварда и MIT: 7000 человек против 4000. В таком несбалансированном графе совершенное паросочетание математически невозможно — даже если мы найдем пару каждому студенту MIT, 3000 студентов Гарварда неизбежно останутся без пары. Таким образом, равенство долей является необходимым, хотя и не достаточным условием существования совершенного паросочетания.
Взвешенные паросочетания
Зачастую ребра графа снабжаются весами — числовыми значениями, отражающими реальные параметры, например, время выполнения задачи на конкретном сервере. В таких условиях цель усложняется: требуется найти не просто совершенное паросочетание, а совершенное паросочетание с минимальным суммарным весом.
В демонстрационном двудольном графе лектор рассматривает возможные совершенные паросочетания с весами ребер 3, 1, 5 и 2. Первая комбинация дает суммарный вес $3 + 2 = 5$, а вторая — $1 + 5 = 6$. Естественно, алгоритм оптимизации выберет первый вариант, так как 5 меньше 6. Закари Абель подчеркивает, что для всех этих задач (поиск наибольшего, совершенного и минимально-взвешенного паросочетания в двудольных графах) существуют эффективные алгоритмы, подробное изучение которых вынесено в специализированные курсы 6.121 и 6.122.
⚖️ Проблема стабильности: алгоритм Гейла — Шепли 21:24
Основная тема лекции — стабильные паросочетания (stable matchings). В этой постановке задачи рассматриваются две равные группы объемом $n$ (например, $n$ кандидатов и $n$ работодателей, или $n$ интернов и $n$ менеджеров), которые необходимо распределить один к одному.
Живой классический пример этой модели — распределение выпускников медицинских вузов США по больницам для прохождения резидентуры. Исторически этот процесс автоматизирован: кандидаты ранжируют больницы по своим предпочтениям, больницы делают то же самое на основе собеседований, а специальная национальная некоммерческая организация обрабатывает эти списки и централизованно объявляет результаты в так называемый «День матча» (Match Day).
Математический фундамент этой системы был заложен в 1962 году Дэвидом Гейлом и Ллойдом Шепли. Позже экономист Эл Рот усовершенствовал их подход для реальных рынков, что привело к присуждению Ллойду Шепли и Элу Роту Нобелевской премии по экономике в 2012 году. (Дэвид Гейл к тому моменту, к сожалению, уже скончался и не мог претендовать на награду).
Понятие «нелегальной пары»
Чтобы алгоритм работал, каждый участник с обеих сторон обязан предоставить строго упорядоченный список своих предпочтений без ничьих и пропусков. Если все кандидаты мечтают попасть в одну и ту же престижную больницу, они все могут поставить ее на первое место — никаких ограничений на совпадения списков нет, хотя получит место только один.
Главная цель — найти совершенное паросочетание, которое сделает участников «достаточно счастливыми». В данном контексте это означает отсутствие нелегальных пар (rogue pairs).
Нелегальная пара образуется в том случае, если некий кандидат и некий работодатель не связаны друг с другом в текущем паросочетании, но при этом они оба взаимно предпочитают друг друга своим текущим назначенным партнерам.
Лектор демонстрирует это на простейшем примере с двумя кандидатами ($A, B$) и двумя работодателями ($C, D$). Их предпочтения выглядят следующим образом:
- Кандидат $A$ предпочитает $C$ больше, чем $D$ ($C > D$).
- Кандидат $B$ также предпочитает $C$ больше, чем $D$ ($C > D$).
- Работодатель $C$ предпочитает $A$ больше, чем $B$ ($A > B$).
- Работодатель $D$ также предпочитает $A$ больше, чем $B$ ($A > B$).
Если мы попробуем сформировать пары $AD$ и $BC$, то работодатель $D$ и кандидат $B$ получат свои первые приоритеты и будут довольны. Однако пара $AC$ окажется нелегальной: кандидат $A$ получил своего второго партнера ($D$), но хочет к $C$, а работодатель $C$ получил второго партнера ($B$), но хочет к $A$. В реальной жизни $A$ и $C$ просто «сбегут» друг к другу, разрушив систему. Стабильным же называется такое совершенное паросочетание, в котором подобных нелегальных пар нет вообще. Для этого примера стабильным решением будет распределение $AC$ и $BD$, где топовые участники сразу удовлетворяют свои запросы.
Важность двудольной структуры (Задача о сожителях)
Закари Абель делает важное отступление: стабильное паросочетание гарантированно существует далеко не всегда, если убрать условие двудольности графа. В неколлективной «задаче о сожителях» (roommates problem), где каждый из четырех участников ($A, B, C, D$) ранжирует всех остальных, стабильного решения может не существовать в принципе.
Если предпочтения зациклены по кругу:
- $A$ выбирает $B > C > D$,
- $B$ выбирает $C > A > D$,
- $C$ выбирает $A > B > D$,
- а предпочтения $D$ могут быть любыми,
то любое распределение пар окажется нестабильным из-за симметрии. В каком бы варианте мы ни закрепили $D$ (например, пары $AD$ и $BC$), пара $AC$ неизбежно уйдет в «нелегальное» положение и разрушит стабильность. Тем удивительнее тот факт, что в двудольных графах алгоритм Гейла — Шепли всегда находит решение, доказывая, что стабильное паросочетание там существует абсолютно всегда.
🚶♂️ Пошаговая механика алгоритма 39:13
Сам алгоритм Гейла — Шепли устроен итеративно и циклично. Каждый условный день состоит из двух простых шагов:
- Шаг 1 (Предложение): Все кандидаты (аппликанты) обращаются к своему самому предпочитаемому работодателю (эвалюатору) из тех, кто их еще не отверг.
- Шаг 2 (Отсев): Каждый работодатель рассматривает всех пришедших к нему в этот день кандидатов, временно оставляет у себя одного самого лучшего (согласно своему списку), а всех остальных окончательно отвергает.
Процесс останавливается в тот день, когда ни один кандидат не получает отказа. Если кандидат умудряется получить отказ абсолютно от всех инстанций в своем списке, он выбывает из системы. Поскольку в алгоритме отсутствуют неопределенности и спорные ситуации (благодаря строгим спискам без ничьих), у каждого работодателя всегда есть один явный фаворит среди пришедших.
Разбор демонстрационного примера 4x4
Лектор демонстрирует работу алгоритма на анимированном примере с 4 больницами и 4 врачами:
- День 1: Все врачи отправляются к своим первым приоритетам. К больнице №3 приходят сразу три кандидата. Больница №3 выбирает доктора $D$ как лучшего, а докторов $B$ и $C$ выставляет за дверь.
- День 2: Врачи $A$ and $D$ остаются на своих местах, а отвергнутые $B$ и $C$ двигаются дальше по своим спискам. Так совпадает, что они оба приходят к больнице №2. Та оставляет себе $B$ и прогоняет $C$.
- День 3: Доктор $C$ идет к больнице №1. Рассмотрев кандидатуры, больница №1 понимает, что $C$ нравится ей больше, чем удерживаемый до этого доктор $A$. В итоге $A$ внезапно получает отказ, несмотря на то, что «сидел» там два дня.
- День 4: Доктор $A$ идет к своему следующему по списку приоритету — больнице №3 (это его второй выбор, а не четвертый, ведь его отвергли лишь раз). Но больница №3 снова прогоняет $A$. Затем $A$ идет к больнице №2. Больнице №2 кандидат $A$ нравится больше, чем $B$, поэтому она забирает $A$ и выгоняет $B$. В свою очередь, $B$ идет к больнице №1 (отказ), а затем к больнице №4. На этом цепочка отказов прекращается, и алгоритм успешно завершается.
Ручной расчет примера 5x5
Чтобы закрепить материал, Закари Абель вместе с залом рассчитывает на доске пример с пятью работодателями ($A, B, C, D, E$) и пятью кандидатами ($F, G, H, I, J$). Кандидаты отправляют заявки, а работодатели принимают жесткие решения.
Хроника процесса по дням:
- День 1: $F$ идет к $C$, $G$ к $A$, $H$ к $D$, $I$ к $A$, $J$ к $A$. Работодатель $A$ выбирает среди троих пришедших кандидата $J$, а $G$ и $I$ безжалостно отвергает.
- День 2: Неотвергнутые $J, F, H$ остаются. Кандидат $G$ идет к своему второму выбору — $B$, а $I$ направляется к $C$. Теперь работодатель $C$ выбирает между прежним $F$ и новым $I$. Кандидат $I$ находится значительно выше в списке его предпочтений, поэтому $C$ оставляет $I$ и выгоняет $F$.
- День 3: Единственный отвергнутый кандидат $F$ идет к работодателю $B$. Тот сравнивает его с удерживаемым $G$. Выигрывает $F$, а кандидат $G$ получает расчет.
- День 4: Кандидат $G$ отправляется к работодателю $E$. Тот пустует, поэтому с радостью принимает заявку. Никаких новых конфликтов и отказов не происходит.
В результате формируются финальные стабильные пары: $A-J$, $B-F$, $C-I$, $D-H$, $E-G$.
Отвечая на вопросы студентов, лектор подчеркивает две важные детали: внутренний порядок рассмотрения кандидатов внутри одного дня никак не влияет на результат, однако если поменять роли сторон местами (чтобы первыми предлагали работодатели), итоговое стабильное паросочетание почти наверняка окажется совершенно другим.
⚙️ Математический анализ: завершаемость и инварианты 52:45
Для строгого доказательства корректности лектор предлагает представить алгоритм Гейла — Шепли в виде абстрактного автомата состояний (state machine).
В этой модели:
- Состояние определяется множеством всех отказов, случившихся на текущий момент (то есть вычеркнутыми позициями в списках участников).
- Переход из одного состояния в другое эквивалентен проживанию одного рабочего дня алгоритма.
Студенты сразу заявляют, что этот автомат гарантированно завершает работу, ссылаясь на лекционные заметки. Закари Абель в шутку пресекает этот аргумент, напоминая, что раз он сам написал эти заметки, то не может использовать их в качестве независимого доказательства. Настоящее обоснование звучит иначе: каждый день в системе происходит как минимум один новый отказ, безвозвратно поглощая доступные ресурсы. Поскольку всего между $n$ кандидатами и $n$ работодателями возможно не более $n^2$ отказов, автомат совершит максимум $n^2$ шагов и неизбежно остановится.
Ключевые инварианты системы
Для анализа поведения автомата формулируются важнейшие инварианты (свойства, остающиеся неизменными в ходе работы):
- Инвариант кандидатов: Каждый кандидат вычеркивает элементы строго с начала своего списка предпочтений (префикса). Это означает, что со временем кандидаты обращаются к более плохим (с их точки зрения) работодателям. Их перспективы только ухудшаются.
- Инвариант работодателей: Положение работодателей со временем только улучшается. Они никогда не согласятся на худшего кандидата по сравнению с тем, кто у них уже есть. Более строгая формулировка инварианта гласит: если работодатель $E$ когда-либо отверг кандидата $A$, то во все последующие дни у $E$ гарантированно будет удерживаться кандидат, который нравится ему строго больше, чем $A$.
Доказательство того, что никто не останется без пары
Используя метод от противного, лектор доказывает, что на момент остановки алгоритм выдает именно совершенное паросочетание, и никто не уходит из системы брошенным.
Допустим, в самом конце некий кандидат (назовем его доктор Джекилл) оказался отвергнут абсолютно всеми работодателями. Согласно второму инварианту, это означает, что каждый из $n$ работодателей закончил алгоритм с кем-то, кто нравится ему больше доктора Джекилла. То есть абсолютно все $n$ работодателей имеют на руках какого-то партнера. Но если сам доктор Джекилл остался без пары, то в системе доступно всего лишь $n-1$ кандидатов для распределения. Физически невозможно распределить $n-1$ человек по $n$ рабочим местам так, чтобы все места были заняты. Мы получили математическое противоречие, а значит, доктор Джекилл и все остальные участники гарантированно найдут себе пару.
🛡️ Доказательство стабильности и справедливости 1:05:43
Финальный и самый красивый этап лекции — доказательство того, что полученное паросочетание действительно является стабильным и не содержит скрытых нелегальных пар.
Для примера лектор берет условного работодателя — Медицинский центр Тафтса (Tufts Medical Center) — и делит всех кандидатов в системе на три изолированные группы относительно него:
- Кандидаты, которых Тафтс отверг в ходе алгоритма (например, доктор Ноу).
- Кандидаты, с которыми Тафтс вообще ни разу не контактировал за все дни (например, доктор Кто).
- Один единственный кандидат, с которым Тафтс остался в финале (например, Хороший Доктор).
Лектор поочередно доказывает, что Тафтс не может образовать нелегальную пару ни с кем из них:
- С Хорошим Доктором: Невозможно по определению, так как они официально состоят в паре, а нелегальная пара — это всегда внешняя связь.
- С доктором Ноу: Поскольку Тафтс когда-то сам отверг доктора Ноу, по инварианту его финальный партнер (Хороший Доктор) нравится ему больше. Раз Тафтс доволен своим выбором больше, чем доктором Ноу, они никак не смогут стать нелегальной парой (для этого нужно взаимное недовольство текущими партнерами).
- С доктором Кто: Раз доктор Кто ни разу не приходил в Тафтс, значит, двигаясь по своему списку сверху вниз, он нашел себе финальную пару где-то выше, до того как дошел до Тафтса. Следовательно, доктор Кто ценит своего текущего партнера выше Тафтса и не станет с ним «сбегать».
Поскольку ни один кандидат из всех групп не способен составить нелегальную пару с Тафтсом, а Тафтс был выбран случайным образом, в итоговом паросочетании нелегальные пары отсутствуют в принципе. Стабильность доказана.
Кому выгоден алгоритм Гейла — Шепли?
В завершение лекции Закари Абель поднимает фундаментальный вопрос справедливости рыночных механизмов: если бы вы сами участвовали в этом процессе, кем бы вы предпочли быть — кандидатом или работодателем? С одной стороны, положение работодателей постоянно улучшается, а кандидатов — ухудшается. С другой — кандидаты начинают с самого верха своих списков и контролируют инициативу.
Для точного ответа вводится понятие допустимых (feasible) партнеров — это те пары, которые теоретически могут быть вместе хотя бы в каком-то одном из множества существующих стабильных паросочетаний для данных списков предпочтений.
Математический анализ приводит к двум поразительным теоремам:
- Оптимальность для кандидатов: Алгоритм Гейла — Шепли распределяет каждого кандидата к его самому предпочитаемому партнеру среди всех допустимых вариантов. Кандидаты получают максимум из того, на что вообще могли рассчитывать в стабильном мире.
- Пессимальность для работодателей: Одновременно с этим алгоритм распределяет каждого работодателя к его самому нелюбимому партнеру среди всех допустимых вариантов.
Лектор признается, что этот факт кажется ему глубоко контринтуитивным. Казалось бы, эгоистичные желания разных кандидатов должны постоянно конфликтовать за лучшие места, однако математика работает так, что оптимальный для кандидатов результат достигается синхронно и безболезненно для них.
Именно поэтому запуск алгоритма в реверсивном режиме (когда первыми предлагают работодатели) полностью переворачивает баланс сил, делая результат идеальным для клиник и худшим из возможных для молодых врачей.
В основе доказательства этого феномена лежит еще один красивый инвариант: если работодатель отвергает кандидата в ходе классического алгоритма, они математически больше никогда не смогут быть вместе ни в одном стабильном паросочетании мира — они принципиально не являются допустимыми партнерами. Более детальный разбор этого сложного доказательства лектор обещает провести на практическом занятии на следующий день.
