Алгоритм Куна: как найти максимальное паросочетание

Алгоритм Куна - простой и наглядный способ найти максимальное паросочетание в двудольном графе за $O(V \cdot E)$. Назван в честь Гарольда Куна, который в 1955 году описал его идею в той же статье, где предложил венгерский алгоритм для взвешенной задачи о назначении. В невзвешенной постановке достаточно куновского ядра: повторяющийся поиск увеличивающих цепей (augmenting paths) обычным DFS из каждой непокрытой вершины. Алгоритм решает классическую задачу - распределить работников по работам, студентов по проектам, поезда по платформам - когда у каждой пары «можно/нельзя» и хочется покрыть как можно больше пар одновременно.

Что такое двудольное паросочетание

Граф $G = (V, E)$ двудольный, если его вершины разбиты на две доли $L$ и $R$ так, что любое ребро соединяет вершину из $L$ с вершиной из $R$. Внутри одной доли рёбер нет. Это естественная модель для отношений «между двумя множествами»: работники–работы, абитуриенты–вузы, заявки–слоты.

Паросочетание $M \subseteq E$ - это набор рёбер без общей вершины. Каждая вершина либо покрыта ровно одним ребром из $M$, либо свободна. Максимальное паросочетание - наибольшее по размеру среди всех возможных. Совершенное (perfect) - то, в котором покрыты вообще все вершины; существует не всегда. Кун находит максимальное; будет ли оно совершенным - видно по сравнению размера ответа с $\min(|L|, |R|)$.

Augmenting path - главная идея

Ключевое понятие - увеличивающая (alternating) цепь. Это путь в графе, который:

1. Начинается в непокрытой вершине левой доли $u \in L$.
2. Чередует рёбра: сначала рёбро не из $M$, затем из $M$, затем не из $M$, и так далее.
3. Заканчивается в непокрытой вершине правой доли $v \in R$.

По такой цепи легко увеличить паросочетание на 1: «инвертировать» её - рёбра из $M$ удалить, рёбра не из $M$ добавить. Внутренние вершины остаются покрыты ровно одним ребром, а свободные концы $u$ и $v$ становятся покрытыми. Размер $M$ растёт на единицу.

Теорема Бержа (1957) - фундамент алгоритма: паросочетание $M$ максимально тогда и только тогда, когда в графе нет увеличивающих цепей относительно $M$. Отсюда прямой план: стартовать с пустого $M$, искать увеличивающие цепи и инвертировать их, пока цепи находятся.

Псевдокод

В двудольном графе поиск увеличивающей цепи устроен особенно просто: достаточно DFS из непокрытой вершины $u \in L$. Алгоритм поддерживает массив $\text{match}[v]$ - какая вершина из $L$ сейчас спарена с $v \in R$ (или $-1$, если свободна).

function try_kuhn(u):
    для каждой v ∈ adj[u]:
        если used[v]: continue
        used[v] = true
        если match[v] == -1 или try_kuhn(match[v]):
            match[v] = u
            return true
    return false

function kuhn(L, R, adj):
    match[v] = -1 для всех v ∈ R
    answer = 0
    для каждой u ∈ L:
        used[v] = false для всех v ∈ R
        если try_kuhn(u):
            answer += 1
    return answer

