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

Теорема

Теорема:

Если из вершины $x$ не существует Корректность алгоритма следует из дополняющей цепи относительно паросочетания $M$ и паросочетание $M'$ получается из $M$ изменением вдоль дополняющей цепи, тогда из $x$ не существует дополняющей цепи в $M'$.

Доказательство:

$\triangleright$

Рисунок 1. Рисунок 2. Пунктиром обозначен путь между двумя вершинами. Ребро красного цвета лежит в паросочетании, а черного - нет. Доказательство от противного. Допустим в паросочетание внесли изменения вдоль дополняющей цепи $(y \rightsquigarrow z)$ и из вершины $x$ появилась дополняющая цепь. Заметим, что эта дополняющая цепь должна вершинно пересекаться с той цепью, вдоль которой вносились изменения, иначе такая же дополняющая цепь из $x$ существовала и в исходном паросочетании. Пусть $p$ – ближайшая к $x$ вершина, которая принадлежит и новой дополняющей цепи и цепи $(y \rightsquigarrow z)$. Тогда $MP$ – последнее ребро на отрезке $(y \rightsquigarrow p)$ цепи $(y \rightsquigarrow z)$, $NP$ – последнее ребро на отрезке $(z \rightsquigarrow p)$ цепи $(y \rightsquigarrow z)$, $QP$ - последнее ребро лежащее на отрезке $(x \rightsquigarrow p)$ новой дополняющей цепи(см. Рисунок 1). Допустим $MP$ принадлежит паросочетанию $M'$, тогда $NP$ ему не принадлежит. (Случай, когда $NP$ принадлежит паросочетанию $M'$ полностью симметричен.) Поскольку паросочетание $M'$ получается из $M$ изменением вдоль дополняющей цепи $(y \rightsquigarrow z)$, в паросочетание $M$ входило ребро $NP$, а ребро $MP$ нет. Кроме того, ребро $QP$ не лежит ни в исходном паросочетании $M$, ни в паросочетании $M'$, в противном случае оказалось бы, что вершина $p$ инцидентна нескольким ребрам из паросочетания, что противоречит определению паросочетания. Тогда заметим, что цепь $(x \rightsquigarrow z)$, полученная объединением цепей $(x \rightsquigarrow p)$ и $(p \rightsquigarrow z)$, по определению будет дополняющей в паросочетании $M$, что приводит к противоречию, поскольку в паросочетании $M$ из вершины $x$ не существует дополняющей цепи.

$\triangleleft$

Алгоритм

Задан граф $G\langle V, E \rangle$, про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в нем

Алгоритм можно описать так: сначала возьмём пустое паросочетание, а потом — пока в графе удаётся найти увеличивающую цепь, — будем выполнять чередование паросочетания вдоль этой цепи, и повторять процесс поиска увеличивающей цепи. Как только такую цепь найти не удалось — процесс останавливаем, — текущее паросочетание и есть максимальное.

В массиве $\mathtt{matching}$ хранятся паросочетания $(v, \mathtt{matching}[v])$ (Если паросочетания с вершиной $v$ не существует, то $\mathtt{matching}[v]= -1$). А $used$ — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды). Функция $\mathrm{dfs}$ возвращает $true$, если ей удалось найти увеличивающую цепь из вершины $v$, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.

Внутри функции просматриваются все рёбра, исходящие из вершины $v$, и затем проверяется: если это ребро ведёт в ненасыщенную вершину $to$, либо если эта вершина $to$ насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из $\mathtt{matching}[to]$, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом $true$ производим чередование в текущем ребре: перенаправляем ребро, смежное с $to$, в вершину $v$.

В основной программе сначала указывается, что текущее паросочетание — пустое (массив $\mathtt{matching}$ заполняется числами $-1$). Затем перебирается вершина $v$, и из неё запускается обход в глубину $\mathrm{dfs}$, предварительно обнулив массив $used$.

Стоит заметить, что размер паросочетания легко получить как число вызовов $\mathrm{dfs}$ в основной программе, вернувших результат $true$. Само искомое максимальное паросочетание содержится в массиве $\mathtt{matching}$. После того, как все вершины $v \in V$ будут просмотрены, текущее паросочетание будет максимальным. Корректность алгоритма следует из теоремы о максимальном паросочетании и дополняющих цепях и теоремы, описанной выше.

Реализация

• Граф $G\langle V, E \rangle$ хранится в матрице смежности $g[i][j]$ размера $n$ на $n$
• n=|V|

bool dfs(v: int):
    if (used[v])
        return false
    used[v] = true
    for to in g[v]
        if (matching[to] == -1 or dfs(matching[to])):
            matching[to] = v
            return true 
    return false

function main():
    fill(matching, -1)
    for i = 1..n
         fill(used, false)
         dfs(i)
    for i = 1..n
         if (matching[i] != -1)
              print(i, " ", matching[i])

Время работы

Итак, алгоритм Куна можно представить как серию из $n$ запусков обхода в глубину на всём графе.

Следовательно, всего этот алгоритм исполняется за время $O(nm)$, где $m$ — количество ребер, что в худшем случае есть $O(n^3)$

Если явно задано разбиение графа на две доли размером $n_1$ и $n_2$, то можно запускать $\mathtt{dfs}$ только из вершин первой доли, поэтому весь алгоритм исполняется за время $O(n_1m)$, где $m$ - число ребер. В худшем случае это составляет $O(n_1^2n_2)$

</tex>.

Ссылки

• Теорема о максимальном паросочетании и дополняющих цепях
• Алгоритм Форда-Фалкерсона для поиска максимального паросочетания

Источники информации

• MAXimal :: algo :: Алгоритм Куна нахождения наибольшего паросочетания
  
• Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — СПб.: Издательство "Лань", 2010. — 291 стр.