Изменения

{{ОпределениеРассмотрим неориентированный невзвешенный [[Основные определения теории графов|definition= Соцветие граф]] <tex>BG =\langle V, E \rangle </tex> графа , где <tex>G=(V,E)</tex> {{-- цикл-}} множество [[Основные определения теории графов| вершин]], состоящий из <tex>2k + 1E </tex> ребер. {{---}}множество [[Основные определения теории графов|рёбер]]. Требуется найти в нём максимальное паросочетание.{{ОпределениеПриведём пример, на котором [[Алгоритм Куна для поиска максимального паросочетания|definitionалгоритм Куна]] работать не будет. Рассмотрим граф <tex>G</tex> с множеством вершин <tex>V= Cжатие соцветия {1,2,3,4} </tex>, и множеством рёбер {{- граф --}}<tex>G'E={\langle 1,2 \rangle, \langle 2, 3 \rangle, \langle 3, 1 \rangle, \langle 2, 4 \rangle}</tex>и пусть ребро <tex>\langle 2, полученный 3\rangle</tex> взято в паросочетание. Тогда при запуске из вершины <tex>G1</tex> сжатием всего нечётного цикла , если обход пойдёт сначала в одну псевдо-вершину (соответственно<tex>2</tex>, все рёбрато он зайдёт в тупик в вершине <tex>3</tex>, инцидентные вершинам этого цикла, становятся инцидентными псевдовместо того чтобы найти увеличивающую цепь <tex>1-3-2-вершине)4</tex>.}}{{Определение|definition= База соцветия - вершина соцветияКак видно на этом примере, основная проблема заключается в том, что при попадании в цикл нечётной длины, обход может пойти по циклу в которую входит ребро не из данного соцветиянеправильном направлении.}}

Пусть даны граф <tex>G</tex>, паросочетание <tex>M</tex> в графе <tex>G</tex> существует соцветие и цикл <tex>Z</tex> длины <tex>2k+1</tex>, содержащий <tex>k</tex> рёбер паросочетания <tex>M</tex> и вершинно непересекающийся с остальными рёбрами из <tex>BM</tex>.Построим новый граф <tex>G'<br /tex> из графа <tex>G</tex>, сжимая цикл <tex>Z</tex>до единичной вершины, при этом все ребра, инцидентные вершинам этого цикла, становятся инцидентными вершине в новом графе. Тогда паросочетание <tex>M -E(Z)</tex>, где <tex>E(z)</tex> {{---}} ребра, инцидентные циклу, является наибольшим в <tex>G'</tex> существует удлиняющий путь тогда и только тогда, когда существует удлиняющий путь М {{---}} наибольшее паросочетание в <tex>G\setminus B</tex>

Пусть граф Предположим, что <tex>M</tex> не является наибольшим паросочетанием в <tex>G'</tex> - граф, полученный тогда в силу [[Теорема о максимальном паросочетании и дополняющих_цепях|теоремы о максимальном паросочетании и дополняющих цепях]] существует увеличивающая относительно <tex>M</tex> цепь <tex>P</tex>. Если <tex>P</tex> не пересекается с <tex>GZ</tex> сжатием соцветия , то цепь является увеличивающей относительно <tex>BM'</tex> и в псевдо-вершину графе <tex>G'</tex>, а значит, <tex>BM'</tex>не может быть наибольшим паросочетанием.Поэтому предположим, что цепь <tex>P</tex> пересекается с <tex>Z<br /tex>. Заметим, что достаточно рассматривать случайхотя бы одна концевая вершина цепи <tex>P</tex> не лежит на <tex>Z</tex>, когда база соцветия является свободной вершиной (не принадлежащей паросочетанию)обозначим её через <tex>u</tex>. В противном случае в базе соцветия оканчивается чередующийся путь чётной длиныТогда пройдём по цепи <tex>P</tex>, начиная с <tex>u</tex> до первой встречной вершины на <tex>Z</tex>, начинающийся в свободной вершинеобозначим её через <tex>v</tex>. Прочередовав паросочетание вдоль этого путиТогда, при сжатии цикла <tex>Z</tex>, участок <tex>P[u, мощность паросочетания v]</tex> отобразится на увеличивающую цепь относительно <tex>M'</tex>, то есть <tex>M'</tex> не изменитсяявляется максимальным паросочетанием, а база соцветия станет свободной вершинойчто противоречит нашему предположению.

Теперь допустим, что <tex>\RightarrowM'</tex>не является наибольшим паросочетанием в графе <tex>G'</tex>. Обозначим через <tex>N'</tex> паросочетание в <tex>G'</tex>, мощности большей, чем <tex>M'</tex>. Восстановим граф <tex>G</tex>, тогда <tex>N'</tex> будет соответствовать некоторому паросочетанию в <tex>G</tex>, покрывающему не более одной вершины в <tex>Z</tex>. Следовательно паросочетание <tex>N'</tex> можно увеличить, используя <tex>k</tex> рёбер цикла <tex>Z</tex>, и получить паросочетание <tex>N</tex>, размера <tex>|N| = |N'|+k > |M'|+k = |M|</tex>, то есть <tex>M</tex> не является наибольшим паросочетанием в <tex>G</tex>, приходим к противоречию. Таким образом теорема доказана.}}

Пусть путь <tex>P</tex> является удлиняющим в графе <tex>G</tex>Для простоты описания алгоритма введём некоторые определения. Если <tex>P</tex> не проходит через <tex>B</tex>, то тогда он будет удлиняющим и в графе <tex>G{{Определение|definition= Будем называть '''соцветием'''</tex>. <br />Пусть проходит через <tex>B</tex>. Тогда что путь P представляет собой некоторый путь <tex>P_1</tex>, не проходящий по вершинам <tex>B</tex>, плюс некоторый путь <tex>P_2</tex>, проходящий по вершинам <tex>B</tex> и, возможно, другим вершинам. Но тогда путь <tex>P_1 + B'</tex> будет являться удлиняющим путём в графе графа <tex>G'</tex>, что и требовалось доказатьего цикл нечётной длины.

'''Cжатием соцветия''' назовём граф <tex>\LeftarrowG'</tex>, полученный из <tex>G</tex> сжатием всего нечётного цикла в одну псевдо-вершину. Все рёбра, инцидентные вершинам этого цикла, становятся инцидентными псевдо-вершине в новом графе.

Пусть путь <tex>P</tex> является удлиняющим путём в графе <tex>G'</tex>. Если <tex>P</tex> не проходит через <tex>B'</tex>'База соцветия''' - вершина соцветия, то тогда он будет удлиняющим и в графе <tex>G</tex>которую входит ребро не из данного соцветия. <br />}}

Рассмотрим отдельно случай, когда <tex>P</tex> начинается со сжатого соцветия <tex>B'</tex>, т[[Файл:blossom1.еjpg|300px|Рис. имеет вид <tex>(B', c, ...)</tex>. Тогда в соцветии <tex>B</tex> найдётся соответствующая вершина <tex>v</tex>, которая связана ребром с <tex>c</tex>. Заметим, что из базы соцветия всегда найдётся чередующийся путь чётной длины до вершины <tex>v</tex>. Учитывая всё вышесказанное, получаем, что путь <tex>P_1(b,...v,...c,..)</tex> является увеличивающим путём в графе <tex>G</tex>.1]]Пусть теперь путь <tex>P</tex> проходит через псевдо-вершину <tex>B'</tex>, но не начинается и не заканчивается в ней. Тогда в <tex>P</tex> есть два ребра, проходящих через <tex>B'</tex>, пусть это <tex>(a,B')</tex> и <tex>(B',c)</tex>. Одно из них обязательно должно принадлежать паросочетанию, однако, так как база цветка не насыщена, а все остальные вершины цикла цветка насыщены рёбрами цикла, то мы приходим к противоречию (это эквивалентно [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графахФайл:blossom2.jpg|300px|случаю отсутствия ребра из <tex>R_-</tex> в <tex>L_+</tex>Рис. 2]]). Таким образом, этот случай просто невозможен. Теорема доказана.}}

