Алгоритм вырезания соцветий - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:21:08Z

rollbackEdits.php mass rollback

194.26.192.187 в 05:19, 1 сентября 2022

2022-09-01T05:19:54Z

178.121.47.217: /* Алгоритм вырезания соцветий */

2021-03-03T15:12:15Z

‎Алгоритм вырезания соцветий

178.121.47.217: /* Алгоритм вырезания соцветий */

2021-03-03T15:07:42Z

‎Алгоритм вырезания соцветий

178.121.47.217: /* Теорема Эдмондса */

2021-03-03T14:55:51Z

‎Теорема Эдмондса

Дмитрий Мурзин в 23:14, 8 января 2020

2020-01-08T23:14:17Z

Dgerasimov: /* Паросочетание в недвудольном графе */

2013-11-16T09:27:53Z

‎Паросочетание в недвудольном графе

178.178.29.194 в 09:33, 6 марта 2012

2012-03-06T09:33:01Z

194.85.160.130: /* Алгоритм вырезания соцветий */

2012-03-06T08:04:01Z

‎Алгоритм вырезания соцветий

83.149.2.234: /* Теорема Эдмондса */

2012-02-29T07:19:17Z

‎Теорема Эдмондса

← Предыдущая		Версия 16:21, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	== Паросочетание в недвудольном графе==		== Паросочетание в недвудольном графе==

← Предыдущая		Версия 05:19, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	== Паросочетание в недвудольном графе==		== Паросочетание в недвудольном графе==

@@ Строка 31: / Строка 31: @@
 Опишем алгоритм, позволяющий находить максимальное паросочетание для произвольного графа <tex>G</tex>. Из теоремы Эдмондса понятно, что необходимо рассматривать паросочетание в сжатом графе, где его можно найти, к примеру, при помощи алгоритма [[Алгоритм Куна для поиска максимального паросочетания|Куна]], а после восстанавливать паросочетание в исходном графе.
-Основную сложность представляют операции сжатия и восстановления цветков. Чтобы эффективно это делать, для каждой вершины необходимо хранить указатель на базу цветка, которому она принадлежит, или на себя в противном случае. Предположим, что для поиска паросочетаний в сжатом графе, мы используем обход в ширину. Тогда на каждой итерации алгоритма будет строиться дерево обхода в ширину, причём путь в нём до любой вершины будет являться чередующимся путём, начинающимся с корня этого дерева. Будем класть в очередь только те вершины, расстояние от корня до которых в дереве путей чётно. Также для каждой вершины, расстояние до которой нечётно, в массиве предков <tex>p[]</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>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> назначим предками друг друга. Это позволит корректно восстановить цветок в случае, когда при восстановлении увеличивающего пути мы зайдем в нечётную вершину цикла.
 == Оценка сложности ==

@@ Строка 31: / Строка 31: @@
 Опишем алгоритм, позволяющий находить максимальное паросочетание для произвольного графа <tex>G</tex>. Из теоремы Эдмондса понятно, что необходимо рассматривать паросочетание в сжатом графе, где его можно найти, к примеру, при помощи алгоритма [[Алгоритм Куна для поиска максимального паросочетания|Куна]], а после восстанавливать паросочетание в исходном графе.
-Основную сложность представляют операции сжатия и восстановления цветков. Чтобы эффективно это делать, для каждой вершины необходимо хранить указатель на базу цветка, которому она принадлежит, или на себя в противном случае. Предположим, что для поиска паросочетаний в сжатом графе, мы используем обход в ширину. Тогда на каждой итерации алгоритма будет строиться дерево обхода в ширину, причём путь в нём до любой вершины будет являться чередующимся путём, начинающимся с корня этого дерева. Будем класть в очередь только те вершины, расстояние от корня до которых в дереве путей чётно. Также для каждой вершины, расстояние до которой нечётно, в массиве предков <tex>p[]</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>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> назначим предками друг друга. Это позволит корректно восстановить цветок, в случае, когда при восстановление увеличивающего пути, мы зайдем в нечётную вершину цикла.
 == Оценка сложности ==

@@ Строка 11: / Строка 11: @@
 Пусть даны граф <tex>G</tex>, паросочетание <tex>M</tex> в <tex>G</tex> и цикл <tex>Z</tex> длины <tex>2k+1</tex>, содержащий <tex>k</tex> рёбер паросочетания <tex>M</tex> и вершинно непересекающийся с остальными рёбрами из <tex>M</tex>. Построим новый граф <tex>G'</tex> из графа <tex>G</tex>, сжимая цикл <tex>Z</tex> до единичной вершины, при этом все ребра, инцидентные вершинам этого цикла, становятся инцидентными вершине в новом графе. Тогда паросочетание <tex>M -E(Z)</tex>, где <tex>E(z)</tex> {{---}} ребра, инцидентные циклу, является наибольшим в <tex>G'</tex> тогда и только тогда, когда М {{---}} наибольшее паросочетание в <tex>G</tex>
 |proof=
