Изменения

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

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

Пусть дан произвольный граф Основную сложность представляют операции сжатия и восстановления цветков. Чтобы эффективно это делать, для каждой вершины необходимо хранить указатель на базу цветка, которому она принадлежит, или на себя в противном случае. Предположим, что для поиска паросочетаний в сжатом графе, мы используем обход в ширину. Тогда на каждой итерации алгоритма будет строиться дерево обхода в ширину, причём путь в нём до любой вершины будет являться чередующимся путём, начинающимся с корня этого дерева. Будем класть в очередь только те вершины, расстояние от корня до которых в дереве путей чётно. Также для каждой вершины, расстояние до которой нечётно, в массиве предков <tex>p[]</tex>Gнеобходимо хранить её предка {{---}} чётную вершину. Заметим, что если в процессе обхода в ширину мы из текущей вершины <tex>v</tex> приходим в такую вершину <tex>u</tex>, являющуюся корнем или принадлежащую паросочетанию и дереву путей, то обе эти вершины принадлежат некоторому цветку. Действительно, при выполнении этих условий эти вершины являются чётными вершинами, следовательно расстояние от них до их наименьшего общего предка имеет одну чётность. Найдём наименьшего общего предка <tex>lca(Vu, Ev)</tex> и требуется найти максимальное паросочетание в нёмвершин <tex>u</tex>, <tex>v</tex>, который является базой цветка. Для нахождения самого цикла необходимо пройтись от вершин <tex>u</tex>, <brtex> ===Общая идея=== #Сжимаем все соцветия#Находим паросочетания v</tex> до базы цветка. В явном виде цветок сжимать не будем, просто положим в полученном графе поиском очередь обхода в глубину/ширинувсе вершины, принадлежащие цветку.#Разжимаем соцветияТакже для всех чётных вершин (за исключением базы) назначим предком соседнюю вершину в цикле, восстанавливая паросочетаниеа для вершин <tex>u</tex> и <tex>v</tex> назначим предками друг друга. ===Пошаговое представление===  Алгоритм строит лес(используя поиск Это позволит корректно восстановить цветок, в глубину или ширину)случае, содержащий деревья удлиняющих путейкогда при восстановление увеличивающего пути, корнями которых являются вершины не из паросочетаниямы зайдем в нечётную вершину цикла.

Сначала пометим все вершиныВсего имеется <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>.

Пока существует удлиняющий путь или пока есть непроверенное ребро из четной вершины <tex>v</tex>:==Литература==#Выберем любое непроверенное ребро<tex>(v*''Ловас, w)</tex> из четной вершины <tex>v</tex> и проверяем:#*Вершина <tex>w</tex> нечетное - ничего не делаемПламмер'' '''Прикладные задачи теории графов. Такая ситуация возникает, когда <tex>(v, w)</tex> ребро из паросочетания или не из паросочетания#*Вершина <tex>w</tex> включено Теория паросочетаний в паросочетание математике и непосещенное. Тогда помечаем <tex>w</tex> нечетным, а <tex>mate(w)</tex> четным. Присваиваем <tex>p(w) \gets v</tex>, а также <tex>p(mate(w)) \gets w</tex>физике'''#*<tex>w<[http:/tex> четное; вершины <tex>w, v</tex> лежат в разных деревьях e- нашли удлиняющий путь от корня дерева, содержащего вершину <tex>v</tex> до корня дерева, содержащего вершину <tex>w</tex>maxx.#*<tex>w<ru/tex> четное; вершины <tex>w, v<algo/tex> лежат matching_edmonds Алгоритм Эдмондса нахождения наибольшего паросочетания в одном дереве - нашли соцветие. Пусть <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; }]]