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

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

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

Определение:
Соцветие [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]v[/math]. Учитывая всё вышесказанное, получаем, что путь [math]P_1(b,...v,...c,..)[/math] является увеличивающим путём в графе [math]G[/math].

Пусть теперь путь [math]P[/math] проходит через псевдо-вершину [math]B'[/math], но не начинается и не заканчивается в ней. Тогда в [math]P[/math] есть два ребра, проходящих через [math]B'[/math], пусть это [math](a,B')[/math] и [math](B',c)[/math]. Одно из них обязательно должно принадлежать паросочетанию, однако, так как база цветка не насыщена, а все остальные вершины цикла цветка насыщены рёбрами цикла, то мы приходим к противоречию (это эквивалентно случаю отсутствия ребра из [math]R_-[/math] в [math]L_+[/math]). Таким образом, этот случай просто невозможен. Теорема доказана.
[math]\triangleleft[/math]

Алгоритм

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

1) Ищем все соцветия и сжимаем их.

2) Ищем дополняющую в цепь в полученном графе обычным поиском в глубину.

3) "Разворачиваем" соцветия для восстановления цепи в исходном графе.