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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 2: Строка 2:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
  Если из вершины <tex>x</tex> не существует [[Теорема о максимальном паросочетании и дополняющих цепях|дополняющей цепи]] относительно паросочетания <tex>M</tex> и паросочетание <tex>M'</tex> получается из <tex>M</tex> изменением вдоль дополняющей цепи, тогда из <tex>x</tex> не существует дополняющей цепи в <tex>M'</tex>.
+
  Если из вершины <tex>x</tex> не существует дополняющей цепи относительно паросочетания <tex>M</tex> и паросочетание <tex>M'</tex> получается из <tex>M</tex> изменением вдоль дополняющей цепи, тогда из <tex>x</tex> не существует дополняющей цепи в <tex>M'</tex>.
 
|proof=
 
|proof=
 
[[Файл:Kuhn2.png|thumb|right|300x300px|Рисунок 1.]]
 
[[Файл:Kuhn2.png|thumb|right|300x300px|Рисунок 1.]]
Строка 9: Строка 9:
 
: Допустим в паросочетание внесли изменения вдоль дополняющей цепи <tex>(y \rightsquigarrow z)</tex> и из вершины <tex>x</tex> появилась дополняющая цепь.
 
: Допустим в паросочетание внесли изменения вдоль дополняющей цепи <tex>(y \rightsquigarrow z)</tex> и из вершины <tex>x</tex> появилась дополняющая цепь.
 
: Заметим, что эта дополняющая цепь должна вершинно пересекаться с той цепью, вдоль которой вносились изменения, иначе такая же дополняющая цепь из <tex>x</tex> существовала и в исходном паросочетании.<br><br>
 
: Заметим, что эта дополняющая цепь должна вершинно пересекаться с той цепью, вдоль которой вносились изменения, иначе такая же дополняющая цепь из <tex>x</tex> существовала и в исходном паросочетании.<br><br>
: Пусть <tex>p</tex> ближайшая к <tex>x</tex> вершина, которая принадлежит и новой дополняющей цепи и цепи <tex>(y \rightsquigarrow z)</tex>.
+
: Пусть <tex>p</tex> - ближайшая к <tex>x</tex> вершина, которая принадлежит и новой дополняющей цепи и цепи <tex>(y \rightsquigarrow z)</tex>.
: Тогда <tex>MP</tex> последнее ребро на отрезке <tex>(y \rightsquigarrow p)</tex> цепи <tex>(y \rightsquigarrow z)</tex>, <tex>NP</tex> последнее ребро на отрезке <tex>(z \rightsquigarrow p)</tex> цепи <tex>(y \rightsquigarrow z)</tex>, <tex>QP</tex> - последнее ребро лежащее на отрезке <tex>(x \rightsquigarrow p)</tex> новой дополняющей цепи(см. Рисунок 1).<br><br>
+
: Тогда <tex>MP</tex> - последнее ребро на отрезке <tex>(y \rightsquigarrow p)</tex> цепи <tex>(y \rightsquigarrow z)</tex>, <tex>NP</tex> - последнее ребро на отрезке <tex>(z \rightsquigarrow p)</tex> цепи <tex>(y \rightsquigarrow z)</tex>, <tex>QP</tex> - последнее ребро лежащее на отрезке <tex>(x \rightsquigarrow p)</tex> новой дополняющей цепи(см. Рисунок 1).<br><br>
: Допустим <tex>MP</tex> принадлежит паросочетанию <tex>M'</tex>, тогда <tex>NP</tex> ему не принадлежит.<br>
+
: Допустим <tex>MP(NP)</tex> принадлежит паросочетанию <tex>M'</tex>, тогда <tex>NP(MP)</tex> ему не принадлежит.<br><br>
:: (Случай, когда <tex>NP</tex> принадлежит паросочетанию <tex>M'</tex> полностью симметричен.)<br><br>
+
: Поскольку паросочетание <tex>M'</tex> получается из <tex>M</tex> изменением вдоль дополняющей цепи <tex>(y \rightsquigarrow z)</tex>, в паросочетание <tex>M</tex> входило ребро <tex>NP(MP)</tex>, а ребро <tex>MP(NP)</tex> нет.
: Поскольку паросочетание <tex>M'</tex> получается из <tex>M</tex> изменением вдоль дополняющей цепи <tex>(y \rightsquigarrow z)</tex>, в паросочетание <tex>M</tex> входило ребро <tex>NP</tex>, а ребро <tex>MP</tex> нет.
+
: Кроме того, ребро <tex>QP</tex> не лежит ни в исходном паросочетании <tex>M</tex>, ни в паросочетании <tex>M'</tex>, в противном случае оказалось бы, что вершина <tex>p</tex> инцидентна нескольким ребрам из паросочетания, что противоречит определению паросочетания.<br><br>
: Кроме того, ребро <tex>QP</tex> не лежит ни в исходном паросочетании <tex>M</tex>, ни в паросочетании <tex>M'</tex>, в противном случае оказалось бы, что вершина <tex>p</tex> инцидентна нескольким рёбрам из паросочетания, что противоречит определению паросочетания.<br><br>
 
 
:Тогда заметим, что цепь <tex>(x \rightsquigarrow z)</tex>, полученная объединением цепей <tex>(x \rightsquigarrow p)</tex> и <tex>(p \rightsquigarrow z)</tex>, по определению будет дополняющей в паросочетании <tex>M</tex>, что приводит к противоречию, поскольку в паросочетании <tex>M</tex> из вершины <tex>x</tex> не существует дополняющей цепи.
 
:Тогда заметим, что цепь <tex>(x \rightsquigarrow z)</tex>, полученная объединением цепей <tex>(x \rightsquigarrow p)</tex> и <tex>(p \rightsquigarrow z)</tex>, по определению будет дополняющей в паросочетании <tex>M</tex>, что приводит к противоречию, поскольку в паросочетании <tex>M</tex> из вершины <tex>x</tex> не существует дополняющей цепи.
 
}}
 
}}
  
 
==Алгоритм==
 
