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

Алгоритм сжатия цветков (англ. Blossom algorithm) — алгоритм в теории графов для построения наибольших паросочетаний на графах. Алгоритм разработал Джек Эдмондс в 1961 году^[1] и опубликовал в 1965 году^[2]. Если дан граф G=(V, E) общего вида, алгоритм находит паросочетание M такое, что каждая вершина из V инцидентна не более чем одному ребру из M и |M| максимально. Паросочетание строится путём итеративного улучшения начального пустого паросочетания вдоль увеличивающих путей графа. В отличие от двудольного паросочетания ключевой новой идеей было сжатие нечётного цикла в графе (цветка) в одну вершину с продолжением поиска итеративно по сжатому графу.

Основной причиной, почему алгоритм сжатия цветков важен, является то, что он дал первое доказательство возможности нахождения наибольшего паросочетания за полиномиальное время. Другой причиной является то, что метод приводит к описанию многогранника линейного программирования для многогранника паросочетаний, что приводит к алгоритму паросочетания минимального веса^[3]. Как уточнил Александр Схрейвер, дальнейшая важность результата следует из факта, что этот многогранник был первым, доказательство целочисленности которого «не просто следовало из тотальной унимодулярности, а его описание было прорывом в комбинаторике многогранников»^[4].

Увеличивающие пути

