Кун, Кёниг и Холл: алгоритм и две теоремы

Если ты умеешь написать Куна, знаешь теорему Кёнига вместе с построением покрытия и формулируешь условие Холла с дефицитом, листай до «Теперь сам».

Как думаешь, почему трое не разойдутся

Трое работников, и все трое умеют только одну и ту же задачу. Сколько работ раздашь? Одну, это очевидно. А теперь скажи не «сколько», а ПОЧЕМУ: какое короткое наблюдение доказывает, что двух быть не может, не перебирая вариантов?

Наблюдение такое: все рёбра графа упираются в одну задачу. Достаточно «накрыть» эту одну вершину - и накрыты все рёбра. Размер такого накрытия и есть предел для паросочетания: одно ребро покрытия не может обслужить две пары. Это и есть теорема Кёнига, увиденная на трёх вершинах.

На что это похоже

Сторож и коридоры. Паросочетание - это непересекающиеся маршруты, вершинное покрытие - посты охраны, мимо которых не пройти. Чем больше непересекающихся маршрутов, тем больше постов нужно; чем меньше постов хватает, тем меньше маршрутов возможно. В двудольном графе эти два числа СОВПАДАЮТ, и потому каждое из них доказывает другое.

Механизм: обход в глубину по чередующимся путям

Кун:
    match_r[j] - кто занял правую вершину j, или -1
    для каждой левой вершины v:
        пометки used[] обнулить
        если try(v): размер += 1

    try(v):
        для каждого соседа j вершины v:
            если j не помечена:
                пометить j
                если match_r[j] == -1 или try(match_r[j]):
                    match_r[j] = v
                    вернуть True
        вернуть False

Рекурсия try(match_r[j]) и есть «переставить»: занявшего правую вершину просят подвинуться, и он ищет себе другое место по тем же правилам. Пометки used не дают ходить по кругу и обнуляются перед КАЖДОЙ новой левой вершиной - это важнее, чем кажется, и забывают об этом чаще всего.

Нумерация здесь двойная, и путать её нельзя: v - номер ЛЕВОЙ вершины, j - номер ПРАВОЙ, adj[v] хранит правые номера, match_r[j] и used[j] индексируются правыми. В рекурсию уходит match_r[j] - снова левый номер.

def try_kuhn(v, adj, match_r, used):
    for j in adj[v]:
        if not used[j]:
            used[j] = True
            if match_r[j] == -1 or try_kuhn(match_r[j], adj, match_r, used):
                match_r[j] = v
                return True
    return False

Цена: одна попытка стоит O(E), попыток |L|, итого O(V·E). Хопкрофт-Карп ищет дополняющие пути пачками и даёт O(E·√V) - это тот же Диниц на единичных пропускных способностях.

Правило

Алгоритм Куна: для каждой левой вершины запускай обход в глубину по чередующимся путям, обнуляя пометки перед каждым запуском; нашёл дополняющий путь - переключи его. Цена O(V·E), у Хопкрофта-Карпа O(E·√V). ТЕОРЕМА КЁНИГА: в двудольном графе максимальное паросочетание равно минимальному вершинному покрытию. ТЕОРЕМА ХОЛЛА: паросочетание, занимающее всю левую долю, существует тогда и только тогда, когда |N(S)| >= |S| для КАЖДОГО подмножества S левой доли; в общем случае размер максимального паросочетания равен |L| − max(|S| − |N(S)|).

Разбор: три работника и одна задача

Граф: слева А, Б, В, справа 1, 2, 3. Рёбра: А-1, Б-1, В-1. Больше никаких.

Прогон Куна:

v = А: сосед 1 свободен          → пара А-1, размер 1
v = Б: сосед 1 занят Аней,
       пробуем переставить Аню:
       у Ани других соседей нет  → путь не найден, Б остаётся свободным
v = В: то же самое              → свободен

Размер 1. Теперь сертификат по Кёнигу: возьмём вершинное покрытие {1} - одна вершина, и все три ребра ею накрыты. Значит паросочетание не больше 1 (каждое его ребро требует своей вершины покрытия), а единица достигнута - ответ доказан.

Холл на том же графе: возьмём S = {А, Б, В}. Соседи этого множества - N(S) = {1}, то есть |N(S)| = 1, а |S| = 3. Условие |N(S)| >= |S| нарушено, дефицит 3 − 1 = 2. Формула даёт |L| − дефицит = 3 − 2 = 1 - тот же ответ, полученный вообще без алгоритма.

Разбор: как достать вершинное покрытие из паросочетания

Кёниг не просто равенство - он конструктивен, и это его практическая часть. Пусть паросочетание уже максимально.

Z строится обходом от СВОБОДНЫХ левых вершин, чередуя рёбра:
    из левой вершины идём по рёбрам ВНЕ паросочетания  → добавляем правые
    из правой вершины идём по ребру ПАРОСОЧЕТАНИЯ      → добавляем левую
    (свободные левые вершины сами входят в Z)

покрытие = (левые, НЕ попавшие в Z)  ∪  (правые, попавшие в Z)

Проверим на графе из прошлого урока: слева A, B, C, справа 1, 2, 3, рёбра A-1, A-2, B-1, C-2, C-3, максимальное паросочетание B-1, A-2, C-3 - размер 3, свободных левых вершин нет. Тогда Z пусто, покрытие = все левые вершины = {A, B, C}, размер 3. Совпало с паросочетанием.

А вот пример поинтереснее: рёбра А-1, Б-1, В-1 из первого разбора. Паросочетание А-1, свободные левые - Б и В. Из Б идём по ребру Б-1 в вершину 1 (ребро не в паре), из 1 по ребру пары возвращаемся в А. Значит Z = {Б, В, 1, А}. Покрытие: левые не из Z - никого; правые из Z - вершина 1. Итого {1}, размер 1 ✓.

Зачем это нужно на практике: покрытие - это ответ на вопрос «где узкое место». В расписании оно говорит, какие именно аудитории или станки создают затор, а не просто «больше 7 пар не выйдет».

Что ломается без этого

Первое: не обнулять used перед каждой новой левой вершиной - алгоритм пропустит существующие дополняющие пути и вернёт заниженный ответ. Второе: обнулять used ВНУТРИ рекурсии - тогда обход зациклится. Третье: применять Кёнига к недвудольному графу: там равенство неверно (простейший контрпример - треугольник: паросочетание 1, покрытие 2). Четвёртое: проверять условие Холла перебором всех подмножеств - их 2^|L|; на практике считают максимальное паросочетание и смотрят, занята ли вся левая доля. Холл нужен как ОБЪЯСНЕНИЕ и как источник контрпримера, а не как алгоритм. Пятое: думать, что Кун работает и на общем графе, потому что код не проверяет двудольность, - проверять её надо самому, иначе ответ будет молча неверным.

Зачем это в работе

Кун - тот редкий алгоритм, который пишут руками прямо на собеседовании: двадцать строк и никакой структуры данных. Его хватает на графы в десятки тысяч рёбер. Кёниг превращает «не получилось назначить всех» в конкретный список узких мест, который можно показать заказчику. Холл объясняет, почему не получилось, языком предметной области: «вот эти пять заявок конкурируют за три слота». Именно эта пара «число плюс объяснение» и отличает решение задачи от отчёта вида «программа выдала 7».

Теперь сам

Слева A, B, C, D, справа 1, 2, 3, 4. Рёбра: A-1, A-2, B-1, B-2, C-1, C-2, D-3. Найди максимальное паросочетание, вершинное покрытие того же размера и объясни ответ по Холлу.