Алгоритм вырезания соцветий — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема Эдмондса)
м (Теорема Эдмондса)
Строка 17: Строка 17:
 
|proof=
 
|proof=
 
Пусть граф <tex>G'</tex> - граф, полученный <tex>G</tex> сжатием соцветия <tex>B</tex> в псевдо-вершину <tex>B'</tex>.<br />
 
Пусть граф <tex>G'</tex> - граф, полученный <tex>G</tex> сжатием соцветия <tex>B</tex> в псевдо-вершину <tex>B'</tex>.<br />
Заметим, что достаточно рассматривать случай, когда база соцветия является свободной вершиной (не принадлежащей паросочетанию). Действительно, в противном случае в базе соцветия оканчивается чередующийся путь чётной длины, начинающийся в свободной вершине. Прочередовав паросочетание вдоль этого пути, мощность паросочетания не изменится, а база соцветия станет свободной вершиной.  
+
Заметим, что достаточно рассматривать случай, когда база соцветия является свободной вершиной (не принадлежащей паросочетанию). В противном случае в базе соцветия оканчивается чередующийся путь чётной длины, начинающийся в свободной вершине. Прочередовав паросочетание вдоль этого пути, мощность паросочетания не изменится, а база соцветия станет свободной вершиной.  
  
 
<tex>\Rightarrow</tex>
 
<tex>\Rightarrow</tex>

Версия 03:57, 26 декабря 2010

Эта статья находится в разработке!

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

Определение:
Соцветие [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]\triangleleft[/math]

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

Алгоритм

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