Алгоритм сжатия цветков

Если дан граф G=(V, E) и паросочетание M для G, вершина v голая (не покрыта паросочетанием), если нет ребра в M, инцидентного v. Путь в G является чередующейся цепью, если её рёбра попеременно не принадлежат M и содержатся в M. Увеличивающий путь P — это чередующаяся цепь, которая начинается и кончается голыми вершинами. Заметим, что число не принадлежащих паросочетанию вершин в увеличивающем пути больше на единицу числа рёбер, принадлежащих паросочетанию, а потому число рёбер в увеличивающем пути нечётно. Увеличение паросочетаний вдоль пути P — это операция замены множества M на новое паросочетание ${\displaystyle M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)}$.

По лемме Бержа, паросочетание M является наибольшим тогда и только тогда, когда нет M-увеличивающего пути в G[5][6]. Следовательно, либо паросочетание является наибольшим, либо его можно увеличить. Таким образом, начав с некоторого паросочетания, мы можем вычислить наибольшее паросочетание путём увеличения текущего паросочетания с помощью увеличенного пути. Можно формализовать алгоритм следующим образом

   ВХОД:  Граф G, начальное паросочетание M на G
   ВЫХОД: наибольшее паросочетание M* на G
A1 function найти_наибольшее_паросочетание(G, M) : M*
A2     ${\displaystyle P\leftarrow }$ найти_увеличивающий_путь(G, M)
A3     if P не пустое then
A4          return найти_наибольшее_паросочетание(G, увеличиваем M вдоль P)
A5     else
A6          return M
A7     end if
A8 end function

Нам нужно описать, каким образом увеличивающие пути могут быть эффективно построены. Подпрограмма их поиска использует цветки и стягивание.

Если дан граф G=(V, E) и паросочетание M графа G, то цветок B — это цикл в G, состоящий из 2k + 1 рёбер, из которых в точности k принадлежат M и в котором есть вершина v (база) такая, что существует чередующаяся цепь чётной длины (стебель) из v в голую вершину w.

Нахождение цветков:

• Просматриваем граф, начиная с голой вершины;
• Начав с этой вершины, помечаем её как внешнюю «o»;
• Попеременно помечаем вершины как внутренние «i» и как внешние «o» так, что никакие две смежные вершины не имеют одну и ту же пометку;
• Если мы завершаем с двумя смежными вершинами, помеченными как внешние «o», мы имеем цикл нечётной длины, а следовательно, цветок[7].

Определим сжатый граф G’ как граф, полученный из G путём стягивания всех рёбер цветка B, и определим сжатое паросточетание M’ как паросочетание графа G’, соответствующее M.

G’ имеет M’-увеличивающий путь тогда и только тогда, когда G имеет M-увеличивающий путь, а тогда любой M’-увеличивающий путь P’ в G’ может быть поднят до M-увеличивающего пути в G путём восстановления цветка B, стянутого ранее, так что сегмент пути P’ (если такой есть), проходящий через v_B заменяет на подходящий сегмент, проходящий через B[8]. Более детально:

• Если P’ проходит через сегмент ${\displaystyle u\to v_{B}\to w}$ in G’, то этот сегмент заменяется на сегмент ${\displaystyle u\to (u'\to \dots \to w')\to w}$ в G, где вершины цветка u’ и w’ и сторона цветка B, ${\displaystyle (u'\to \dots \to w')}$, идущая от u’ в w’ выбираются так, чтобы новый путь оставался чередующимся (u’ голая по отношению к ${\displaystyle M\cap B}$, ${\displaystyle \{w',w\}\in E\setminus M}$).

• Если P’ имеет конечный пункт v_B, то сегмент пути ${\displaystyle u\to v_{B}}$ в G’ заменяется сегментом ${\displaystyle u\to (u'\to \dots \to v')}$ в G, где вершины цветка u’ и v’ и сторона цветка B, ${\displaystyle (u'\to \dots \to v')}$, идущая от u’ в v’, выбирается так, чтобы путь был чередующимся (v’ голая, ${\displaystyle \{u',u\}\in E\setminus M}$).

Тогда цветок может быть сжат и поиск может быть продолжен по сжатым графам. Это сжатие является сердцем алгоритма Эдмондса.

Поиск увеличивающего пути использует дополнительную структуру данных, представляющую собой лес F, индивидуальные деревья которого соответствуют порциям графа G. Фактически, лес F тот же самый, что и применяемый для поиска наибольших паросочетаний в двудольных графах (без необходимости стягивания цветков). На каждой итерации алгоритм либо (1) находит увеличивающий путь, либо (2) находит цветок и осуществляет рекурсию в сжатый граф, либо (3) делается вывод, что увеличивающего пути не существует. Дополнительная структура строится посредством инкрементальной процедуры, которая обсуждается ниже[8].

Процедура построения просматривает вершины v и рёбра e графа G и инкрементально обновляет F соответствующим образом. Если v находится в дереве T леса, мы через root(v) обозначим корень дерева T. Если и u, и v лежат в том же дереве T в F, через distance(u, v) обозначим длину единственного пути из u в v в дереве T.

    ВХОД:  Граф G, паросочетание M в G
    ВЫХОД: Увеличивающий путь P в G или пустой путь, если такого пути не найдено
B01 function найти_ увеличивающий_путь(G, M):P
B02   ${\displaystyle F\leftarrow }$ пустой лес
B03   делаем все вершины и рёбра непомеченными в G, помечаем все рёбра M
B05   for each голой вершины v do
B06     создаём дерево из одной вершины {v} и добавляем дерево в F
B07   end for
B08   while имеется непомеченная вершина v в F с чётным distance(v, root(v)) do
B09     while существует непомеченное ребро e={v, w} do
B10       if w не в F then
            // w входит в паросочетание, так что добавляем ребро, 
            // покрывающее e и w в F
B11         ${\displaystyle x\leftarrow }$ сочетается с вершиной w в M
B12         добавляем рёбра {v,w} и {w,x} в дерево для v
B13       else
B14         if distance(w, root( w )) нечётно then
              // не делаем ничего.
B15         else
B16           if root(v) ≠ root(w) then
                // Рапортуем о увеличивающем пути в F ${\displaystyle \cup \{e\}}$.
B17             ${\displaystyle P\leftarrow }$ путь (${\displaystyle root(v)\to \dots \to v)\to (w\to \dots \to root(w)}$)
B18             return P
B19           else
                // Стягиваем цветок в G и ищем путь в сжатом графе.
B20             ${\displaystyle B\leftarrow }$ цветок, образованный e и рёбрами пути ${\displaystyle v\to w}$ в T
B21             ${\displaystyle G',M'\leftarrow }$ сжимаем G и M путём стягивания цветка B
B22             ${\displaystyle P'\leftarrow }$ найти_ увеличивающий_путь ${\displaystyle (G',M')}$
B23             ${\displaystyle P\leftarrow }$ поднимаем P’ в G
B24             return P
B25           end if
B26         end if
B27       end if
B28       помечаем ребро e
B29     end while
B30     помечаем вершину v
B31   end while
B32   return пустой путь
B33 end function

• Алгоритм Эдмондса нахождения наибольшего паросочетания в произвольных графах
• Алгоритм вырезания соцветий для нахождения наибольшего паросочетания в недвудольном графе