Алгоритм Гопкрофта-Карпа

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм Гопкрофта-Карпа предназначен для решения задачи о назначениях в случае единичных цен. По заданному двудольному графу алгоритм находит максимальное паросочетание за время $O(m \sqrt{n})$.

1.2 Математическое описание алгоритма

Граф $G = (V, E)$ называется двудольным, если его вершины можно разделить на две части $V = X \sqcup Y$, так что каждое ребро $e \in E$ соединяет вершины из $X$ и $Y$. Набор рёбер $M \subseteq E$ называется паросочетанием, если каждая вершина $v \in V$ принадлежит не более чем одному ребру из $M$. Требуется найти максимальное паросочетание – паросочетание с максимально возможным числом рёбер.

Вершина $v \in V$ называется свободной, если она не принадлежит ни одному ребру из $M$. Простой путь

$P: e_1 = (v_1, v_2), e_2 = (v_2, v_3), \ldots, e_{2k-1} = (v_{2k-1}, v_{2k})$

называется увеличивающей цепью, если его концы $v_1$ и $v_{2k}$ – свободные вершины, а каждое второе ребро принадлежит текущему паросочетанию:

$e_2, e_4, \ldots, e_{2k-2} \in M.$

Паросочетание $M$ является максимальным, если для него не существует увеличивающей цепи.

Множество $M'$, полученное заменой в $M$ рёбер $e_2, e_4, \ldots, e_{2k-2}$ на рёбра $e_1, e_3, \ldots, e_{2k-1}$, является паросочетанием и содержит на одно ребро больше, чем $M$. Множество $M' = M \mathop{\Delta} P$, где $\mathop{\Delta}$ обозначает операцию симметрической разности множеств.

На каждом шаге алгоритма Гопкрофта-Карпа строится максимальное по включению множество кратчайших увеличивающих цепей $\{ P_1, \ldots, P_q \}$, не пересекающихся по вершинам, и текущее паросочетание $M$ заменяется на $M = M \mathop{\Delta} P_1 \mathop{\Delta} P_2 \mathop{\Delta} \dots \mathop{\Delta} P_q$. Гарантируется, что число шагов не превышает $2 (\sqrt{\mu} + 1) = O(\sqrt{n})$, где $\mu$ – число рёбер максимального паросочетания.

Для поиска максимального множества кратчайших увеличивающих цепей применяется поиск в ширину с последующим поиском в глубину.

1.3 Вычислительное ядро алгоритма

Основная вычислительная сложность алгоритма приходится на операции поиска в ширину и поиска в глубину.

1.4 Макроструктура алгоритма

1. Выбрать начальное паросочетание $M_0$ (например, $M_0 = \emptyset$ или паросочетание, полученное жадным алгоритмом).
2. Вычислить максимальное по включение множество кратчайших увеличивающих цепей $\{ P_1, \ldots, P_q \}$, не пересекающихся по вершинам. Если улучшающих цепей не существует, остановиться: текущее паросочетание $M_i$ является максимальным.
3. Составить новое паросочетание $M_{i + 1} = M_i \mathop{\Delta} P_1 \mathop{\Delta} P_2 \mathop{\Delta} \dots \mathop{\Delta} P_q$ и перейти к шагу 2.

1.5 Схема реализации последовательного алгоритма

Опишем, каким образом ищется максимальное множество кратчайших увеличивающих цепей на втором шаге алгоритма.

Пусть $G = (V, E)$ – двудольный граф с разбиением вершин $V = X \sqcup Y$, а $M$ – текущее паросочетание в нём. Обозначим через $X_f \subseteq X$ и $Y_f \subseteq Y$ соответствующие множества свободных вершин.

1. Если одно из множеств $X_f$ или $Y_f$ пусто, то увеличивающих цепей не существует.
2. Ориентируем рёбра $G$ следующим образом:
   • рёбра из $M$ идут из $X$ в $Y$;
   • все остальные рёбра идут из $Y$ в $X$.
3. Выполним один поиск в ширину на полученном ориентированном графе, двигаясь от множества вершин $X_f$ в обратном направлении.
   • Поиск останавливается на том шаге, на котором будет посещена хотя бы одна из вершин в $Y_f$.
   • Если поиск будет завершён без посещения одной из вершин $Y_f$, то увеличивающих цепей не существует.
   • Пометим вершины и рёбра, посещённые в ходе поиска в ширину.
4. Для каждой из свободных вершин $y \in Y_f$ выполним поиск в глубину в прямом направлении, двигаясь только по помеченным рёбрам и вершинам.
   • Снимем пометку с посещённых рёбер и вершин.
   • Если на очередном шаге посещена вершина $x \in X_f$, то поиск останавливается, а текущее содержимое стека определяет кратчайшую увеличивающую цепь от $y$ к $x$.
   • Если поиск в глубину завершается без посещения множества $X_f$, то для данной вершины $y$ увеличивающей цепи не существует, и необходимо перейти к следующей свободной вершине.

1.6 Последовательная сложность алгоритма

Алгоритм выполняет не более $O(\sqrt{n})$ шагов, на каждом из которых производятся поиск в ширину и поиск в глубину сложностью $O(m)$. Таким образом, общая сложность составляет $O(m \sqrt{n})$.