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

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

Определение:

Паросочетание в недвудольном графе - произвольное множество ребер недвудольного графа, такое, что никакие два ребра не имеют общей вершины. Обозначается паросочетание как [math]M[/math].

Определение:

Вершины графа, инцидентные ребрам [math]M[/math], называются покрытыми, а неинцидентные - свободными.

Определение:

Чередующаяся цепь - путь в графе, для любых двух соседних ребер которого выполняется, что одно из них принадлежит паросочетанию [math]M[/math], а другое нет.

Определение:

Дополняющая цепь - чередующаяся цепь, у которой оба конца свободны.

Определение:

Соцветие [math]B[/math] графа [math]G=(V,E)[/math] - цикл, состоящий из [math]2k + 1[/math] ребер, из которых только [math]k[/math] входят в соцветие [math]M[/math]

Определение:

Cжатие соцветия - граф [math]G'[/math], полученный из [math]G[/math] сжатием соцветия в одну псевдо-вершину

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

Теорема:

В графе [math]G'[/math] существует увеличивающая цепь тогда и только тогда, когда существует увеличивающая цепь в [math]G[/math]

Доказательство:

[math]\triangleright[/math]

[math]\Rightarrow[/math] [math]\Leftarrow[/math]

[math]\triangleleft[/math]

Алгоритм

Пусть дан произвольный граф [math]G(V, E)[/math] и требуется найти максимальное паросочетание в нём.
Для построения алгоритма по теореме Бержа нужно уметь находить дополняющую цепь.