-Предположим, что <tex>M</tex> не является наибольшим паросочетанием в <tex>G</tex>, тогда в силу [[Теорема о максимальном паросочетании и дополняющих_цепях|теоремы о максимальном паросочетании и дополняющих цепях]] существует увеличивающая относительно <tex>M</tex> цепь <tex>P</tex>. Если <tex>P</tex> не пересекается с <tex>Z</tex>, то цепь является увеличивающей относительно <tex>M'</tex> и в графе <tex>G'</tex>, а значит, <tex>M'</tex> не может быть наибольшим паросочетанием. Поэтому предположим, что цепь <tex>P</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>M</tex> цепь <tex>P</tex>. Если <tex>P</tex> не пересекается с <tex>Z</tex>, то цепь является увеличивающей относительно <tex>M'</tex> и в графе <tex>G'</tex>, а значит, <tex>M'</tex> не может быть наибольшим паросочетанием. Поэтому предположим, что цепь <tex>P</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>, приходим к противоречию. Таким образом теорема доказана.

@@ Строка 1: / Строка 1: @@
 == Паросочетание в недвудольном графе==
-Рассмотрим неориентированный невзвешенный [[Основные определения теории графов|граф]] <tex> G =\langle V, E \rangle </tex>, где <tex>V </tex> {{---}} множество [[Основные определения теории графов| вершин]], <tex>E </tex> {{---}} множество [[Основные определения теории графов|ребер]]. Требуется найти в нем максимальное паросочетание.
+Рассмотрим неориентированный невзвешенный [[Основные определения теории графов|граф]] <tex> G =\langle V, E \rangle </tex>, где <tex>V </tex> {{---}} множество [[Основные определения теории графов| вершин]], <tex>E </tex> {{---}} множество [[Основные определения теории графов|рёбер]]. Требуется найти в нём максимальное паросочетание.
-Приведем пример, на котором [[Алгоритм Куна для поиска максимального паросочетания|алгоритм Куна]] работать не будет. Рассмотрим граф <tex>G</tex> с множеством вершин <tex>V={1,2,3,4} </tex>, и множеством ребер {{---}}<tex>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>1</tex>, если обход пойдёт сначала в вершину <tex>2</tex>, то он зайдет в тупик в вершине <tex>3</tex>, вместо того чтобы найти увеличивающую цепь <tex>1-3-2-4</tex>. Как видно на этом примере, основная проблема заключается в том, что при попадании в цикл нечётной длины, обход может пойти по циклу в неправильном направлении.
+Приведём пример, на котором [[Алгоритм Куна для поиска максимального паросочетания|алгоритм Куна]] работать не будет. Рассмотрим граф <tex>G</tex> с множеством вершин <tex>V={1,2,3,4} </tex>, и множеством рёбер {{---}}<tex>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>1</tex>, если обход пойдёт сначала в вершину <tex>2</tex>, то он зайдёт в тупик в вершине <tex>3</tex>, вместо того чтобы найти увеличивающую цепь <tex>1-3-2-4</tex>. Как видно на этом примере, основная проблема заключается в том, что при попадании в цикл нечётной длины, обход может пойти по циклу в неправильном направлении.
 == Теорема Эдмондса ==