==Алгоритм==
Задан граф <tex>G\langle V, E \rangle</tex>, про который известно, что он двудольный, но разбиение не задано явно. Требуется найти наибольшее паросочетание в нём
+
:Алгоритм просматривает все вершины графа по очереди, запуская из каждой обход (в глубину или в ширину), пытающийся найти увеличивающую цепь, начинающуюся в этой вершине.
  
Алгоритм можно описать так: сначала возьмём пустое паросочетание, а потом — пока в графе удаётся найти увеличивающую цепь, — будем выполнять чередование паросочетания вдоль этой цепи, и повторять процесс поиска увеличивающей цепи. Как только такую цепь найти не удалось — процесс останавливаем, — текущее паросочетание и есть максимальное.
+
:Краткое описание алгоритма:
 +
:* Возьмём пустое паросочетание
 +
:* Разобьем граф на две доли
 +
:* Проходя по всем вершинам первой доли пытаемся найти увеличивающую цепь
 +
:* Если удается найти увеличивающую цепь, выполняем чередование паросочетания вдоль этой цепи
 +
:* Повторяем процесс поиска увеличивающей цепи
 +
:* Найденное паросочетание и является максимальным
  
В массиве <tex>\mathtt{matching}</tex> хранятся паросочетания <tex> (v, \mathtt{matching}[v]) </tex>  (Если паросочетания с вершиной <tex> v </tex> не существует, то <tex> \mathtt{matching}[v]= -1</tex>). А <tex>used</tex> — обычный массив "посещённостей" вершин в обходе в глубину (он нужен, чтобы обход в глубину не заходил в одну вершину дважды).
 
Функция <tex> \mathrm{dfs} </tex> возвращает  <tex>true</tex>, если ей удалось найти увеличивающую цепь из вершины <tex>v</tex>, при этом считается, что эта функция уже произвела чередование паросочетания вдоль найденной цепи.
 
  
Внутри функции просматриваются все рёбра, исходящие из вершины <tex>v</tex>, и затем проверяется: если это ребро ведёт в ненасыщенную вершину <tex> to</tex>, либо если эта вершина <tex>to</tex> насыщена, но удаётся найти увеличивающую цепь рекурсивным запуском из <tex>\mathtt{matching}[to]</tex>, то мы говорим, что мы нашли увеличивающую цепь, и перед возвратом из функции с результатом <tex>true</tex> производим чередование в текущем ребре: перенаправляем ребро, смежное с <tex>to</tex>, в вершину <tex> v</tex>.
+
:Будем считать, что граф уже разбит на две доли.
 +
:Просматриваем все вершины <tex>v</tex> первой доли графа <tex>v = 1 ... n_1</tex>:
 +
:*Если текущая вершина уже насыщена текущим паросочетанием (т.е. уже выбрано какое-то смежное ей ребро), то эту вершину пропускаем
 +
:*Иначе — алгоритм пытается насытить эту вершину, для чего запускается поиск увеличивающей цепи, начинающейся с этой вершины.
  
В основной программе сначала указывается, что текущее паросочетание — пустое (массив <tex> \mathtt{matching}</tex> заполняется числами <tex>-1</tex>). Затем перебирается вершина  <tex>v </tex>, и из неё запускается обход в глубину <tex> \mathrm{dfs} </tex>, предварительно обнулив массив <tex> used</tex>.
 
  
Стоит заметить, что размер паросочетания легко получить как число вызовов <tex> \mathrm{dfs} </tex> в основной программе, вернувших результат <tex> true </tex>. Само искомое максимальное паросочетание содержится в массиве <tex> \mathtt{matching}</tex>.
+
:Рассмотрим поиск увеличивающей цепи обходом в глубину.
После того, как все вершины <tex>v \in V</tex> будут просмотрены, текущее паросочетание будет максимальным.
+
:* Изначально обход в глубину стоит в текущей ненасыщенной вершине <tex>v</tex> первой доли.
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше.<br>
+
:* Просматриваем все рёбра из этой вершины, пусть текущее ребро — <tex>(v, to)</tex>.
 +
:* Если вершина <tex>to</tex> ещё не насыщена паросочетанием, то, значит, мы смогли найти увеличивающую цепь: она состоит из единственного ребра <tex>(v, to)</tex>.
 +
