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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм вырезания соцветий)
(Алгоритм вырезания соцветий)
Строка 36: Строка 36:
  
 
Пусть дан произвольный граф <tex>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. <br>
 
Пусть дан произвольный граф <tex>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. <br>
 +
 +
===Общая идея===
 +
 +
#Сжимаем все соцветия
 +
#Находим паросочетания в полученном графе поиском в глубину/ширину.
 +
#Разжимаем соцветия, восстанавливая паросочетание.
 +
 +
===Пошаговое представление===
 +
  
 
Алгоритм строит лес, содержащий деревья удлиняющих путей, корнями которых являются вершины не из паросочетания.
 
Алгоритм строит лес, содержащий деревья удлиняющих путей, корнями которых являются вершины не из паросочетания.
Строка 44: Строка 53:
 
Также для каждой вершины <tex>v</tex> алгоритм в <tex>p(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;
 +
    }

Версия 23:12, 15 января 2011

Эта статья находится в разработке!

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

Определение:
Соцветие [math]B[/math] графа [math]G=(V,E)[/math] - цикл, состоящий из [math]2k + 1[/math] ребер, из которых только [math]k[/math] входят в соцветие [math]B[/math].


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


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


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

Теорема:
Пусть в графе [math]G[/math] существует соцветие [math]B[/math].
Тогда в [math]G[/math] существует удлиняющий путь тогда и только тогда, когда существует удлиняющий путь в [math]G\setminus B[/math]
Доказательство:
[math]\triangleright[/math]

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

[math]\Rightarrow[/math]

Пусть путь [math]P[/math] является удлиняющим в графе [math]G[/math]. Если [math]P[/math] не проходит через [math]B[/math], то тогда он будет удлиняющим и в графе [math]G'[/math].
Пусть проходит через [math]B[/math]. Тогда что путь P представляет собой некоторый путь [math]P_1[/math], не проходящий по вершинам [math]B[/math], плюс некоторый путь [math]P_2[/math], проходящий по вершинам [math]B[/math] и, возможно, другим вершинам. Но тогда путь [math]P_1 + B'[/math] будет являться удлиняющим путём в графе [math]G'[/math], что и требовалось доказать.

[math]\Leftarrow[/math]

Пусть путь [math]P[/math] является удлиняющим путём в графе [math]G'[/math]. Если [math]P[/math] не проходит через [math]B'[/math], то тогда он будет удлиняющим и в графе [math]G[/math].

Рассмотрим отдельно случай, когда [math]P[/math] начинается со сжатого соцветия [math]B'[/math], т.е. имеет вид [math](B', c, ...)[/math]. Тогда в соцветии [math]B[/math] найдётся соответствующая вершина [math]v[/math], которая связана ребром с [math]c[/math]. Заметим, что из базы соцветия всегда найдётся чередующийся путь чётной длины до вершины [math]v[/math]. Учитывая всё вышесказанное, получаем, что путь [math]P_1(b,...v,...c,..)[/math] является увеличивающим путём в графе [math]G[/math].

Пусть теперь путь [math]P[/math] проходит через псевдо-вершину [math]B'[/math], но не начинается и не заканчивается в ней. Тогда в [math]P[/math] есть два ребра, проходящих через [math]B'[/math], пусть это [math](a,B')[/math] и [math](B',c)[/math]. Одно из них обязательно должно принадлежать паросочетанию, однако, так как база цветка не насыщена, а все остальные вершины цикла цветка насыщены рёбрами цикла, то мы приходим к противоречию (это эквивалентно случаю отсутствия ребра из [math]R_-[/math] в [math]L_+[/math]). Таким образом, этот случай просто невозможен. Теорема доказана.
[math]\triangleleft[/math]

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

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

Общая идея

  1. Сжимаем все соцветия
  2. Находим паросочетания в полученном графе поиском в глубину/ширину.
  3. Разжимаем соцветия, восстанавливая паросочетание.

Пошаговое представление

Алгоритм строит лес, содержащий деревья удлиняющих путей, корнями которых являются вершины не из паросочетания.

Разобьем каждое неориентированное ребро [math](w, v)[/math] на два ориентированных ребра [math](w, v)[/math] и [math](v, w)[/math]. Каждое ребро может принимать одно из трех состояний: непосещенное, четное и нечетное. Для каждой вершины из паросочетания [math]v[/math] в [math]mate(v)[/math] будем хранить вершину, смежную [math]v[/math]. Также для каждой вершины [math]v[/math] алгоритм в [math]p(v)[/math] будет хранить родителя в дереве обхода.

Сначала пометим все вершины, включенные в паросочетание, непосещенными, все остальные - четными.

Пока существует удлиняющий путь или пока есть непроверенное ребро из четной вершины [math]v[/math]:

  1. Выберем любое непроверенное ребро[math](v, w)[/math] из четной вершины [math]v[/math] и проверяем:
    • Вершина [math]w[/math] нечетное - ничего не делаем. Такая ситуация возникает, когда [math](v, w)[/math] ребро из паросочетания или не из паросочетания
    • Вершина [math]w[/math] включено в паросочетание и непосещенное. Тогда помечаем [math]w[/math] нечетным, а [math]mate(w)[/math] четным. Присваиваем [math]p(w) \gets v[/math], а также [math]p(mate(w)) \gets w[/math]
    • [math]w[/math] четное; вершины [math]w, v[/math] лежат в разных деревьях - нашли удлиняющий путь от корня дерева, содержащего вершину [math]v[/math] до корня дерева, содержащего вершину [math]w[/math].
    • [math]w[/math] четное; вершины [math]w, v[/math] лежат в одном дереве - нашли соцветие. Пусть [math]u[/math] - наименьший общий предок вершин [math]v[/math] и [math]w[/math]. Сожмем соцветие в псевдо-вершину [math]b[/math], [math]p(b) \gets p(u)[/math], а также для каждой вершины [math]x[/math] в соцветии определим [math]p(x) \gets b[/math]

Псевдокод

  Edmonds {
     for [math]u \in V[/math]
     if (вершина u не в паросочетании) {
         int last_v = find_augment_path (u);
         if (last_v != -1)
             выполнить чередование вдоль пути из u в last_v;
     }
  }

  int find_augment_path (root) {
     обход в ширину:
        v = текущая_вершина;
        for [math](v,w) \in E[/math]
            если обнаружили цикл нечётной длины, сжать его
            если пришли в свободную вершину, return
            если пришли в несвободную вершину, то добавить в очередь смежную ей в паросочетании
     return -1;
   }