Информатика / Алгоритмы и анализ данных

Алгоритм Куна: увеличивающий путь паросочетания

Алгоритм Куна ищет максимальное по числу пар паросочетание в двудольном графе. Увеличивающий путь чередует свободные и занятые рёбра; смена их принадлежности освобождает место и добавляет одну новую пару.

Опубликовано: 26 октября 2026 г.Обновлено: 26 октября 2026 г.

Формула

M_{\mathrm{new}}=M\triangle P,\qquad |M_{\mathrm{new}}|=|M|+1,\qquad T=O(|L|E)

Схема Три пары после переназначения

Зелёные рёбра: u1-v2, u2-v1, u3-v3. Серые показывают остальные допустимые пары.

Обозначения

$L,R$: левая и правая доли без внутренних рёбер, множества
$M$: текущее паросочетание, множество рёбер
$P$: чередующийся путь со свободными концами, путь
$△$: симметрическая разность наборов рёбер, операция
$E$: число допустимых рёбер между долями, 1

Условия применения

Граф двудолен: каждая дуга совместимости соединяет левую и правую доли. Оптимизируется число пар без весов. Поиск из свободной левой вершины может рекурсивно переназначать уже занятые правые вершины; отметки посещения обновляют для каждого нового поиска.

Ограничения

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

Подробное объяснение

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

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

DFS отмечает посещённые левые вершины, чтобы не зациклиться на переназначениях. Для следующей исходной вершины отметки очищают, потому что паросочетание уже изменилось. Один поиск стоит O(E), а запусков не более |L|, что даёт O(|L|E) для стандартного варианта.

Отсутствие увеличивающего пути характеризует максимальный размер паросочетания. В двудольном графе задачу можно также свести к потоку с единичными ёмкостями. Это даёт независимую проверку размера, но не меняет условие допустимости каждой пары.

Как пользоваться формулой

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

Историческая справка

Алгоритмы паросочетания развивают идею улучшения допустимого набора пар по чередующимся путям. В двудольном случае связь с единичным сетевым потоком делает переназначение особенно наглядным: обратные остаточные дуги соответствуют отмене уже выбранных пар.

В алгоритмических курсах XX–XXI веков простой DFS-вариант часто называют алгоритмом Куна. Документация Princeton описывает alternating-path matching и отдельно связывает его со сведением к максимальному потоку. При этом общее название паросочетания нельзя смешивать со взвешенной задачей назначения: совпадение математических тем не означает совпадения целевой функции. Современная реализация хранит партнёра правой вершины и допускает рекурсивное переназначение, сохраняя исходный смысл увеличения числа непересекающихся пар.

Историческая линия формулы

Название алгоритма Куна в этой задаче относится к простому поиску увеличивающих путей в двудольном графе. Принцип чередования и связь с потоком шире одной реализации. Здесь максимизируется число пар; венгерский метод для стоимостного назначения решает другую цель.

Пример

Пусть L={u1,u2,u3}, R={v1,v2,v3}; допустимы u1-v1, u1-v2, u2-v1, u3-v2, u3-v3. Сначала возьмём u1-v1. Для u2 единственный сосед v1 уже занят, но есть чередующийся путь u2-v1-u1-v2. Меняем принадлежность трёх рёбер: получаем u2-v1 и u1-v2, то есть две пары вместо одной. Затем u3 занимает v3. Итоговый размер 3, все шесть концов различны. Верхняя граница равна min(|L|,|R|)=3, поэтому решение максимально. Без переназначения u1 первый жадный выбор мог бы оставить u2 без пары и ошибочно закончить на размере 2.

Частая ошибка

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

Практика

Задачи с решением

Общий единственный сосед

Условие. Две левые вершины обе соединены только с одной правой. Каков максимальный размер?

Решение. Одна правая вершина входит не более чем в одну пару; одну пару построить можно.

Ответ. 1.

Перестановка партнёра

Условие. Рёбра u1-v1,u1-v2,u2-v1; уже выбрано u1-v1. Найдите увеличение.

Решение. Путь u2-v1-u1-v2 меняет одну старую пару на две новые: u2-v1 и u1-v2.

Ответ. Размер увеличивается с 1 до 2.

Дополнительные источники

https://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/BipartiteMatching.html
https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/07AssignmentProblem.pdf

Связанные формулы

Информатика

Метод Форда—Фалкерсона: увеличивающий путь потока

$\delta=\min_{e\in P}c_f(e),\quad |f_{\mathrm{new}}|=|f|+\delta,\quad c_f(u,v)=c(u,v)-f(u,v)$

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

Информатика

Максимальный поток и минимальный разрез сети

$\max_f |f|=\min_{s\in S,\ t\notin S}c(S,V\setminus S),\quad c(S,\bar S)=\sum_{u\in S,\ v\notin S}c(u,v)$

Теорема о максимальном потоке и минимальном разрезе даёт сертификат оптимальности: допустимый поток максимален, если его величина совпала с суммой ёмкостей некоторого разделяющего разреза источника и стока.

Информатика

Поиск в глубину: дерево обхода и времена входа и выхода

$u\text{ — предок }v\iff t_{in}(u)<t_{in}(v)<t_{out}(v)<t_{out}(u),\quad u\ne v$

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