@@ Строка 9: / Строка 9: @@
 {{Теорема
 |statement=
-Пусть даны граф <tex>G</tex>, паросочетание <tex>M</tex> в <tex>G</tex> и цикл <tex>Z</tex> длины <tex>2k+1</tex>, содержащий <tex>k</tex> ребер паросочетания <tex>M</tex> и вершинно непересекающийся с остальными ребрами из <tex>M</tex>. Построим новый граф <tex>G'</tex> из графа <tex>G</tex>, сжимая цикл <tex>Z</tex> до единичной вершины, при этом все ребра, инцидентные вершинам этого цикла, становятся инцидентными вершине в новом графе. Тогда паросочетание <tex>M -E(Z)</tex>, где <tex>E(z)</tex> {{---}} ребра, инцидентные циклу, является наибольшим в <tex>G'</tex> тогда и только тогда, когда М {{---}} наибольшее паросочетание в <tex>G</tex>
+Пусть даны граф <tex>G</tex>, паросочетание <tex>M</tex> в <tex>G</tex> и цикл <tex>Z</tex> длины <tex>2k+1</tex>, содержащий <tex>k</tex> рёбер паросочетания <tex>M</tex> и вершинно непересекающийся с остальными рёбрами из <tex>M</tex>. Построим новый граф <tex>G'</tex> из графа <tex>G</tex>, сжимая цикл <tex>Z</tex> до единичной вершины, при этом все ребра, инцидентные вершинам этого цикла, становятся инцидентными вершине в новом графе. Тогда паросочетание <tex>M -E(Z)</tex>, где <tex>E(z)</tex> {{---}} ребра, инцидентные циклу, является наибольшим в <tex>G'</tex> тогда и только тогда, когда М {{---}} наибольшее паросочетание в <tex>G</tex>
 |proof=
-Предположим, что <tex>M</tex> не является наибольшим паросочетанием в <tex>G</tex>, тогда в силу [[Теорема о максимальном паросочетании и дополняющих_цепях|теоремы о максимальном паросочетании и дополняющих цепях]] существует увеличивающая относительно <tex>M</tex> цепь <tex>P</tex>. Если <tex>P</tex> не пересекается с <tex>Z</tex>, то цепь является увеличивающей относительно <tex>M'</tex> и в графе <tex>G'</tex>, а значит, <tex>M'</tex> не может быть наибольшим паросочетанием. Поэтому предположим, что цепь <tex>P</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>M</tex> цепь <tex>P</tex>. Если <tex>P</tex> не пересекается с <tex>Z</tex>, то цепь является увеличивающей относительно <tex>M'</tex> и в графе <tex>G'</tex>, а значит, <tex>M'</tex> не может быть наибольшим паросочетанием. Поэтому предположим, что цепь <tex>P</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>, приходим к противоречию. Таким образом теорема доказана.
+Теперь допустим, что <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> его цикл нечетной длины.
+|definition= Будем называть '''соцветием''' <tex>B</tex> графа <tex>G</tex> его цикл нечётной длины.
-'''Cжатием соцветия''' назовем граф <tex>G'</tex>, полученный из <tex>G</tex> сжатием всего нечётного цикла в одну псевдо-вершину. Все рёбра, инцидентные вершинам этого цикла, становятся инцидентными псевдо-вершине в новом графе.
+'''Cжатием соцветия''' назовём граф <tex>G'</tex>, полученный из <tex>G</tex> сжатием всего нечётного цикла в одну псевдо-вершину. Все рёбра, инцидентные вершинам этого цикла, становятся инцидентными псевдо-вершине в новом графе.
 '''База соцветия''' - вершина соцветия, в которую входит ребро не из данного соцветия.
@@ Строка 31: / Строка 31: @@
 Опишем алгоритм, позволяющий находить максимальное паросочетание для произвольного графа <tex>G</tex>. Из теоремы Эдмондса понятно, что необходимо рассматривать паросочетание в сжатом графе, где его можно найти, к примеру, при помощи алгоритма [[Алгоритм Куна для поиска максимального паросочетания|Куна]], а после восстанавливать паросочетание в исходном графе.
-Основную сложность представляют операции сжатия и восстановления цветков. Чтобы эффективно это делать, для каждой вершины необходимо хранить указатель на базу цветка, которому она принадлежит, или на себя в противном случае. Предположим, что для поиска паросочетаний в сжатом графе, мы используем обход в ширину. Тогда на каждой итерации алгоритма будет строиться дерево обхода в ширину, причём путь в нём до любой вершины будет являться чередующимся путём, начинающимся с корня этого дерева. Будем класть в очередь только те вершины, расстояние от корня до которых в дереве путей четно. Также для каждой вершины, расстояние до которой нечетно, в массиве предков <tex>p[]</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>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> назначим предками друг друга. Это позволит корректно восстановить цветок, в случае, когда при восстановление увеличивающего пути, мы зайдем в нечётную вершину цикла.
 == Оценка сложности ==

@@ Строка 29: / Строка 29: @@
 ==Алгоритм вырезания соцветий==
-Опишем алгоритм, позволяющий находить максимальное паросочетание для произвольного графа <tex>G</tex>. Из теоремы Эдмондса понятно, что необходимо рассматривать паросочетание в сжатом графе, где его можно найти, к примеру, при помощи обхода в ширину, а после восстанавливать паросочетание в исходном графе.
+Опишем алгоритм, позволяющий находить максимальное паросочетание для произвольного графа <tex>G</tex>. Из теоремы Эдмондса понятно, что необходимо рассматривать паросочетание в сжатом графе, где его можно найти, к примеру, при помощи алгоритма [[Алгоритм Куна для поиска максимального паросочетания|Куна]], а после восстанавливать паросочетание в исходном графе.
 Основную сложность представляют операции сжатия и восстановления цветков. Чтобы эффективно это делать, для каждой вершины необходимо хранить указатель на базу цветка, которому она принадлежит, или на себя в противном случае. Предположим, что для поиска паросочетаний в сжатом графе, мы используем обход в ширину. Тогда на каждой итерации алгоритма будет строиться дерево обхода в ширину, причём путь в нём до любой вершины будет являться чередующимся путём, начинающимся с корня этого дерева. Будем класть в очередь только те вершины, расстояние от корня до которых в дереве путей четно. Также для каждой вершины, расстояние до которой нечетно, в массиве предков <tex>p[]</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> назначим предками друг друга. Это позволит корректно восстановить цветок, в случае, когда при восстановление увеличивающего пути, мы зайдем в нечетную вершину цикла.