Пусть дан произвольный граф <tex>G(VОсновную сложность представляют операции сжатия и восстановления цветков. Чтобы эффективно это делать, для каждой вершины необходимо хранить указатель на базу цветка, которому она принадлежит, E)</tex> и требуется найти максимальное паросочетание или на себя в нёмпротивном случае. <br>[[Файл:blossom1.jpg|thumb|right|Рис. 1]]  ===Общая идея=== [[Файл:blossom2.jpg|thumb|right|Рис. 2]]#Сжимаем все соцветия#Находим паросочетания Предположим, что для поиска паросочетаний в полученном сжатом графе поиском , мы используем обход в глубину/ширину.#Разжимаем соцветия, восстанавливая паросочетание. ===Пошаговое представление===  Алгоритм строит лес(используя поиск Тогда на каждой итерации алгоритма будет строиться дерево обхода в глубину или ширину), содержащий деревья удлиняющих путей, корнями которых являются причём путь в нём до любой вершины не из паросочетания. Разобьем каждое неориентированное ребро <tex>(wбудет являться чередующимся путём, v)</tex> на два ориентированных ребра <tex>(w, v)</tex> и <tex>(v, w)</tex>начинающимся с корня этого дерева. Каждое ребро может принимать одно из трех состояний: непосещенноеБудем класть в очередь только те вершины, четное и нечетное.Для каждой вершины из паросочетания <tex>v</tex> расстояние от корня до которых в <tex>mate(v)</tex> будем хранить вершину, смежную <tex>v</tex>дереве путей чётно.Также для каждой вершины <tex>v</tex> алгоритм , расстояние до которой нечётно, в массиве предков <tex>p(v)[]</tex> будет необходимо хранить родителя её предка {{---}} чётную вершину. Заметим, что если в дереве процессе обхода. Сначала пометим все вершины, включенные в паросочетание, непосещенными, все остальные - четными. Пока существует удлиняющий путь или пока есть непроверенное ребро ширину мы из четной текущей вершины <tex>v</tex>:#Выберем любое непроверенное реброприходим в такую вершину <tex>(v, w)</tex> из четной вершины <tex>v</tex> и проверяем:#*Вершина <tex>wu</tex> нечетное - ничего не делаем. Такая ситуация возникает, когда <tex>(v, w)</tex> ребро из паросочетания что она является корнем или не из паросочетания#*Вершина <tex>w</tex> включено в паросочетание принадлежит паросочетанию и непосещенноедереву путей, то обе эти вершины принадлежат некоторому цветку. Тогда помечаем <tex>w</tex> нечетнымДействительно, при выполнении этих условий эти вершины являются чётными вершинами, а <tex>mate(w)</tex> четнымследовательно расстояние от них до их наименьшего общего предка имеет одну чётность. Присваиваем Найдём наименьшего общего предка <tex>plca(w) \gets u,v</tex>, а также <tex>p(mate(w)) \gets w</tex>#*вершин <tex>w</tex> четное; вершины <tex>w, vu</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; }цикла.

Всего имеется <tex>V</tex> итераций, на каждой из которых выполняется обход в ширину за <tex>O(E)</tex>, кроме того, могут происходить операции сжатия цветков — их может быть <tex>O(V)</tex>. Если уметь сжимать соцветие Сжатие соцветий работает за <tex>O(V)</tex>, то есть общая асимптотика алгоритма составит <tex>O(V(E + V^2)) = O(V^3)</tex>.

*''R. TarjanЛовас, Пламмер'' '''Data Structures and Network AlgorithmsПрикладные задачи теории графов. Теория паросочетаний в математике и физике''' -ISBN 0898711878*[http://e-maxx.ru/algo/matching_edmonds Алгоритм Алгоритм Эдмондса нахождения наибольшего паросочетания в произвольных графах] [[Категория: Алгоритмы и структуры данных]][[Категория: Задача о паросочетании]]