Алгоритм вырезания соцветий — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Эдмондса)
м (rollbackEdits.php mass rollback)
 
(не показано 17 промежуточных версий 9 участников)
Строка 1: Строка 1:
 
== Паросочетание в недвудольном графе==
 
== Паросочетание в недвудольном графе==
  
{{Определение
+
Рассмотрим неориентированный невзвешенный [[Основные определения теории графов|граф]] <tex> G =\langle V, E \rangle </tex>, где <tex>V </tex> {{---}} множество [[Основные определения теории графов| вершин]], <tex>E </tex> {{---}} множество [[Основные определения теории графов|рёбер]]. Требуется найти в нём максимальное паросочетание.
|definition= '''Соцветие''' <tex>B</tex> графа <tex>G=(V,E)</tex> - цикл, состоящий из <tex>2k + 1</tex> ребер. }}
+
 
{{Определение
+
Приведём пример, на котором [[Алгоритм Куна для поиска максимального паросочетания|алгоритм Куна]] работать не будет. Рассмотрим граф <tex>G</tex> с множеством вершин <tex>V={1,2,3,4} </tex>, и множеством рёбер {{---}}<tex>E={\langle 1,2 \rangle, \langle 2, 3 \rangle, \langle 3, 1 \rangle, \langle 2, 4 \rangle}</tex> и пусть ребро <tex>\langle 2, 3\rangle</tex> взято в паросочетание. Тогда при запуске из вершины <tex>1</tex>, если обход пойдёт сначала в вершину <tex>2</tex>, то он зайдёт в тупик в вершине <tex>3</tex>, вместо того чтобы найти увеличивающую цепь <tex>1-3-2-4</tex>. Как видно на этом примере, основная проблема заключается в том, что при попадании в цикл нечётной длины, обход может пойти по циклу в неправильном направлении.
|definition= '''Cжатие соцветия''' - граф <tex>G'</tex>, полученный из <tex>G</tex> сжатием всего нечётного цикла в одну псевдо-вершину (соответственно, все рёбра, инцидентные вершинам этого цикла, становятся инцидентными псевдо-вершине).}}
 
{{Определение
 
|definition= '''База соцветия''' - вершина соцветия, в которую входит ребро не из данного соцветия.}}
 
  
 
== Теорема Эдмондса ==
 
== Теорема Эдмондса ==
Строка 12: Строка 9:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Пусть в графе <tex>G</tex> существует соцветие <tex>B</tex>.<br />
+
Пусть даны граф <tex>G</tex>, паросочетание <tex>M</tex> в <tex>G</tex> и цикл <tex>Z</tex> длины <tex>2k+1</tex>, содержащий <tex>k</tex> рёбер паросочетания <tex>M</tex> и вершинно непересекающийся с остальными рёбрами из <tex>M</tex>. Построим новый граф <tex>G'</tex> из графа <tex>G</tex>, сжимая цикл <tex>Z</tex> до единичной вершины, при этом все ребра, инцидентные вершинам этого цикла, становятся инцидентными вершине в новом графе. Тогда паросочетание <tex>M -E(Z)</tex>, где <tex>E(z)</tex> {{---}} ребра, инцидентные циклу, является наибольшим в <tex>G'</tex> тогда и только тогда, когда М {{---}} наибольшее паросочетание в <tex>G</tex>
Тогда в <tex>G</tex> существует удлиняющий путь тогда и только тогда, когда существует удлиняющий путь в <tex>G\setminus B</tex>
 
 
|proof=
 
|proof=
Пусть граф <tex>G'</tex> - граф, полученный <tex>G</tex> сжатием соцветия <tex>B</tex> в псевдо-вершину <tex>B'</tex>.<br />
+
Предположим, что <tex>M</tex> не является наибольшим паросочетанием в <tex>G</tex>, тогда в силу [[Теорема о максимальном паросочетании и дополняющих_цепях|теоремы о максимальном паросочетании и дополняющих цепях]] существует увеличивающая относительно <tex>M</tex> цепь <tex>P</tex>. Если <tex>P</tex> не пересекается с <tex>Z</tex>, то цепь является увеличивающей относительно <tex>M'</tex> и в графе <tex>G'</tex>, а значит, <tex>M'</tex> не может быть наибольшим паросочетанием. Поэтому предположим, что цепь <tex>P</tex> пересекается с <tex>Z</tex>. Заметим, что хотя бы одна концевая вершина цепи <tex>P</tex> не лежит на <tex>Z</tex>, обозначим её через <tex>u</tex>. Тогда пройдём по цепи <tex>P</tex>, начиная с <tex>u</tex> до первой встречной вершины на <tex>Z</tex>, обозначим её через <tex>v</tex>. Тогда, при сжатии цикла <tex>Z</tex>, участок <tex>P[u,v]</tex> отобразится на увеличивающую цепь относительно <tex>M'</tex>, то есть <tex>M'</tex> не является максимальным паросочетанием, что противоречит нашему предположению.
Заметим, что достаточно рассматривать случай, когда база соцветия является свободной вершиной (не принадлежащей паросочетанию). В противном случае в базе соцветия оканчивается чередующийся путь чётной длины, начинающийся в свободной вершине. Прочередовав паросочетание вдоль этого пути, мощность паросочетания не изменится, а база соцветия станет свободной вершиной.  
 
  
<tex>\Rightarrow</tex>
+
Теперь допустим, что <tex>M'</tex> не является наибольшим паросочетанием в графе <tex>G'</tex>. Обозначим через <tex>N'</tex> паросочетание в <tex>G'</tex>, мощности большей, чем <tex>M'</tex>. Восстановим граф <tex>G</tex>, тогда <tex>N'</tex> будет соответствовать некоторому паросочетанию в <tex>G</tex>, покрывающему не более одной вершины в <tex>Z</tex>. Следовательно паросочетание <tex>N'</tex> можно увеличить, используя <tex>k</tex> рёбер цикла <tex>Z</tex>, и получить паросочетание <tex>N</tex>, размера <tex>|N| = |N'|+k > |M'|+k = |M|</tex>, то есть <tex>M</tex> не является наибольшим паросочетанием в <tex>G</tex>, приходим к противоречию. Таким образом теорема доказана.
 +
}}
  
