Паросочетания и алгоритм Куна

Паросочетание — набор рёбер графа, попарно не имеющих общих вершин. Вершина, инцидентная ребру набора, называется покрытой, остальные — свободными.

Задача о максимальном паросочетании в двудольном графе решается просто и встречается постоянно — в том числе там, где про паросочетания в условии не сказано ни слова.

Увеличивающий путь

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

На увеличивающем пути рёбер не из $M$ на одно больше, чем рёбер из $M$. Поменяем их местами: получится снова паросочетание, но больше на единицу.

Теорема Бержа. Паросочетание максимально тогда и только тогда, когда увеличивающего пути не существует.

Доказательство обратной стороны — стандартный приём, который стоит запомнить. Пусть $M'$ больше $M$. Рассмотрим симметрическую разность $M \triangle M'$: у каждой вершины в ней не больше двух инцидентных рёбер, по одному из каждого паросочетания, поэтому она распадается на пути и циклы с чередующимися рёбрами. Циклы имеют чётную длину и содержат поровну рёбер обоих паросочетаний. Раз $|M'| > |M|$, найдётся путь, где рёбер $M'$ больше, — а это увеличивающий путь для $M$.

Алгоритм Куна

Ищем увеличивающий путь обходом в глубину из свободной вершины левой доли:

bool tryKuhn(int u) {
    for (int v : adj[u]) {
        if (used[v]) continue;
        used[v] = true;
        if (matchRight[v] == -1 || tryKuhn(matchRight[v])) {
            matchRight[v] = u;
            return true;
        }
    }
    return false;
}

int size = 0;
for (int u = 0; u < n; u++) {
    std::fill(used.begin(), used.end(), false);
    if (tryKuhn(u)) size++;
}

Метка used ставится на вершину правой доли и обнуляется перед каждым запуском. Один запуск просматривает каждое ребро не больше раза, то есть стоит $O(E)$; запусков $n$; итого $O(VE)$.

Две эвристики, которые надо писать всегда

Жадное начало. Перед основным циклом пройдите по вершинам и возьмите любое свободное ребро:

for (int u = 0; u < n; u++)
    for (int v : adj[u])
        if (matchRight[v] == -1) { matchRight[v] = u; matchLeft[u] = v; break; }

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

Случайный порядок. Кун чувствителен к порядку просмотра: существуют графы, на которых при неудачном порядке он делает почти $VE$ операций. Перемешивание списков смежности лечит это почти всегда.

Если и этого мало — есть Хопкрофт — Карп с честной оценкой $O(E\sqrt V)$.

Теорема Холла

Паросочетание, покрывающее всю долю $A$, существует тогда и только тогда, когда $|N(S)| \ge |S|$ для любого $S \subseteq A$, где $N(S)$ — множество соседей вершин из $S$.

Проверять все подмножества не нужно — Кун отвечает на тот же вопрос за полином. Теорема полезна другим: она объясняет, почему паросочетания не хватает. Есть и количественная форма:

$$n - |M| = \max_{S \subseteq A} \bigl(|S| - |N(S)|\bigr).$$

Слева — число вершин доли $A$, которые останутся без пары; справа — «самое узкое место». Обе стороны выводятся из теоремы Кёнига.

Чего Кун не умеет

Не работает в недвудольном графе. Обход упирается в нечётные циклы: чередующийся путь может вернуться в уже пройденную вершину и «схлопнуться». Для общего случая нужен алгоритм Эдмондса со сжатием соцветий — заметно сложнее.

Не учитывает веса. Максимальное по числу рёбер и максимальное по сумме весов — разные задачи. Вторая решается венгерским алгоритмом или потоком минимальной стоимости. Исключение — когда веса стоят на вершинах одной доли: тогда работает жадность по убыванию веса, потому что покрываемые множества образуют трансверсальную матроиду.