Изменения

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

Пусть теперь путь <tex>P</tex> проходит через псевдо-вершину <tex>B'</tex>, но не начинается и не заканчивается в ней. Тогда в <tex>P</tex> есть два ребра, проходящих через <tex>B'</tex>==Алгоритм вырезания соцветий==Опишем алгоритм, пусть это позволяющий находить максимальное паросочетание для произвольного графа <tex>(a,B')</tex> и <tex>(B',c)G</tex>. Одно из них обязательно должно принадлежать паросочетаниюИз теоремы Эдмондса понятно, однакочто необходимо рассматривать паросочетание в сжатом графе, так как база цветка не насыщенагде его можно найти, а все остальные вершины цикла цветка насыщены рёбрами циклак примеру, то мы приходим к противоречию (это эквивалентно при помощи алгоритма [[Связь Алгоритм Куна для поиска максимального паросочетания и минимального вершинного покрытия в двудольных графах|случаю отсутствия ребра из <tex>R_-</tex> в <tex>L_+</tex>Куна]]). Таким образом, этот случай просто невозможен. Теорема доказанаа после восстанавливать паросочетание в исходном графе.}}

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>.

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