Пусть путь <tex>P</tex> является удлиняющим в графе <tex>G</tex>. Если <tex>P</tex> не проходит через <tex>B</tex>, то тогда он будет удлиняющим и в графе <tex>G'</tex>. <br />
+
Для простоты описания алгоритма введём некоторые определения.
Пусть  проходит через <tex>B</tex>. Тогда путь <tex>P</tex> представляет собой некоторый путь <tex>P_1</tex>, не проходящий по вершинам <tex>B</tex>, плюс некоторый путь <tex>P_2</tex>, проходящий по вершинам <tex>B</tex> и, возможно, другим вершинам. Но тогда путь <tex>P_1 + B'</tex>  будет являться удлиняющим путём в графе <tex>G'</tex>, что и требовалось доказать.
+
{{Определение
 +
|definition= Будем называть '''соцветием''' <tex>B</tex> графа <tex>G</tex> его цикл нечётной длины.
  
<tex>\Leftarrow</tex>
+
'''Cжатием соцветия''' назовём граф <tex>G'</tex>, полученный из <tex>G</tex> сжатием всего нечётного цикла в одну псевдо-вершину. Все рёбра, инцидентные вершинам этого цикла, становятся инцидентными псевдо-вершине в новом графе.
  
Пусть путь <tex>P</tex> является удлиняющим путём в графе <tex>G'</tex>. Если <tex>P</tex> не проходит через <tex>B'</tex>, то тогда он будет удлиняющим и в графе <tex>G</tex>. <br />
+
'''База соцветия''' - вершина соцветия, в которую входит ребро не из данного соцветия.
 +
}}
  