Что делает рекурсивный вызов try_kuhn(u). Из $u$ перебираем соседей $v$ в правой доле. Если $v$ свободна - спарили $u$ с $v$ и вернули true. Если $v$ занята какой-то $u'$ - пытаемся «перевесить» $u'$ на другую вершину рекурсивным try_kuhn(u'). Если получилось - освободившаяся $v$ достаётся $u$. Если не получилось - пробуем следующего соседа $u$.

DFS из $u$ - это и есть поиск увеличивающей цепи, начинающейся в $u$. Массив used[] защищает от повторного посещения вершины в одном DFS и обнуляется перед каждой попыткой расширить паросочетание.

Сложность

Внешний цикл по $u \in L$ запускает DFS не более $|L|$ раз. Каждый DFS просматривает каждое ребро не более одного раза (за счёт used), то есть его стоимость $O(E)$. Итого:

$T_{\text{Кун}} = O(V \cdot E).$

Эта оценка груба, но без специальных ухищрений плохо улучшаема в общем случае. На практике алгоритм Куна часто работает заметно быстрее - особенно если паросочетание небольшое: тогда DFS быстро завершается, не успев пройти все рёбра.

Память - $O(V + E)$ на список смежности плюс массивы $\text{match}$ и $\text{used}$.

Подробный пример

Пять работников $L = \{A, B, C, D, E\}$ и пять задач $R = \{1, 2, 3, 4, 5\}$. Рёбра - «работник умеет выполнить задачу»:

A - 1, 2
B - 1, 3
C - 2, 3
D - 4
E - 3, 4, 5

Шаг 1. DFS из $A$: $1$ свободна → $\text{match}[1] = A$. Шаг 2. Из $B$: $1$ занята $A$, но $A$ умеет ещё $2$ - перевешиваем. Цепь $B \to 1 \to A \to 2$. $\text{match}[1] = B, \text{match}[2] = A$. Шаг 3. Из $C$: $2$ занята $A$, перевес $A$ не выходит. $3$ свободна → $\text{match}[3] = C$. Шаг 4. Из $D$: $4$ свободна → $\text{match}[4] = D$. Шаг 5. Из $E$: $3$ и $4$ заняты, цепи перевеса не находятся, но $5$ свободна → $\text{match}[5] = E$.

Итог: совершенное паросочетание $\{A{-}2, B{-}1, C{-}3, D{-}4, E{-}5\}$. Без ребра $E{-}5$ алгоритм остановился бы на размере 4, и теорема Бержа гарантировала бы максимальность.

Связь с теоремой Кёнига

Минимальное вершинное покрытие $C$ - набор вершин такой, что каждое ребро инцидентно хотя бы одной вершине из $C$.

Теорема Кёнига (1931): в двудольном графе

$|M_{\max}| = |C_{\min}|.$

Это редкий случай, когда задача о покрытии (NP-трудная в общих графах) становится полиномиальной: прогон Куна даёт и паросочетание, и явное минимальное покрытие. Конструктивно: пусть $U$ - непокрытые вершины $L$. Из $U$ обходим по нерёбрам $M$ вправо, из $R$ - по рёбрам $M$ влево, помечаем посещённые. Тогда $C = (L \setminus \text{посещённые}) \cup (R \cap \text{посещённые})$.

Двойственно - теорема Холла: совершенное паросочетание из $L$ в $R$ существует тогда и только тогда, когда для любого $S \subseteq L$ выполнено $|N(S)| \ge |S|$.

Применения

• Задача о назначении. Распределить $n$ работников по $n$ работам так, чтобы каждый получил подходящую задачу. Если важны только «может/не может» - алгоритм Куна. Если у каждой пары есть числовая стоимость и нужно минимизировать суммарную - нужен венгерский алгоритм ($O(V^3)$), который в этой же статье Куна и был предложен.
• Расписание. Аудитории на лекции, поезда на платформы, врачи на смены. Двудольная модель: одна доля - слоты, другая - события; ребро - «событие можно поставить в этот слот».
• Распределение ресурсов. Серверы на запросы, лицензии на пользователей, грузовики на маршруты.
• Доказательства существования. Многие комбинаторные утверждения - теорема Дилворта, формулы для перманентов 0/1-матриц, разложения латинских квадратов - сводятся к существованию совершенного паросочетания и поэтому проверяются Куном.

Сравнение с венгерским алгоритмом и Хопкрофтом-Карпом

• Кун - максимальное паросочетание в невзвешенном двудольном графе, $O(V \cdot E)$. Простой код в 20 строк.
• Венгерский алгоритм (Kuhn, 1955; Munkres, 1957) - минимальное по сумме весов совершенное паросочетание во взвешенном двудольном графе, $O(V^3)$. Использует двойственные переменные и «эквивалентную матрицу».
• Хопкрофт-Карп (1973) - то же, что Кун, но за $O(E\sqrt{V})$. Вместо одной увеличивающей цепи за раз BFS-уровнями находит множество вершинно-непересекающихся кратчайших цепей и инвертирует их разом. На разреженных графах $O(V\sqrt{V})$ против $O(V^2)$.

Для учебных задач и графов до пары тысяч вершин Кун достаточен. Для серьёзных размеров - Хопкрофт-Карп. Для взвешенной задачи о назначении - венгерский, и никакой Кун его не заменит.

Частые ошибки

• Применяют Куна к не-двудольному графу. В общем графе понятие увеличивающей цепи сложнее (blossom-стяжки, алгоритм Эдмондса 1965 года), и обычный DFS работает неверно. Кун - только для двудольных.
• Забывают обнулять used перед каждым внешним вызовом. used защищает от циклов внутри одного DFS; между DFS-ами его обязательно сбрасывать, иначе помеченные прошлой попыткой вершины остаются недоступны.
• Считают, что Кун даёт минимум по весу. Он не учитывает веса вообще. Если они есть и важны - это венгерский, не Кун.
• Путают «максимальное» и «совершенное» паросочетание. Кун возвращает максимальное; совершенно оно или нет - зависит от графа. После прогона сравните размер с $|L|$ или $|R|$.

FAQ

Чем алгоритм Куна отличается от венгерского? Кун решает невзвешенную задачу - найти как можно больше совместимых пар. $O(V \cdot E)$, код в 20 строк. Венгерский алгоритм минимизирует сумму стоимостей при покрытии каждой вершины, $O(V^3)$. Куна нельзя «приспособить» к весам - нужен венгерский.

Что такое увеличивающая цепь простыми словами? Путь, который начинается и заканчивается в свободных вершинах разных долей и чередует рёбра «вне $M$ / внутри $M$». Если поменять «вне» и «внутри» местами, паросочетание вырастет на единицу. Кун ищет такие цепи, пока находит.

Когда применять Хопкрофта-Карпа вместо Куна? Когда $V$ и $E$ велики (десятки тысяч и больше). Хопкрофт-Карп - $O(E\sqrt{V})$, на разреженных графах $O(V\sqrt{V})$ против $O(V^2)$ у Куна. На маленьких задачах Кун обычно быстрее из-за меньшей константы.

Коротко

Алгоритм Куна находит максимальное паросочетание в двудольном графе за $O(V \cdot E)$. Идея - теорема Бержа: пока существует увеличивающая чередующаяся цепь из свободной вершины $L$ в свободную вершину $R$, паросочетание можно увеличить инверсией её рёбер. Кун ищет такие цепи обычным DFS из каждой непокрытой вершины слева, поддерживая массив match пар правой доли. Через теорему Кёнига алгоритм заодно даёт минимальное вершинное покрытие. Для взвешенной задачи о назначении нужен венгерский алгоритм ($O(V^3)$), для больших невзвешенных графов - Хопкрофт-Карп ($O(E\sqrt{V})$). Кун - простой, наглядный и достаточный в большинстве учебных и средних задач.