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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники: изменил с : на *)
(Реализация: половина изменений)
Строка 35: Строка 35:
 
: Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше.<br>
 
: Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше.<br>
  
==Релизация==
+
==Реализация==
  
: Граф <tex>G</tex> хранится списками смежности <tex>g[v][i]</tex>
+
* Граф <tex>G</tex> хранится списками смежности <tex>g[v][i]</tex>
: Функция <tex>dfs(v)</tex> {{---}} обход в глубину, возвращает <tex>true</tex> если есть увеличивающая цепь из вершины <tex>v</tex>.
+
* Функция <tex>dfs(v)</tex> {{---}} обход в глубину, возвращает <tex>true</tex> если есть увеличивающая цепь из вершины <tex>v</tex>.
: В массиве <tex>matching</tex> хранятся паросочетания. Паросочетание есть ребро <tex>(i, matching[i])</tex>.
+
* В массиве <tex>matching</tex> хранятся паросочетания. Паросочетание есть ребро <tex>(i, matching[i])</tex>.
  
  
  bool dfs(int v)  
+
  '''bool''' '''dfs'''('''int''' v)  
{
+
     '''if''' (used[v])
     if (used[v])
+
         return false
         return false;
 
 
 
     used[v] = true;
 
     used[v] = true;
     for (int i = 0; i < g[v].size(); i++)
+
     '''for''' to '''in''' g[v]:
    {
 
        int to = g[v][i];
 
 
         if (matching[to] == -1 || dfs(matching[to]))
 
         if (matching[to] == -1 || dfs(matching[to]))
        {
+
             matching[to] = v
             matching[to] = v;
+
             '''return''' true  
             return true;
+
     '''return''' false
        }
+
 
    }
+
Как вызывать:
     return false;
+
 
}
+
fill(matching, -1)
+
'''for''' u '''in''' N:
int main()
+
     fill(used, false)
{
+
    '''dfs'''(u)
    ... чтение графа ...
+
for (int i = 0; i < k; i++)
    matching.assign (k, -1);
+
    if (matching[i] != -1)
    for (int u = 0; u < n; u++)
+
          ... вывод ...*/
     {
 
        used.assign(n, false);
 
        dfs(u);
 
    }
 
 
    for (int i = 0; i < k; i++)
 
        if (matching[i] != -1)
 
            ... вывод ...
 
 
}
 
  
 
==Время работы==
 
==Время работы==

Версия 15:45, 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]V_1[/math] и [math]V_2[/math] — его левая и правая доли соответственно.
Просматриваем все вершины [math]v[/math] первой доли графа [math]u \in V_1[/math]:
  • Если текущая вершина уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем;
  • Иначе запускаем поиск увеличивающей цепи, начинающейся с этой вершины.
Рассмотрим поиск увеличивающей цепи обходом в глубину.
  • Запускаем обход от вершины [math]v[/math].
  • Просматриваем все рёбра из этой вершины, пусть текущее ребро — [math](v, to)[/math].
  • Если вершина [math]to[/math] ещё не насыщена паросочетанием, то включаем ребро [math](v, to)[/math] в паросочетание и прекращаем поиск из вершины [math]v[/math].
  • Иначе, если вершина [math]to[/math] уже насыщена каким-то ребром [math](p, to)[/math] и не посещена, то просто перейдем в нашем обходе в вершину [math]p[/math].
    • Пробуем найти часть увеличивающей цепи из вершины [math]p[/math].
    • Если получилось, то удаляем из паросочетания ребро [math](p, to)[/math], а вместо него добавляем [math](v, to)[/math]
Этот обход, запущенный из вершины [math]v[/math], либо найдет увеличивающую цепь, и тем самым насытит вершину, либо же такой увеличивающей цепи не найдёт (и, следовательно, эта вершина уже не сможет стать насыщенной).
После того, как все вершины [math]u \in V_1[/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(int v) 
    if (used[v])
        return false
    used[v] = true;
    for to in g[v]:
        if (matching[to] == -1 || dfs(matching[to]))
            matching[to] = v
            return true    
    return false

Как вызывать:

fill(matching, -1) for u in N:

    fill(used, false)
    dfs(u)

for (int i = 0; i < k; i++)

    if (matching[i] != -1)
         ... вывод ...*/

Время работы

Итак, алгоритм Куна можно представить как серию из [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] — число вершин второй доли.

Ссылки

Источники