Рассмотрим отдельно случай, когда <tex>P</tex> начинается со сжатого соцветия <tex>B'</tex>, т.е. имеет вид <tex>(B', c, ...)</tex>. Тогда в соцветии <tex>B</tex> найдётся соответствующая вершина <tex>v</tex>, которая связана ребром с <tex>c</tex>. Заметим, что из базы соцветия всегда найдётся чередующийся путь чётной длины до вершины <tex>v</tex>. Учитывая всё вышесказанное, получаем, что путь <tex>P_1(b,...v,...c,..)</tex> является увеличивающим путём в графе <tex>G</tex>.
+
[[Файл:blossom1.jpg|300px|Рис. 1]]
 
+
[[Файл:blossom2.jpg|300px|Рис. 2]]
Пусть теперь путь <tex>P</tex> проходит через псевдо-вершину <tex>B'</tex>, но не начинается и не заканчивается в ней. Тогда в <tex>P</tex> есть два ребра, проходящих через <tex>B'</tex>, пусть это <tex>(a,B')</tex> и <tex>(B',c)</tex>. Одно из них обязательно должно принадлежать паросочетанию, однако, так как база цветка не насыщена, а все остальные вершины цикла цветка  насыщены рёбрами цикла, то мы приходим к противоречию (это эквивалентно [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах|случаю отсутствия ребра из <tex>R^-</tex> в <tex>L^+</tex>]]). Таким образом, этот случай просто невозможен. Теорема доказана.
 
}}
 
  
 
==Алгоритм вырезания соцветий==
 
==Алгоритм вырезания соцветий==
 +
Опишем алгоритм, позволяющий находить максимальное паросочетание для произвольного графа <tex>G</tex>. Из теоремы Эдмондса понятно, что необходимо рассматривать паросочетание в сжатом графе, где его можно найти, к примеру, при помощи алгоритма [[Алгоритм Куна для поиска максимального паросочетания|Куна]], а после восстанавливать паросочетание в исходном графе.
  
Пусть дан произвольный граф <tex>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. <br>
+
Основную сложность представляют операции сжатия и восстановления цветков. Чтобы эффективно это делать, для каждой вершины необходимо хранить указатель на базу цветка, которому она принадлежит, или на себя в противном случае. Предположим, что для поиска паросочетаний в сжатом графе, мы используем обход в ширину. Тогда на каждой итерации алгоритма будет строиться дерево обхода в ширину, причём путь в нём до любой вершины будет являться чередующимся путём, начинающимся с корня этого дерева. Будем класть в очередь только те вершины, расстояние от корня до которых в дереве путей чётно. Также для каждой вершины, расстояние до которой нечётно, в массиве предков <tex>p[]</tex> необходимо хранить её предка {{---}} чётную вершину. Заметим, что если в процессе обхода в ширину мы из текущей вершины <tex>v</tex> приходим в такую вершину <tex>u</tex>, что она является корнем  или принадлежит паросочетанию и дереву путей, то обе эти вершины принадлежат некоторому цветку. Действительно, при выполнении этих условий эти вершины являются чётными вершинами, следовательно расстояние от них до их наименьшего общего предка имеет одну чётность. Найдём наименьшего общего предка <tex>lca(u,v)</tex> вершин <tex>u</tex>, <tex>v</tex>, который является базой цветка. Для нахождения самого цикла необходимо пройтись от вершин <tex>u</tex>, <tex>v</tex> до базы цветка. В явном виде цветок сжимать не будем, просто положим в очередь обхода в ширину все вершины, принадлежащие цветку. Также для всех чётных вершин (за исключением базы) назначим предком соседнюю вершину в цикле, а для вершин <tex>u</tex> и <tex>v</tex> назначим предками друг друга. Это позволит корректно восстановить цветок в случае, когда при восстановлении увеличивающего пути мы зайдем в нечётную вершину цикла.
[[Файл:blossom1.jpg|thumb|right|Рис. 1]]
 
 
 
 
 
===Общая идея===
 
 
 
