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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
м (Алгоритм)
(не показаны 82 промежуточные версии 9 участников)
Строка 1: Строка 1:
 +
==Теорема==
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
  Если из вершины х не существует дополняющей цепи относительно паросочетания М, то если  паросочетание М' получается из М изменением вдоль дополняющей цепи, то из х не существует дополняющей цепи в М'.
+
  Если из вершины <tex>x</tex> не существует [[Теорема о максимальном паросочетании и дополняющих цепях|дополняющей цепи]] относительно паросочетания <tex>M</tex> и паросочетание <tex>M'</tex> получается из <tex>M</tex> изменением вдоль дополняющей цепи, тогда из <tex>x</tex> не существует дополняющей цепи в <tex>M'</tex>.
|proof=Доказательство от противного! Допустим, что из х появилась дополняющая цепь относительно M'. Рассмотрим изменения, которые мы внесли в М вдоль дополняющей цепи, чтобы получить паросочетание М'. В этой цепи все промежуточные вершины были насыщенными, а концы свободные. После изменения вдоль этой цепи все вершины, лежащие на этой цепи станут насыщенными. Тогда появившаяся дополняющая цепь должна проходить хотя бы через одну из концевых вершин в той дополняющей цепи, относительно которой вносили изменения, поскольку иначе такая же дополняющая цепь была и в паросочетании М. Однако поскольку в паросочетании М концевые вершины не насыщены, то из вершины х в паросочетании М есть все равно есть дополняющая цепь. Надо рассмотреть часть дополняющей цепи В М', ограниченную концом текущей дополняющей цепи и концом той дополняющей цепи, вдоль которой вносили изменения, такую что вершина х будет промежуточной. Легко заметить что в такой цепи все промежуточные вершины насыщенные, а концы свободны, поэтому она является дополняющей. Значит, мы пришли к противоречию, поскольку в паросочетании М нет дополняющих цепей из вершины х.
+
|proof=
 +
[[Файл:Kuhn2.png|thumb|right|300x300px|Рисунок 1.]]
 +
[[Файл:Kuhn1.png|thumb|right|300x300px|Рисунок 2.<br>Пунктиром обозначен путь между двумя вершинами. Ребро красного цвета лежит в паросочетании, а черного - нет.]]
 +
: Доказательство от противного.<br><br>
 +
: Допустим в паросочетание внесли изменения вдоль дополняющей цепи <tex>(y \rightsquigarrow z)</tex> и из вершины <tex>x</tex> появилась дополняющая цепь.
 +
: Заметим, что эта дополняющая цепь должна вершинно пересекаться с той цепью, вдоль которой вносились изменения, иначе такая же дополняющая цепь из <tex>x</tex> существовала и в исходном паросочетании.<br><br>
 +
: Пусть <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>M'</tex>, тогда <tex>NP</tex> ему не принадлежит.<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</tex>, а ребро <tex>MP</tex> нет.
 +
: Кроме того, ребро <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>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. Обозначим доли исходного графа как <tex>L</tex> и <tex>R</tex>. <br>
+
Задан граф <tex>G\langle V, E \rangle</tex>, про который известно, что он двудольный, но разбиение не задано явно. Требуется найти наибольшее паросочетание в нём
1) Будем искать путь из <tex>s</tex> в <tex>t</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> \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> будут просмотрены, текущее паросочетание будет максимальным.
 +
Корректность алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы о максимальном паросочетании и дополняющих цепях]] и теоремы, описанной выше.<br>
 +
 
 +
==Реализация==
 +
 
 +
* Граф <tex>G\langle V, E \rangle</tex> хранится в матрице смежности <tex>g[i][j]</tex> размера <tex>n </tex> на <tex>n</tex>
 +
*<tex>n  = |V|</tex>
 +
 
 +
'''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])
 +
 
 +
==Время работы==
 +
:Итак, алгоритм Куна можно представить как серию из <tex>n</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>
  
2) Если путь найден, инвертируем все ребра на пути.
+
==Ссылки==
  
3) Если путь не был найден, значит текущее паросочетание является максимальным и алгоритм завершает работу. Иначе переходим к пункту 1)
+
* [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]]
 +
* [[Алгоритм Форда-Фалкерсона для поиска максимального паросочетания|Алгоритм Форда-Фалкерсона для поиска максимального паросочетания]]
  
В любой момент времени текущим паросочетанием будет множество ребер, направленных из <tex>R</tex> в <tex>L</tex>. Корректность работы алгоритма следует из [[Теорема о максимальном паросочетании и дополняющих цепях|теоремы Бержа]] и доказанной выше теоремы.
+
==Источники информации==
 +
*[http://e-maxx.ru/algo/kuhn_matching MAXimal :: algo :: Алгоритм Куна нахождения наибольшего паросочетания]<br>
 +
* Асанов М., Баранский В., Расин В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы — СПб.: Издательство "Лань", 2010. — 291 стр.
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Задача о паросочетании]]

Версия 22:18, 22 января 2017

Теорема

Теорема:
Если из вершины [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\langle V, E \rangle[/math], про который известно, что он двудольный, но разбиение не задано явно. Требуется найти наибольшее паросочетание в нём

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

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

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

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

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

Реализация

  • Граф [math]G\langle V, E \rangle[/math] хранится в матрице смежности [math]g[i][j][/math] размера [math]n [/math] на [math]n[/math]
  • [math]n = |V|[/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 i = 1..n
         fill(used, false)
         dfs(i)
    for i = 1..n
         if (matching[i] != -1)
              print(i, " ", matching[i])

Время работы

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

Ссылки

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