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

Коротко

Задача

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

Такой набор рёбер без общих вершин называется паросочетанием, а максимальный по размеру — максимальным паросочетанием.

работники   задачи
    A ──────── 1
      \
    B ──╳───── 2
       /
    C ──────── 3

паросочетание: A-1, B-2, C-3  (размер 3)

Ключевое понятие: увеличивающая цепь

Алгоритм Куна строится вокруг одной идеи.

Увеличивающая цепь — путь, который начинается в свободной вершине левой доли, заканчивается в свободной вершине правой доли, и по пути чередуются рёбра: не в паросочетании, в паросочетании, не в паросочетании, и так далее.

A ---- 1 ==== B ---- 2
  свободн.  в паре   свободн.

--- ребро вне паросочетания
=== ребро в паросочетании

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

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

Реализация

def kuhn(graph: dict, left_vertices: list) -> dict:
    """graph: вершина левой доли -> список вершин правой доли.
    Возвращает {вершина правой доли: вершина левой}."""
    match = {}      # правая -> левая

    def try_kuhn(v, visited) -> bool:
        for to in graph.get(v, ()):
            if to in visited:
                continue
            visited.add(to)

            # либо задача свободна, либо её текущего исполнителя
            # удаётся переназначить
            if to not in match or try_kuhn(match[to], visited):
                match[to] = v
                return True

        return False

    for v in left_vertices:
        try_kuhn(v, set())      # visited своё для каждого запуска

    return match


graph = {
    'A': [1, 2],
    'B': [1],
    'C': [2, 3],
}

result = kuhn(graph, ['A', 'B', 'C'])
print(result)                 # {1: 'B', 2: 'A', 3: 'C'}
print('размер:', len(result)) # 3

Вся суть в строке if to not in match or try_kuhn(match[to], visited). Она читается так: «если задача свободна — берём её; если занята — пробуем переселить текущего исполнителя на другую задачу».

Именно эта рекурсия и есть поиск увеличивающей цепи.

Множество visited создаётся заново для каждой стартовой вершины. Это принципиально: оно защищает от зацикливания внутри одного поиска, но не должно мешать следующим запускам.

Оптимизация: жадная инициализация

Простое улучшение, которое на практике ускоряет алгоритм в разы. Перед основным циклом жадно назначаем очевидные пары.

def kuhn_optimized(graph: dict, left_vertices: list) -> dict:
    match = {}
    used_left = set()

    # жадно берём всё, что берётся без конфликтов
    for v in left_vertices:
        for to in graph.get(v, ()):
            if to not in match:
                match[to] = v
                used_left.add(v)
                break

    def try_kuhn(v, visited) -> bool:
        for to in graph.get(v, ()):
            if to in visited:
                continue
            visited.add(to)
            if to not in match or try_kuhn(match[to], visited):
                match[to] = v
                return True
        return False

    for v in left_vertices:
        if v not in used_left:
            try_kuhn(v, set())

    return match

Жадная фаза обычно закрывает большую часть пар, и дорогой поиск цепей запускается лишь для остатка.

Теорема Кёнига: неожиданное следствие

Красивый результат: в двудольном графе размер максимального паросочетания равен размеру минимального вершинного покрытия.

Вершинное покрытие — минимальный набор вершин, «трогающий» каждое ребро.

Это даёт бесплатное решение ещё двух задач:

• минимальное вершинное покрытие = размер паросочетания;
• максимальное независимое множество = V − размер паросочетания.

Для произвольных (не двудольных) графов обе задачи NP-полны. Двудольность превращает их в полиномиальные — вот почему проверка на двудольность имеет практический смысл.

Практические применения

Распределение задач между исполнителями с учётом навыков.

Составление расписания: преподаватели и аудитории, врачи и смены.

Задача о назначениях — если добавить веса, нужен венгерский алгоритм.

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

Сопоставление данных — связывание записей из двух источников.

Сравнение с другими подходами

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

Сведение к максимальному потоку тоже работает (исток → левая доля → правая доля → сток с единичными пропускными способностями), но код длиннее.

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

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

Отсутствие visited вообще. Бесконечная рекурсия.

Применение к недвудольному графу. Алгоритм отработает, но результат будет неверным. Для произвольных графов нужен алгоритм Эдмондса с «цветками».

Глубокая рекурсия. На больших графах стоит переписать try_kuhn итеративно.

Путаница направления в match. В коде выше словарь хранит «правая → левая». Смешение направлений — источник трудноуловимых багов.

Что запомнить

• Паросочетание — набор рёбер без общих вершин; ищем максимальное.
• Алгоритм Куна ищет увеличивающие цепи и инвертирует их, наращивая размер на единицу.
• Ключевая строка: «задача свободна или её исполнителя можно переселить».
• Множество посещённых создаётся заново для каждой стартовой вершины.
• По теореме Кёнига размер паросочетания равен минимальному вершинному покрытию.

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→