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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Теорема Эдмондса)
Строка 26: Строка 26:
 
<tex>\Leftarrow</tex>
 
<tex>\Leftarrow</tex>
  
Пусть путь <tex>P</tex> является увеличивающим путём в графе <tex>G'</tex>. Если <tex>P</tex> не проходит через <tex>B'</tex>, то тогда он будет удлиняющим и в графе <tex>G</tex>. <br />
+
Пусть путь <tex>P</tex> является удлиняющим путём в графе <tex>G'</tex>. Если <tex>P</tex> не проходит через <tex>B'</tex>, то тогда он будет удлиняющим и в графе <tex>G</tex>. <br />
  
 
Рассмотрим отдельно случай, когда <tex>P</tex> начинается со сжатого соцветия <tex>B'</tex>, т.е. имеет вид <tex>(B', c, ...)</tex>. Тогда в соцветии <tex>B</tex> найдётся соответствующая вершина <tex>v</tex>, которая связана ребром с <tex>c</tex>. Заметим, что из базы соцветия всегда найдётся чередующийся путь чётной длины до вершины <tex>v</tex>. Учитывая всё вышесказанное, получаем, что путь <tex>P_1(b,...v,...c,..)</tex> является увеличивающим путём в графе <tex>G</tex>.
 
Рассмотрим отдельно случай, когда <tex>P</tex> начинается со сжатого соцветия <tex>B'</tex>, т.е. имеет вид <tex>(B', c, ...)</tex>. Тогда в соцветии <tex>B</tex> найдётся соответствующая вершина <tex>v</tex>, которая связана ребром с <tex>c</tex>. Заметим, что из базы соцветия всегда найдётся чередующийся путь чётной длины до вершины <tex>v</tex>. Учитывая всё вышесказанное, получаем, что путь <tex>P_1(b,...v,...c,..)</tex> является увеличивающим путём в графе <tex>G</tex>.
 +
 +
Пусть теперь путь <tex>P</tex> проходит через псевдо-вершину <tex>B'</tex>, но не начинается и не заканчивается в ней. Тогда в <tex>P</tex> есть два ребра, проходящих через <tex>B'</tex>, пусть это <tex>(a,B')</tex> и <tex>(B',c)</tex>. Одно из них обязательно должно принадлежать паросочетанию, однако, так как база цветка не насыщена, а все остальные вершины цикла цветка  насыщены рёбрами цикла, то мы приходим к противоречию (это эквивалентно [[Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах|случаю отсутствия ребра из <tex>R_-</tex> в <tex>L_+</tex>]]). Таким образом, этот случай просто невозможен. Теорема доказана.
 
}}
 
}}
  
Пусть теперь путь <tex>P</tex> проходит через псевдо-вершину <tex>B'</tex>, но не начинается и не заканчивается в ней. Тогда в <tex>P</tex> есть два ребра, проходящих через <tex>B'</tex>, пусть это <tex>(a,B')</tex> и <tex>(B',c)</tex>. Одно из них обязательно должно принадлежать паросочетанию, однако, так как база цветка не насыщена, а все остальные вершины цикла цветка  насыщены рёбрами цикла, то мы приходим к противоречию. Таким образом, этот случай просто невозможен. Теорема доказана.
+
==Алгоритм==
  
==Алгоритм==
 
 
Пусть дан произвольный граф <tex>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. <br>
 
Пусть дан произвольный граф <tex>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. <br>
Для построения алгоритма по [[Теорема о максимальном паросочетании и дополняющих цепях|теореме Бержа]] нужно уметь находить дополняющую цепь.
+
 
 +
1) Ищем все соцветия и сжимаем их.
 +
 
 +
2) Ищем дополняющую в цепь в полученном графе обычным поиском в глубину.
 +
 
 +
3) "Разворачиваем" соцветия для восстановления цепи в исходном графе.

Версия 10:15, 29 декабря 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]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) "Разворачиваем" соцветия для восстановления цепи в исходном графе.