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

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

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

Основная причина важности алгоритма цветения заключается в том, что он дал первое доказательство того, что совпадение максимального размера может быть найдено с использованием полиномиального количества времени вычислений. Другая причина заключается в том, что это привело к с помощью линейного программирования полиэдрическому описанию совпадающего многогранника , что дало алгоритм сопоставления с минимальным весом . ^[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$ не существует $M$ -дополняющего пути $является максимальным тогда и только тогда, когда в G$ . ^[6]^[7] Следовательно, либо паросочетание максимально, либо его можно расширить. Таким образом, начиная с начального сопоставления, мы можем вычислить максимальное сопоставление, дополняя текущее сопоставление дополняющими путями, пока мы можем их найти, и возвращаться всякий раз, когда дополняющих путей не остается. Формализовать алгоритм можно следующим образом:

   INPUT:  Graph G, initial matching M on G   OUTPUT: maximum matching M* on GA1 function find_maximum_matching(G, M) : M*A2     P ← find_augmenting_path(G, M)A3     if P is non-empty thenA4         return find_maximum_matching(G, augment M along P)A5     elseA6         return MA7     end ifA8 end function

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

Цветение и схватки

Учитывая $G = (V, E)$ и паросочетание $M$ группы $G$ , цветок $B$ — это цикл в $G,$ состоящий из $2 k + 1$ которого $ребра, ровно k$ принадлежит $M$ , и где одна из вершин $v$ цикла ( base ) таков, что существует альтернативный путь четной длины ( основа ) от $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 $v$ , $(u' \to \dots \to v')$ , идущие от $u'$ к $',$ выбираются так, чтобы путь был чередующимся ( $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$ .

    INPUT:  Graph G, matching M on G    OUTPUT: augmenting path P in G or empty path if none foundB01 function find_augmenting_path(G, M) : PB02    F ← empty forestB03    unmark all vertices and edges in G, mark all edges of MB05    for each exposed vertex v doB06        create a singleton tree { v } and add the tree to FB07    end forB08    while there is an unmarked vertex v in F with distance(v, root(v)) even doB09        while there exists an unmarked edge e = { v, w } doB10            if w is not in F then                   // w is matched, so add e and w's matched edge to FB11                x ← vertex matched to w in MB12                add edges { v, w } and { w, x } to the tree of vB13            elseB14                if distance(w, root(w)) is odd then                       // Do nothing.B15                elseB16                    if root(v) ≠ root(w) then                           // Report an augmenting path in F  $\cup$  { e }.B17                        P ← path (root(v) → ... → v) → (w → ... → root(w))B18                        return PB19                    else                           // Contract a blossom in G and look for the path in the contracted graph.B20                        B ← blossom formed by e and edges on the path v → w in TB21                        G’, M’ ← contract G and M by BB22                        P’ ← find_augmenting_path(G’, M’)B23                        P ← lift P’ to GB24                        return PB25                    end ifB26                end ifB27            end ifB28            mark edge eB29        end whileB30        mark vertex vB31    end whileB32    return empty pathB33 end function

Примеры

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

[glimpse-1] Эдмондс, Джек (1991), «Взгляд на небеса», в Дж. К. Ленстре; AHG Риннуй Кан; А. Шрийвер (ред.), История математического программирования --- Сборник личных воспоминаний , CWI, Амстердам и Северная Голландия, Амстердам, стр. 32–54.

[algorithm-2] Эдмондс, Джек (1965). «Дорожки, деревья и цветы» . Может. Дж. Математика . 17 : 449–467. дои : 10.4153/CJM-1965-045-4 .

[micali-3] Микали, Сильвио; Вазирани, Виджай (1980). O(V ^1/2Д) алгоритм поиска максимального паросочетания в общих графах . 21-й ежегодный симпозиум по основам информатики. Издательство IEEE Computer Society Press, Нью-Йорк. стр. 17–27.

[weighted-4] Эдмондс, Джек (1965). «Максимальное паросочетание и многогранник с 0,1-вершинами» . Журнал исследований Национального бюро стандартов . Раздел B. 69 : 125–130. дои : 10.6028/jres.069B.013 .

[5] Шрийвер, Александр (2003). Комбинаторная оптимизация: многогранники и эффективность . Алгоритмы и комбинаторика. Берлин Гейдельберг: Springer-Verlag. ISBN 9783540443896 .

[matching_book-6] Перейти обратно: ^а ^б Ловас, Ласло ; Пламмер, Майкл (1986). Теория соответствия . Академическое издательство. ISBN 963-05-4168-8 .

[karp_notes-7] Перейти обратно: ^а ^б Карп, Ричард, «Алгоритм недвустороннего сопоставления Эдмондса», Примечания к курсу. Калифорнийский университет в Беркли (PDF) , заархивировано из оригинала (PDF) 30 декабря 2008 г.

[tarjan_notes-8] Перейти обратно: ^а ^б Тарьян, Роберт, «Отрывочные заметки о невероятном алгоритме Эдмондса сжимающегося цветка для общего сопоставления», конспекты курса, факультет компьютерных наук, Принстонский университет (PDF)

[kenyon_report-9] Кеньон, Клэр; Ловас, Ласло , «Алгоритмическая дискретная математика», технический отчет CS-TR-251-90, факультет компьютерных наук, Принстонский университет.

[blossom5-10] Колмогоров, Владимир (2009), «Blossom V: Новая реализация алгоритма идеального сопоставления с минимальной стоимостью» , Mathematical Programming Computation , 1 (1): 43–67, doi : 10.1007/s12532-009-0002-8

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]