52
правки
Изменения
м
→Паросочетание в недвудольном графе
{{Определение
|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> сжатием соцветия в одну псевдо-вершину}}
== Теорема Эдмондса ==
{{Теорема
|statement=
В графе <tex>G'</tex> существует увеличивающая цепь тогда и только тогда, когда существует увеличивающая цепь в <tex>G</tex>
|proof=
<tex>\Rightarrow</tex>
<tex>\Leftarrow</tex>
}}
==Алгоритм==
Пусть дан произвольный граф <tex>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. <br>
Для построения алгоритма по [[Теорема о максимальном паросочетании и дополняющих цепях|теореме Бержа]] нужно уметь находить дополняющую цепь.