[[Файл:blossom2.jpg|thumb|right|Рис. 2]]
 
#Сжимаем все соцветия
 
#Находим паросочетания в полученном графе поиском в глубину/ширину.
 
#Разжимаем соцветия, восстанавливая паросочетание.
 
 
 
===Пошаговое представление===
 
 
 
 
 
Алгоритм строит лес(используя поиск в глубину или ширину), содержащий деревья удлиняющих путей, корнями которых являются вершины не из паросочетания.
 
 
 
Разобьем каждое неориентированное ребро <tex>(w, v)</tex> на два ориентированных ребра <tex>(w, v)</tex> и <tex>(v, w)</tex>.  
 
Каждое ребро может принимать одно из трех состояний: непосещенное, четное и нечетное.
 
Для каждой вершины из паросочетания <tex>v</tex> в <tex>mate(v)</tex> будем хранить вершину, смежную <tex>v</tex>.
 
Также для каждой вершины <tex>v</tex> алгоритм в <tex>p(v)</tex> будет хранить родителя в дереве обхода.
 
 
 
Сначала пометим все вершины, включенные в паросочетание, непосещенными, все остальные - четными.
 
 
 
Пока существует удлиняющий путь или пока есть непроверенное ребро из четной вершины <tex>v</tex>:
 
#Выберем любое непроверенное ребро<tex>(v, w)</tex> из четной вершины <tex>v</tex> и проверяем:
 
#*Вершина <tex>w</tex> нечетное - ничего не делаем. Такая ситуация возникает, когда <tex>(v, w)</tex> ребро из паросочетания или не из паросочетания
 
#*Вершина <tex>w</tex> включено в паросочетание и непосещенное. Тогда помечаем <tex>w</tex> нечетным, а <tex>mate(w)</tex> четным. Присваиваем <tex>p(w) \gets v</tex>, а также <tex>p(mate(w)) \gets w</tex>
 
#*<tex>w</tex> четное; вершины <tex>w, v</tex> лежат в разных деревьях - нашли удлиняющий путь от корня дерева, содержащего вершину <tex>v</tex> до корня дерева, содержащего вершину <tex>w</tex>.
 
#*<tex>w</tex> четное; вершины <tex>w, v</tex> лежат в одном дереве - нашли соцветие. Пусть <tex>u</tex> - наименьший общий предок вершин <tex>v</tex> и <tex>w</tex>. Сожмем соцветие в псевдо-вершину <tex>b</tex>, <tex>p(b) \gets p(u)</tex>, а также для каждой вершины <tex>x</tex> в соцветии определим <tex>p(x) \gets b</tex>
 
 
 
===Псевдокод===
 
  '''Edmonds''' {
 
      '''for''' <tex>u \in V</tex>'''
 
      if (вершина u не в паросочетании)''' {
 
          '''int''' '''last_v''' = '''find_augment_path''' (u);
 
          '''if (last_v != -1)'''
 
              '''выполнить чередование вдоль пути из u в last_v;'''
 
      }
 
  }
 
 
  int find_augment_path (root) {
 
      обход в ширину:
 
        v = текущая_вершина;
 
        for <tex>(v,w) \in E</tex>
 
            если обнаружили цикл нечётной длины, сжать его
 
            если пришли в свободную вершину, return
 
            если пришли в несвободную вершину, то добавить в очередь смежную ей в паросочетании
 
      return -1;
 
    }
 
  
 
== Оценка сложности ==
 
== Оценка сложности ==
  
Всего имеется <tex>V</tex> итераций, на каждой из которых выполняется обход в ширину за <tex>O(E)</tex>, кроме того, могут происходить операции сжатия цветков — их может быть <tex>O(V)</tex>. Если уметь сжимать соцветие за <tex>O(V)</tex>, то общая асимптотика алгоритма составит <tex>O(V(E + V^2)) = O(V^3)</tex>.
+
Всего имеется <tex>V</tex> итераций, на каждой из которых выполняется обход в ширину за <tex>O(E)</tex>, кроме того, могут происходить операции сжатия цветков — их может быть <tex>O(V)</tex>. Сжатие соцветий работает за <tex>O(V)</tex>, то есть общая асимптотика алгоритма составит <tex>O(V(E + V^2)) = O(V^3)</tex>.
  
 
==Литература==
 
