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

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!

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

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


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


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

Теорема:
Пусть в графе [math]G[/math] существует соцветие [math]B[/math].
Тогда в [math]G[/math] существует удлиняющий путь тогда и только тогда, когда существует удлиняющий путь в [math]G\setminus B[/math]
Доказательство:
[math]\triangleright[/math]

Пусть граф [math]G'[/math] - граф, полученный [math]G[/math] сжатием цветка [math]B[/math] в псевдо-вершину [math]B'[/math].

[math]\Rightarrow[/math]

Пусть путь [math]P[/math] является удлиняющим в графе [math]G[/math]. Если [math]P[/math] не проходит через [math]B[/math], то тогда он будет удлиняющим и в графе [math]G'[/math].
Пусть проходит через [math]B[/math]. Тогда что путь P представляет собой некоторый путь [math]P_1[/math], не проходящий по вершинам [math]B[/math], плюс некоторый путь [math]P_2[/math], проходящий по вершинам [math]B[/math] и, возможно, другим вершинам. Но тогда путь [math]P_1 + B'[/math] будет являться удлиняющим путём в графе [math]G'[/math], что и требовалось доказать.

[math]\Leftarrow[/math]

Пусть путь [math]P[/math] является увеличивающим путём в графе [math]G'[/math]. Если [math]P[/math] не проходит через [math]B'[/math], то тогда он будет удлиняющим и в графе [math]G[/math].

Рассмотрим отдельно случай, когда [math]P[/math] начинается со сжатого соцветия [math]B'[/math], т.е. имеет вид [math](B', c, ...)[/math]. Тогда в соцветии [math]B[/math] найдётся соответствующая вершина [math]v[/math], которая связана ребром с [math]c[/math].
[math]\triangleleft[/math]

Алгоритм

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