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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Реализация: маленькая правка)
(Алгоритм: изменил алгоритм)
Строка 19: Строка 19:
  
 
==Алгоритм==
 
==Алгоритм==
:Алгоритм просматривает все вершины графа по очереди, запуская из каждой обход (в глубину или в ширину), пытающийся найти увеличивающую цепь, начинающуюся в этой вершине.
+
Задан граф <tex>G(V, E)</tex>, про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в нем
:Задан двудольный граф <tex>G(V, E)</tex>, где <tex>V_1</tex> и <tex>V_2</tex> {{---}} его левая и правая доли соответственно.  
+
 
:Просматриваем все вершины <tex>v</tex> первой доли графа <tex>u \in V_1</tex>:
+
Алгоритм можно описать так: сначала возьмём пустое паросочетание, а потом — пока в графе удаётся найти увеличивающую цепь, — будем выполнять чередование паросочетания вдоль этой цепи, и повторять процесс поиска увеличивающей цепи. Как только такую цепь найти не удалось — процесс останавливаем, — текущее паросочетание и есть максимальное.
:*Если текущая вершина  уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем;
+
 
:*Иначе запускаем поиск увеличивающей цепи, начинающейся с этой вершины.
+
В массиве <tex>matching</tex> хранятся паросочетания <tex> (v, matching[v]) </tex> (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> matching[v] </tex> = -1). А <tex>used</tex> - обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
:Рассмотрим поиск увеличивающей цепи обходом в глубину.
+
Функция <tex> \mathrm{dfs} </tex> возвращает  <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.
:* Запускаем обход от вершины <tex>v</tex>.
+
 
:* Просматриваем все рёбра из этой вершины, пусть текущее ребро <tex>(v, to)</tex>.
+
Внутри функции просматриваются все рёбра, исходящие из вершины v первой доли, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>mt[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.
:* Если вершина <tex>to</tex> ещё не насыщена паросочетанием, то включаем ребро <tex>(v, to)</tex> в паросочетание и прекращаем поиск из вершины <tex>v</tex>.
+
 
:* Иначе, если вершина <tex>to</tex> уже насыщена каким-то ребром <tex>(p, to)</tex> и не посещена, то просто перейдем в нашем обходе в вершину <tex>p</tex>.
+
В основной программе сначала указывается, что текущее паросочетание — пустое (список <tex> mt</tex> заполняется числами -1). Затем перебирается вершина  <tex>v </tex> первой доли, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.
:** Пробуем найти часть увеличивающей цепи из вершины <tex>p</tex>.
+
 
:** Если получилось, то удаляем из паросочетания ребро <tex>(p, to)</tex>, а вместо него добавляем <tex>(v, to)</tex>
+
Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> mt </tex>.
: Этот обход, запущенный из вершины <tex>v</tex>, либо найдет увеличивающую цепь, и тем самым насытит вершину, либо же такой увеличивающей цепи не найдёт (и, следовательно, эта вершина  уже не сможет стать насыщенной).
+
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
: После того, как все вершины <tex>u \in V_1</tex> будут просмотрены, текущее паросочетание будет максимальным.
+
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше.<br>
: Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше.<br>
 
  
 
==Реализация==
 
==Реализация==

Версия 16:27, 11 января 2015

Теорема

Теорема:
Если из вершины [math]x[/math] не существует дополняющей цепи относительно паросочетания [math]M[/math] и паросочетание [math]M'[/math] получается из [math]M[/math] изменением вдоль дополняющей цепи, тогда из [math]x[/math] не существует дополняющей цепи в [math]M'[/math].
Доказательство:
[math]\triangleright[/math]
Рисунок 1.
Рисунок 2.
Пунктиром обозначен путь между двумя вершинами. Ребро красного цвета лежит в паросочетании, а черного - нет.
Доказательство от противного.

Допустим в паросочетание внесли изменения вдоль дополняющей цепи [math](y \rightsquigarrow z)[/math] и из вершины [math]x[/math] появилась дополняющая цепь.
Заметим, что эта дополняющая цепь должна вершинно пересекаться с той цепью, вдоль которой вносились изменения, иначе такая же дополняющая цепь из [math]x[/math] существовала и в исходном паросочетании.

Пусть [math]p[/math] — ближайшая к [math]x[/math] вершина, которая принадлежит и новой дополняющей цепи и цепи [math](y \rightsquigarrow z)[/math].
Тогда [math]MP[/math] - последнее ребро на отрезке [math](y \rightsquigarrow p)[/math] цепи [math](y \rightsquigarrow z)[/math], [math]NP[/math] - последнее ребро на отрезке [math](z \rightsquigarrow p)[/math] цепи [math](y \rightsquigarrow z)[/math], [math]QP[/math] - последнее ребро лежащее на отрезке [math](x \rightsquigarrow p)[/math] новой дополняющей цепи(см. Рисунок 1).

Допустим [math]MP[/math] принадлежит паросочетанию [math]M'[/math], тогда [math]NP[/math] ему не принадлежит.
(Случай, когда [math]NP[/math] принадлежит паросочетанию [math]M'[/math] полностью симметричен.)

Поскольку паросочетание [math]M'[/math] получается из [math]M[/math] изменением вдоль дополняющей цепи [math](y \rightsquigarrow z)[/math], в паросочетание [math]M[/math] входило ребро [math]NP[/math], а ребро [math]MP[/math] нет.
Кроме того, ребро [math]QP[/math] не лежит ни в исходном паросочетании [math]M[/math], ни в паросочетании [math]M'[/math], в противном случае оказалось бы, что вершина [math]p[/math] инцидентна нескольким ребрам из паросочетания, что противоречит определению паросочетания.

Тогда заметим, что цепь [math](x \rightsquigarrow z)[/math], полученная объединением цепей [math](x \rightsquigarrow p)[/math] и [math](p \rightsquigarrow z)[/math], по определению будет дополняющей в паросочетании [math]M[/math], что приводит к противоречию, поскольку в паросочетании [math]M[/math] из вершины [math]x[/math] не существует дополняющей цепи.
[math]\triangleleft[/math]

Алгоритм

Задан граф [math]G(V, E)[/math], про который известно, что он двудольный, но разбиение не задано явно.Требуется найти наибольшее паросочетание в нем

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

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

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

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

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

Реализация

  • Граф [math]G[/math] хранится списками смежности [math]g[v][i][/math]
  • Функция [math]dfs(v)[/math] — обход в глубину, возвращает [math]true[/math], если есть увеличивающая цепь из вершины [math]v[/math].
  • В массиве [math]matching[/math] хранятся паросочетания. Паросочетание есть ребро [math](i, matching[i])[/math].


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 v in V:
         fill(used, false)
         dfs(v)
    for v in V:
         if (matching[v] != -1):
              print(v, " ", matching[v])

Время работы

Итак, алгоритм Куна можно представить как серию из [math]n_1[/math] запусков обхода в глубину на всём графе.
Следовательно, всего этот алгоритм исполняется за время [math]O(nm)[/math], где [math]m[/math] — количество ребер, что в худшем случае есть [math]O(n^3)[/math].
Более точная оценка:
В описанной выше реализации запуски обхода в глубину/ширину происходят только из вершин первой доли, поэтому весь алгоритм исполняется за время [math]O(n_1m)[/math] , где [math]n_1[/math] — число вершин первой доли. В худшем случае это составляет [math]O(n_1^2n_2)[/math], где [math]n_2[/math] — число вершин второй доли.

Ссылки

Источники