Формулировка (теорема Холла). Пусть $G=(X,Y,E)$ — двудольный граф. Обозначим для множества $S\subseteq X$ его соседство в $Y$ как $N(S)=\{y\in Y:\exists x\in S,(x,y)\in E\}$. Тогда в $G$ существует паросочетание, насыщающее все вершины $X$ (т.е. такое, что каждая вершина из $X$ инцидентна некоторому ребру паросочетания) тогда и только тогда, когда
$$\forall S\subseteq X|N(S)|\ge |S|.$$ В частном случае $|X|=|Y|$ это условие эквивалентно существованию совершенного паросочетания (покрывающего все вершины).
Доказательство.
1) Необходимость. Если есть паросочетание, насыщающее $X$, то для любого $S\subseteq X$ ребра паросочетания инцидентны различным вершинам $N(S)$, поэтому $|N(S)|\ge |S|$.
2) Достаточность (индукция по $|X|$). Для $|X|=0$ тривиально. Пусть утверждение верно для всех меньших размеров, и пусть для текущего графа выполнено $\forall S\subseteq X|N(S)|\ge |S|$. Возьмём произвольный $x\in X$ и любой $y\in N(\{x\})$. Рассмотрим граф $G^{\prime }$, полученный удалением вершин $x$ и $y$. Если в $G^{\prime }$ условие Холла для множества $X\setminus \{x\}$ выполняется, то по индукции существует паросочетание в $G^{\prime }$, насыщающее $X\setminus \{x\}$, и добавление ребра $(x,y)$ даёт требуемое паросочетание в $G$.
Пусть же в $G^{\prime }$ существует некоторое $S\subseteq X\setminus \{x\}$ с $|N_{G^{\prime }}(S)|<|S|$. Тогда в исходном графе соседство этого $S$ могло увеличиться не более на добавленную вершину $y$, т.е.
$$|N_G(S\cup \{x\})|\le |N_{G^{\prime }}(S)|+1<|S|+1=|S\cup \{x\}|,$$ что противоречит условию Холла для множества $S\cup \{x\}$. Следовательно, такой $S$ не существует, и по индукции паросочетание есть. Тем самым доказано достаточное условие.
Алгоритм для больших двудольных графов (наивысшая производительность). Для задачи ненаправленного максимального (необязательно совершенного) паросочетания в двудольных графах стандартный быстрый алгоритм — Hopcroft–Karp.
Краткая идея алгоритма Hopcroft–Karp:
- Поддерживаем текущее паросочетание $M$.
- Пока существуют увеличивающие (alternating) пути, выполняем фазу:
1. BFS от всех несвязанных вершин левой доли $X$ по ориентированному графу чередующихся рёбер (неиспользуемые ребра слева→справа, используемые ребра справа→слева), строим уровневую структуру и находим длину кратчайших увеличивающих путей.
2. DFS по уровневому графу находит (и добавляет в $M$) максимально возможное множество попарно вершин-непересекающихся кратчайших увеличивающих путей.
- Повторяем, пока BFS находит путь до свободной вершины правой доли.
Сложность и обоснование:
- Пусть $n=|X|+|Y|$, $m=|E|$. Одна фаза (BFS+серия DFS) выполняется за $O(m)$ при хранении списков смежности.
- Количество фаз ограничено $O(\sqrt{n})$ (стандартный аргумент: либо длина кратчайшего увеличивающего пути быстро растёт, либо за короткие пути увеличивается размер соответствующего набора пар и в сумме число фаз не превосходит $O(\sqrt{n})$).
- Значит общая сложность алгоритма
$$O(\sqrt{n}m).$$ Практически для двудольных графов это лучший известный алгоритм по асимптотике для неконструированных (unweighted) задач. Альтернативы: редуцировать задачу к потоку и использовать Dinic/Push–Relabel; для полной двудолицы со взвешиванием применяют венгерский алгоритм ($O(n^3)$ для полных графов).
Применение к распределению студентов по проектам.
Сформулируем модель:
- Левые вершины $X$ — студенты, $|X|=n_s$.
- Правые вершины $Y$ — проекты, $|Y|=n_p$.
- Ребро $(s,p)\in E$ если студент $s$ допустим или заинтересован в проекте $p$.
Случай A (каждый проект — не более одного студента): это стандартное паросочетание; запускаем Hopcroft–Karp с асимптотикой
$$O\left(\sqrt{n}m\right),n=n_s+n_p,m=|E|.$$ Практические замечания: для $n_s$ порядка $10^5$ и $m$ порядка $10^6$ алгоритм укладывается в память при использовании компактных списков смежности и работает быстро.
Случай B (проекты имеют ёмкости $c_p\ge 1$): редуцируем к потоку:
- Строим сеть: источник $\to$ каждый студент (cap $1$), студент→проект (cap $1$), проект→сток (cap $c_p$). Тогда максимум потока даёт оптимальное распределение.
- Для решения используем Dinic или оптимизированный Push–Relabel; практическая сложность выше, но для разреженных графов масштабируемо. Если все $c_p$ малы, можно также «размножить» вершины проектов в $c_p$ копий и применить Hopcroft–Karp (эффективно при суммарном числе копий не очень большом).
Ограничения и практические проблемы:
- Память: хранение $m$ рёбер требует $O(m)$ памяти — критично при $m$ десятки/сотни миллионов.
- Критические случаи: очень высокий максимум степени (горячие проекты) влияет на баланс и кэш-производительность.
- Дополнительные ограничения (приоритеты студентов, нижние квоты проектов, взаимные предпочтения, стабильность) требуют иных формулировок: стабильное распределение — алгоритм Гейла–Шепли, нижние/верхние квоты — потоки с нижними ограничениями, оптимизация по весам — задача назначений (венгер) или min-cost-flow.
- Для динамических или распределённых задач возможны эвристики/приближённые алгоритмы (жадный, многократный локальный поиск) и параллельные реализации Hopcroft–Karp / Dinic.
Рекомендации на практике:
- Если каждый проект — одно место: использовать Hopcroft–Karp (реализация с adjacency lists).
- Если проекты имеют большой/разный capacity: построить сеть и запускать Dinic/Push–Relabel; при малых суммарных ёмкостях — клонить вершины и Hopcroft–Karp.
- Для очень больших и динамиčnih систем — предварительный жадный подбор + последующая оптимизация Hopcroft–Karp/Dinic, и/или распределённые/параллельные реализации.
Если хотите, могу дать компактный псевдокод Hopcroft–Karp и/или схему преобразования с ёмкостями для конкретных чисел $n_s,n_p,m$.