==Литература==
*''R. Tarjan'' '''Data Structures and Network Algorithms''' -ISBN 0898711878
+
*''Ловас, Пламмер'' '''Прикладные задачи теории графов. Теория паросочетаний в математике и физике'''
 
*[http://e-maxx.ru/algo/matching_edmonds Алгоритм Эдмондса нахождения наибольшего паросочетания в произвольных графах]
 
*[http://e-maxx.ru/algo/matching_edmonds Алгоритм Эдмондса нахождения наибольшего паросочетания в произвольных графах]
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Задача о паросочетании]]

Текущая версия на 19:21, 4 сентября 2022

Паросочетание в недвудольном графе

Рассмотрим неориентированный невзвешенный граф [math] G =\langle V, E \rangle [/math], где [math]V [/math] — множество вершин, [math]E [/math] — множество рёбер. Требуется найти в нём максимальное паросочетание.

Приведём пример, на котором алгоритм Куна работать не будет. Рассмотрим граф [math]G[/math] с множеством вершин [math]V={1,2,3,4} [/math], и множеством рёбер —[math]E={\langle 1,2 \rangle, \langle 2, 3 \rangle, \langle 3, 1 \rangle, \langle 2, 4 \rangle}[/math] и пусть ребро [math]\langle 2, 3\rangle[/math] взято в паросочетание. Тогда при запуске из вершины [math]1[/math], если обход пойдёт сначала в вершину [math]2[/math], то он зайдёт в тупик в вершине [math]3[/math], вместо того чтобы найти увеличивающую цепь [math]1-3-2-4[/math]. Как видно на этом примере, основная проблема заключается в том, что при попадании в цикл нечётной длины, обход может пойти по циклу в неправильном направлении.

Теорема Эдмондса

Теорема:
Пусть даны граф [math]G[/math], паросочетание [math]M[/math] в [math]G[/math] и цикл [math]Z[/math] длины [math]2k+1[/math], содержащий [math]k[/math] рёбер паросочетания [math]M[/math] и вершинно непересекающийся с остальными рёбрами из [math]M[/math]. Построим новый граф [math]G'[/math] из графа [math]G[/math], сжимая цикл [math]Z[/math] до единичной вершины, при этом все ребра, инцидентные вершинам этого цикла, становятся инцидентными вершине в новом графе. Тогда паросочетание [math]M -E(Z)[/math], где [math]E(z)[/math] — ребра, инцидентные циклу, является наибольшим в [math]G'[/math] тогда и только тогда, когда М — наибольшее паросочетание в [math]G[/math]
Доказательство:
[math]\triangleright[/math]

Предположим, что [math]M[/math] не является наибольшим паросочетанием в [math]G[/math], тогда в силу теоремы о максимальном паросочетании и дополняющих цепях существует увеличивающая относительно [math]M[/math] цепь [math]P[/math]. Если [math]P[/math] не пересекается с [math]Z[/math], то цепь является увеличивающей относительно [math]M'[/math] и в графе [math]G'[/math], а значит, [math]M'[/math] не может быть наибольшим паросочетанием. Поэтому предположим, что цепь [math]P[/math] пересекается с [math]Z[/math]. Заметим, что хотя бы одна концевая вершина цепи [math]P[/math] не лежит на [math]Z[/math], обозначим её через [math]u[/math]. Тогда пройдём по цепи [math]P[/math], начиная с [math]u[/math] до первой встречной вершины на [math]Z[/math], обозначим её через [math]v[/math]. Тогда, при сжатии цикла [math]Z[/math], участок [math]P[u,v][/math] отобразится на увеличивающую цепь относительно [math]M'[/math], то есть [math]M'[/math] не является максимальным паросочетанием, что противоречит нашему предположению.

