52
правки
Изменения
м
|definition= Вершины графа, инцидентные ребрам <tex>M</tex>, называются покрытыми, а неинцидентные - свободными.}} {{Определение|definition= Чередующаяся цепь - путь в графе, для любых двух соседних ребер которого выполняется, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}{{Определение|definition= Дополняющая цепь - чередующаяся цепь, у которой оба конца свободны.}}{{Определение|definition= Соцветие <tex>B</tex> графа <tex>G=(V,E)</tex> - цикл, состоящий из <tex>2k + 1</tex> ребер, из которых только <tex>k</tex> входят в соцветие <tex>M</tex>}}{{Определение|definition= Cжатие соцветия - граф <tex>G'</tex>, полученный из <tex>G</tex> сжатием соцветия в одну псевдо-вершину.}}
В Пусть в графе <tex>G'</tex> существует увеличивающая цепь соцветие <tex>B</tex>.<br />Тогда в <tex>G</tex> существует удлиняющий путь тогда и только тогда, когда существует увеличивающая цепь удлиняющий путь в <tex>G\setminus B</tex>
Нет описания правки
{{Определение
|definition= Паросочетание в недвудольном графе Соцветие <tex>B</tex> графа <tex>G=(V,E)</tex> - произвольное множество цикл, состоящий из <tex>2k + 1</tex> ребер недвудольного графа, такое, что никакие два ребра не имеют общей вершины. Обозначается паросочетание как из которых только <tex>k</tex> входят в соцветие <tex>MB</tex>.}}
{{Определение
== Теорема Эдмондса ==
{{Теорема
|statement=
|proof=
Пусть граф <tex>G'</tex> - граф, полученный <tex>G</tex> сжатием цветка <tex>B</tex> в псевдо-вершину <tex>B'</tex>.<br />
<tex>\Rightarrow</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>\Leftarrow</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>.
}}
