Алгоритм цветения

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

Алгоритм выполняется за время $O (| E || V | 2)$ , где $| E |$ — число ребер графа, а $| V |$ — число его вершин . Лучшее время выполнения для той же задачи может быть достигнуто с помощью гораздо более сложного алгоритма Микали и Вазирани. ^[3] $O(|E|{\sqrt {|V|}})$

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

Дополняющие пути

При условии $G = (V, E)$ и соответствия $M$ из $G$ вершина $v$ открыта , если ни одно ребро $M$ не инцидентно $v$ . Путь в $G$ является чередующимся путем , если его ребра попеременно не находятся в $M$ и в $M$ (или в $M$ и не в $M$ ). Увеличивающий путь $P$ является чередующимся путем, который начинается и заканчивается в двух различных открытых вершинах. Обратите внимание, что количество несоответствующих ребер в увеличивающем пути на единицу больше количества сопоставленных ребер, и, следовательно, общее количество ребер в увеличивающем пути нечетно. Соответствующее увеличение вдоль увеличивающего пути $P$ является операцией замены $M$ новым сопоставлением

M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)

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

 ВХОД: Граф G , начальное соответствие M на G ВЫХОД: максимальное соответствие M* на G Функция
A1 find_maximum_matching ( G , M ) : M*
A2 P ← find_augmenting_path ( G , M )A3 если  P непустое, то
A4 возвращает  find_maximum_matching ( G , дополняет M по P )A5 иначе
A6 вернуть MA7 конец, если
A8 конец функции

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

Цветы и сокращения

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

В поисках цветов:

Обойти граф, начиная с открытой вершины.
Начиная с этой вершины, обозначим ее как внешнюю вершину $o$ .
Поочередно маркируйте вершины как внутренние $i$ и как внешние $o$ так, чтобы никакие две смежные вершины не имели одинаковой метки.
Если в итоге у нас останутся две смежные вершины, помеченные как внешние $o,$ то у нас будет цикл нечетной длины и, следовательно, цветение.

Определим сжатый граф $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$ в $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 функция  find_augmenting_path ( G , M ) : P
B02 F ← пустой лесB03 снять отметку со всех вершин и ребер в G , отметить все ребра M
B05 для каждой открытой вершины v  выполнить
B06 создать одноэлементное дерево { v } и добавить дерево к F
B07 завершить для
B08 пока есть неотмеченная вершина v в F с расстоянием (v, root(v)) четным выполнить
B09 пока существует неотмеченное ребро e = { v , w } выполнить
B10 если  w не находится в F  , то // w сопоставлено, поэтому добавить сопоставленное ребро e и w к F
B11 x ← вершина, сопоставленная с w в M
B12 добавить ребра { v , w } и { w , x } к дереву v
B13 иначе
B14 если  расстояние (w, root(w)) нечетное , то // Ничего не делать.B15 else
B16 if  root(v) ≠ root(w)  then // Сообщить о увеличивающемся пути в F { e }. $\чашка$ B17 P ← путь ( корень ( v ) → ... → v ) → ( w → ... → корень ( w ))B18 return  P
B19 else // Сжимаем цветок в G и ищем путь в сжатом графе.B20 B ← цветок, образованный e и ребрами на пути v → w в T
B21 G', M' ← контракт G и M с помощью B
B22 P' ← поиск_увеличения_пути ( G' , M' )B23 P ← поднять P' до G
B24 вернуть  P
B25 конец, если
B26 конец, если
B27 конец, если
B28 отметить ребро e
B29 конец, пока
B30 отметить вершину v
B31 конец, пока
B32 вернуть пустой путьB33 конечная функция

Примеры

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

Далее он обнаруживает цветение и сжимает график (линии B20 – B21).

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

Анализ

Лес $F$ , построенный функцией find_augmenting_path(), является чередующимся лесом. ^[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})$

Двудольное соответствие

Когда $G$ двудольный , в $G$ нет нечетных циклов . В этом случае цветки никогда не будут найдены, и можно просто удалить строки B20 – B24 алгоритма. Таким образом, алгоритм сводится к стандартному алгоритму построения паросочетаний максимальной мощности в двудольных графах ^[7] , где мы многократно ищем увеличивающий путь простым обходом графа: это, например, случай алгоритма Форда–Фалкерсона .

Взвешенное соответствие

Проблему сопоставления можно обобщить, назначив веса ребрам в $G$ и запросив множество $M$ , которое производит сопоставление максимального (минимального) общего веса: это проблема сопоставления максимального веса . Эту задачу можно решить с помощью комбинаторного алгоритма, который использует невзвешенный алгоритм Эдмондса в качестве подпрограммы. ^[6] Колмогоров предоставляет эффективную реализацию этого на C++. ^[10]

Ссылки

^ Эдмондс, Джек (1991), «Проблеск неба», в JK Lenstra; AHG Риннуй Кан; А. Шрийвер (ред.), История математического программирования --- Сборник личных воспоминаний , CWI, Амстердам и Северная Голландия, Амстердам, стр. 32–54.
^ Эдмондс, Джек (1965). «Пути, деревья и цветы». Can. J. Math . 17 : 449–467. doi : 10.4153/CJM-1965-045-4 .
^ Микали, Сильвио; Вазирани, Виджай (1980). Алгоритм O(V ^1/2 E) для поиска максимального паросочетания в общих графах . 21-й ежегодный симпозиум по основам компьютерной науки. IEEE Computer Society Press, Нью-Йорк. С. 17–27.
^ Эдмондс, Джек (1965). «Максимальное соответствие и многогранник с 0,1-вершинами». Журнал исследований Национального бюро стандартов, раздел B. 69 : 125–130. doi : 10.6028/jres.069B.013 .
^ Schrijver, Alexander (2003). Комбинаторная оптимизация: многогранники и эффективность. Алгоритмы и комбинаторика. Berlin Heidelberg: Springer-Verlag. ISBN 9783540443896.
^ аб Ловас, Ласло ; Пламмер, Майкл (1986). Теория соответствия . Академик Киадо. ISBN 963-05-4168-8.
^ ab Karp, Richard, "Алгоритм недвудольного сопоставления Эдмондса", Курсовые заметки. Калифорнийский университет в Беркли (PDF) , архивировано из оригинала (PDF) 2008-12-30
^ ab Tarjan, Robert, «Краткие заметки об алгоритме невероятного уменьшающегося цветения Эдмондса для общего сопоставления», Курсовые заметки, Кафедра компьютерных наук, Принстонский университет (PDF)
^ Кеньон, Клэр; Ловас, Ласло , «Алгоритмическая дискретная математика», технический отчет CS-TR-251-90, факультет компьютерных наук, Принстонский университет.
^ Колмогоров, Владимир (2009), «Blossom V: Новая реализация алгоритма идеального соответствия с минимальной стоимостью», Математическое программирование и вычисления , 1 (1): 43–67, doi :10.1007/s12532-009-0002-8