Теперь допустим, что [math]M'[/math] не является наибольшим паросочетанием в графе [math]G'[/math]. Обозначим через [math]N'[/math] паросочетание в [math]G'[/math], мощности большей, чем [math]M'[/math]. Восстановим граф [math]G[/math], тогда [math]N'[/math] будет соответствовать некоторому паросочетанию в [math]G[/math], покрывающему не более одной вершины в [math]Z[/math]. Следовательно паросочетание [math]N'[/math] можно увеличить, используя [math]k[/math] рёбер цикла [math]Z[/math], и получить паросочетание [math]N[/math], размера [math]|N| = |N'|+k \gt |M'|+k = |M|[/math], то есть [math]M[/math] не является наибольшим паросочетанием в [math]G[/math], приходим к противоречию. Таким образом теорема доказана.
[math]\triangleleft[/math]

Для простоты описания алгоритма введём некоторые определения.

Определение:
Будем называть соцветием [math]B[/math] графа [math]G[/math] его цикл нечётной длины.

Cжатием соцветия назовём граф [math]G'[/math], полученный из [math]G[/math] сжатием всего нечётного цикла в одну псевдо-вершину. Все рёбра, инцидентные вершинам этого цикла, становятся инцидентными псевдо-вершине в новом графе.

База соцветия - вершина соцветия, в которую входит ребро не из данного соцветия.


Рис. 1 Рис. 2

Алгоритм вырезания соцветий

Опишем алгоритм, позволяющий находить максимальное паросочетание для произвольного графа [math]G[/math]. Из теоремы Эдмондса понятно, что необходимо рассматривать паросочетание в сжатом графе, где его можно найти, к примеру, при помощи алгоритма Куна, а после восстанавливать паросочетание в исходном графе.

Основную сложность представляют операции сжатия и восстановления цветков. Чтобы эффективно это делать, для каждой вершины необходимо хранить указатель на базу цветка, которому она принадлежит, или на себя в противном случае. Предположим, что для поиска паросочетаний в сжатом графе, мы используем обход в ширину. Тогда на каждой итерации алгоритма будет строиться дерево обхода в ширину, причём путь в нём до любой вершины будет являться чередующимся путём, начинающимся с корня этого дерева. Будем класть в очередь только те вершины, расстояние от корня до которых в дереве путей чётно. Также для каждой вершины, расстояние до которой нечётно, в массиве предков [math]p[][/math] необходимо хранить её предка — чётную вершину. Заметим, что если в процессе обхода в ширину мы из текущей вершины [math]v[/math] приходим в такую вершину [math]u[/math], что она является корнем или принадлежит паросочетанию и дереву путей, то обе эти вершины принадлежат некоторому цветку. Действительно, при выполнении этих условий эти вершины являются чётными вершинами, следовательно расстояние от них до их наименьшего общего предка имеет одну чётность. Найдём наименьшего общего предка [math]lca(u,v)[/math] вершин [math]u[/math], [math]v[/math], который является базой цветка. Для нахождения самого цикла необходимо пройтись от вершин [math]u[/math], [math]v[/math] до базы цветка. В явном виде цветок сжимать не будем, просто положим в очередь обхода в ширину все вершины, принадлежащие цветку. Также для всех чётных вершин (за исключением базы) назначим предком соседнюю вершину в цикле, а для вершин [math]u[/math] и [math]v[/math] назначим предками друг друга. Это позволит корректно восстановить цветок в случае, когда при восстановлении увеличивающего пути мы зайдем в нечётную вершину цикла.

Оценка сложности

Всего имеется [math]V[/math] итераций, на каждой из которых выполняется обход в ширину за [math]O(E)[/math], кроме того, могут происходить операции сжатия цветков — их может быть [math]O(V)[/math]. Сжатие соцветий работает за [math]O(V)[/math], то есть общая асимптотика алгоритма составит [math]O(V(E + V^2)) = O(V^3)[/math].

Литература