Если дан граф G=(V, E) и паросочетание M для G, вершина v голая (не покрыта паросочетанием), если нет ребра в M, инцидентного v. Путь в G является чередующейся цепью, если её рёбра попеременно не принадлежат M и содержатся в M. Увеличивающий путь P — это чередующаяся цепь, которая начинается и кончается голыми вершинами. Заметим, что число не принадлежащих паросочетанию рёбер в увеличивающем пути больше на единицу числа рёбер, принадлежащих паросочетанию, а потому число рёбер в увеличивающем пути нечётно. Увеличение паросочетаний вдоль пути P — это операция замены множества M на новое паросочетание $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      $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’ проходит через сегмент $u\to v_{B}\to w$ in G’, то этот сегмент заменяется на сегмент $u\to (u'\to \dots \to w')\to w$ в G, где вершины цветка u’ и w’ и сторона цветка B, $(u'\to \dots \to w')$ , идущая от u’ в w’ выбираются так, чтобы новый путь оставался чередующимся (u’ голая по отношению к $M\cap B$ , $\{w',w\}\in E\setminus M$ ).

Если P’ имеет конечный пункт v_B, то сегмент пути $u\to v_{B}$ в G’ заменяется сегментом $u\to (u'\to \dots \to v')$ в G, где вершины цветка u’ и v’ и сторона цветка B, $(u'\to \dots \to v')$ , идущая от u’ в v’, выбирается так, чтобы путь был чередующимся (v’ голая, $\{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    $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 входит в паросочетание, так что добавляем ребро, 
            // покрывающее w и ребро e в F
B11          $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  $\cup \{e\}$ .
B17              $P\leftarrow$  путь ( $root(v)\to \dots \to v)\to (w\to \dots \to root(w)$ )
B18             return P
B19           else
                // Стягиваем цветок в G и ищем путь в сжатом графе.
B20              $B\leftarrow$  цветок, образованный e и рёбрами пути  $v\to w$  в T
B21              $G',M'\leftarrow$  сжимаем G и M путём стягивания цветка B
B22              $P'\leftarrow$  найти_ увеличивающий_путь  $(G',M')$ 
B23              $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

Примеры

Следующие четыре рисунка иллюстрируют выполнение алгоритма. Пунктирные линии показывают рёбра, которые в этот момент не представлены в лесе. Сначала алгоритм обрабатывает ребро, не принадлежащее лесу, которое приводит к расширению текущего леса (строки B10 — B12).

Затем удаляется цветок и сжимается граф (строи B20 — B21).

Наконец, алгоритм обнаруживает увеличивающий путь P′ в сжатом графе (строка B22) и поднимает его в исходном графе (строка B23). Заметим, что способность алгоритма стягивания цветков здесь является решающим. Алгоритм не может найти P в исходном графе прямо, поскольку только рёбра не из леса между вершинами на чётном расстоянии от корня рассматриваются в строке B17 алгоритма.

Анализ

Лес F, построенный функцией найти_увеличивающий_путь(), является чередующимся лесом^[9].

дерево T в G является чередующимся деревом относительно M, если
- T содержит ровно одну голую вершину r, называемую корнем дерева
- любая вершина на нечётном расстоянии от корня имеет ровно два инцидентных ребра в T и
- все пути из r в листья в T имеют чётные длины, их нечётные рёбра не принадлежат M, а чётные рёбра M принадлежат.
лес F в G является чередующимся лесом относительно M, если
- его связные компоненты являются чередующимися деревьями и
- любая голая вершина в G является корнем в чередующемся дереве в F.

Каждая итерация цикла, начиная со строки B09, либо добавляет вершину в дерево T в F (строка B10), либо находит увеличивающий путь (строка B17), либо находит цветок (строка B20). Легко видеть, что время работы алгоритма равно $O(|E||V|^{2})$ . Микали и Вазирани^[10] показали алгоритм, который строит наибольшее паросочетание за время $O(|E||V|^{1/2})$ .

Двудольное паросочетание

Алгоритм сводится к стандартному алгоритму для паросочетаний в двудольных графах^[6], если G является двудольным. Поскольку в этом случае нет нечётных циклов G, цветки никогда не будут найдены и можно просто удалить строки B20 — B24 алгоритма.

Взвешенное паросочетание

Задачу о паросочетаниях можно обобщить назначением весов рёбрам графа G. В этом случае задаётся вопрос о множестве M, которое даёт паросочетание с максимальным (минимальным) полным весом. Взвешенную задачу о паросочетаниях можно решить с помощью комбинаторного алгоритма, который использует невзвешенный алгоритм Эдмондса в качестве подпрограммы^[5]. Владимир Колмогоров дал эффективную имплементацию этого алгоритма на C++^[11].

Примечания

↑ Edmonds, 1961, pp. 32—54.
↑ Edmonds, 1965, pp. 449—467.
↑ Edmonds, 1965, pp. 125—130.
↑ Schrijver, 2003.
↑ ¹ ² Lovász, Plummer, 1986.
↑ ¹ ² Karp, 2006.
↑ По построению «i» помечает начало ребра из M, так что случай встречи двух смежных помеченных «i» вершин невозможен.
↑ ¹ ² Tarjan, 2002.
↑ Kenyon, Lovász, 1990.
↑ Micali, Vazirani, 1980, pp. 17—27.
↑ Kolmogorov, 2009, pp. 43—67.

Литература

Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. — Berlin, Heidelberg: Springer-Verlag, 2003. — (Algorithms and Combinatorics). — ISBN 9783540443896.
Jack Edmonds. A glimpse of heaven // History of Mathematical Programming — A Collection of Personal Reminiscences / J.K. Lenstra, A.H.G. Rinnooy Kan, A. Schrijver. — CWI, Amsterdam and North-Holland, Amsterdam, 1961. — С. 32–54.
Jack Edmonds. Paths, trees, and flowers // Can. J. Math.. — 1965. — Т. 17. — С. 449–467. — doi:10.4153/CJM-1965-045-4.
Jack Edmonds. Maximum matching and a polyhedron with 0,1-vertices // Journal of Research of the National Bureau of Standards Section B. — 1965. — Т. 69. — С. 125–130.
László Lovász, Michael D. Plummer. Matching Theory. — Akadémiai Kiadó, 1986. — ISBN 963-05-4168-8.
Richard Karp. Course Notes. U. C. Berkeley. — 2006. Архивировано 30 декабря 2008 года.
Robert. Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching // Course Notes-423: Theory of Algorithms. — Department of Computer Science, Princeton University, 2002.
Claire Kenyon, László Lovász. Algorithmic Discrete Mathematics // Technical Report CS-TR-251-90, Department of Computer Science, Princeton University. — 1990.
Blossom V: A new implementation of a minimum cost perfect matching algorithm // Mathematical Programming Computation. — 2009. — Т. 1, № 1. — С. 43–67.
Silvio Micali, Vijay Vazirani. An O(V^1/2E) algorithm for finding maximum matching in general graphs // 21st Annual Symposium on Foundations of Computer Science,. — IEEE Computer Society Press, New York, 1980. — С. 17–27.

Ссылки

[_a184686f2d65cc6a-1] Edmonds, 1961, pp. 32—54.

[_8a9423c2a5adf474-2] Edmonds, 1965, pp. 449—467.

[_aa2d88e23b72991e-3] Edmonds, 1965, pp. 125—130.

[_3d21c711b557557e-4] Schrijver, 2003.

[_807b6eac893ed17b-5] ¹ ² Lovász, Plummer, 1986.

[_3fbe43a03e701757-6] ¹ ² Karp, 2006.

[7] По построению «i» помечает начало ребра из M, так что случай встречи двух смежных помеченных «i» вершин невозможен.

[_d6dfe6571604b58d-8] ¹ ² Tarjan, 2002.

[_c492a06b43215872-9] Kenyon, Lovász, 1990.

[_878d8341da510d55-10] Micali, Vazirani, 1980, pp. 17—27.

[_61271da7eafe2b95-11] Kolmogorov, 2009, pp. 43—67.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]