:** Включаем это ребро в паросочетание и прекращаем поиск увеличивающей цепи из вершины <tex>v</tex>.
 +
:* Иначе, — если уже насыщена каким-то ребром <tex>(p, to)</tex> и не посещена, то попытаемся пройти вдоль этого ребра: тем самым мы попробуем найти увеличивающую цепь, проходящую через рёбра <tex>(v, t_0), (t_0, p)</tex>. Для этого просто перейдем в нашем обходе в вершину <tex>p</tex>.
 +
:** Пробуем найти увеличивающую цепь из вершины <tex>p</tex>.
  
==Реализация==
+
: Этот обход, запущенный из вершины <tex>v</tex>, либо найдёт увеличивающую цепь, и тем самым насытит вершину, либо же такой увеличивающей цепи не найдёт (и, следовательно, эта вершина  уже не сможет стать насыщенной).
  
* Граф <tex>G\langle V, E \rangle</tex> хранится в матрице смежности <tex>g[i][j]</tex> размера <tex>n </tex> на <tex>n</tex>
+
: После того, как все вершины <tex>v = 1 ... n_1</tex> будут просмотрены, текущее паросочетание будет максимальным.
*<tex>n  = |V|</tex>
 
  
'''bool''' dfs(v: '''int'''):
+
: Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы Бержа]] и теоремы, описанной выше.<br>
    '''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''
 
  
 +
: Граф <tex>G</tex> хранится списками смежности <tex>g[][]</tex>
 +
: Функция <tex>dfs(v)</tex> - обход в глубину, возвращает <tex>true</tex> если есть увеличивающая цепь из вершины <tex>v</tex>.
 +
: В массиве <tex>mt</tex> хранятся паросочетания. Паросочетание есть ребро <tex>(i, mt[i])</tex>.
  
  function '''main'''():
+
 
     fill(matching, -1)
+
bool dfs(int v)
     '''for''' i = 1..n
+
{
          fill(used, ''false'')
+
    if (used[v])
          dfs(i)
+
        return false;
     '''for''' i = 1..n
+
          '''if''' (matching[i] != -1)
+
    used[v] = true;
              print(i, " ", matching[i])
+
    for (int i = 0; i < g[v].size(); i++)
 +
    {
 +
        int to = g[v][i];
 +
        if (mt[to] == -1 || dfs(mt[to]))
 +
        {
 +
            mt[to] = v;
 +
            return true;
 +
        }
 +
    }
 +
    return false;
 +
  }
 +
 +
int main()
 +
{
 +
    ... чтение графа ...
 +
     mt.assign (k, -1);
 +
     for (int v = 0; v < n; v++)
 +
    {
 +
        used.assign(n, false);
 +
        dfs(v);
 +
    }
 +
 +
     for (int i = 0; i < k; i++)
 +
        if (mt[i] != -1)
 +
            ... вывод ...
 +
 +
}
  
 
==Время работы==
 
==Время работы==
:Итак, алгоритм Куна можно представить как серию из  <tex>n</tex> запусков обхода в глубину на всём графе.
+
:Итак, алгоритм Куна можно представить как серию из  <tex>n_1</tex> запусков обхода в глубину на всём графе.
:Следовательно, всего этот алгоритм исполняется за время <tex>O(nm)</tex>, где <tex>m</tex> {{---}} количество рёбер, что в худшем случае есть <tex>O(n^3)</tex>
+
:Следовательно, всего этот алгоритм исполняется за время <tex>O(nm)</tex>, где <tex>m</tex> {{---}} количество ребер, что в худшем случае есть <tex>O(n^3)</tex>.
:Если явно задано разбиение графа на две доли размером <tex>n_1</tex> и <tex>n_2</tex>, то можно запускать <tex>\mathtt{dfs}</tex> только из вершин первой доли, поэтому весь алгоритм исполняется за время <tex>O(n_1m)</tex>. В худшем случае это составляет <tex>O(n_1^2n_2).</tex>
 
  
==Ссылки==
 
  
* [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]]
+
:Более точная оценка:
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
+
:В описанной выше реализации запуски обхода в глубину/ширину происходят только из вершин первой доли, поэтому весь алгоритм исполняется за время <tex>O(n_1)</tex> , где <tex>n_1</tex> — число вершин первой доли. В худшем случае это составляет <tex>O(n_1^2n_2)</tex>,  где <tex>n_2</tex> — число вершин второй доли.
  
==Источники информации==
+
==Источники==
*[http://e-maxx.ru/algo/kuhn_matching MAXimal :: algo :: Алгоритм Куна нахождения наибольшего паросочетания]<br>
+
:[http://e-maxx.ru/algo/kuhn_matching MAXimal :: algo :: Алгоритм Куна нахождения наибольшего паросочетания]<br>
* Асанов М., Баранский В., Расин В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы — СПб.: Издательство "Лань", 2010. — 291 стр.
+
: Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы — СПб.: Издательство "Лань", 2010. — 291 стр.
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о паросочетании]]
 
[[Категория: Задача о паросочетании]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: