Изменения

Рассмотрим неориентированный невзвешенный [[Основные определения теории графов|граф]] <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<br /tex> пересекается с <tex>Z</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>M'</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>, приходим к противоречию. Таким образом теорема доказана.}} Для простоты описания алгоритма введём некоторые определения.{{Определение|definition= Будем называть '''соцветием''' <tex>B</tex> графа <tex>G</tex> его цикл нечётной длины. '''Cжатием соцветия оканчивается чередующийся путь чётной длины''' назовём граф <tex>G'</tex>, начинающийся полученный из <tex>G</tex> сжатием всего нечётного цикла в свободной одну псевдо-вершину. Все рёбра, инцидентные вершинам этого цикла, становятся инцидентными псевдо-вершинев новом графе. Прочередовав паросочетание вдоль этого пути '''База соцветия''' - вершина соцветия, мощность паросочетания в которую входит ребро не изменится, а база из данного соцветия станет свободной вершиной. }}

Пусть путь <tex>P</tex> является удлиняющим в графе ==Алгоритм вырезания соцветий==Опишем алгоритм, позволяющий находить максимальное паросочетание для произвольного графа <tex>G</tex>. Если <tex>P</tex> не проходит через <tex>B</tex>Из теоремы Эдмондса понятно, то тогда он будет удлиняющим и что необходимо рассматривать паросочетание в сжатом графе <tex>G'</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>, что и требовалось доказать.

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

Рассмотрим отдельно случай, когда Всего имеется <tex>P</tex> начинается со сжатого соцветия <tex>B'V</tex>итераций, т.е. имеет вид на каждой из которых выполняется обход в ширину за <tex>O(B', c, ...E)</tex>. Тогда в соцветии <tex>B</tex> найдётся соответствующая вершина <tex>v</tex>, которая связана ребром с кроме того, могут происходить операции сжатия цветков — их может быть <tex>cO(V)</tex>. Заметим, что из базы соцветия всегда найдётся чередующийся путь чётной длины до вершины Сжатие соцветий работает за <tex>vO(V)</tex>. Учитывая всё вышесказанное, получаем, что путь то есть общая асимптотика алгоритма составит <tex>P_1O(V(E + V^2)) = O(b,...v,...c,..V^3)</tex> является увеличивающим путём в графе <tex>G</tex>.}}

Пусть теперь путь <tex>P</tex> проходит через псевдо-вершину <tex>B==Литература==*''</tex>Ловас, но не начинается и не заканчивается в нейПламмер'' '''Прикладные задачи теории графов. Тогда Теория паросочетаний в <tex>P</tex> есть два ребра, проходящих через <tex>Bматематике и физике''</tex>, пусть это <tex>(a,B')<*[http:/tex> и <tex>(B',c)</tex>. Одно из них обязательно должно принадлежать паросочетанию, однако, так как база цветка не насыщена, а все остальные вершины цикла цветка насыщены рёбрами цикла, то мы приходим к противоречию. Таким образом, этот случай просто невозможен. Теорема доказанаe-maxx.ru/algo/matching_edmonds Алгоритм Эдмондса нахождения наибольшего паросочетания в произвольных графах]

==Алгоритм==Пусть дан произвольный граф <tex>G(V, E)</tex> [[Категория: Алгоритмы и требуется найти максимальное паросочетание в нём. <br>структуры данных]]Для построения алгоритма по [[Теорема Категория: Задача о максимальном паросочетании и дополняющих цепях|теореме Бержа]] нужно уметь находить дополняющую цепь.