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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 3: Строка 3:
  
 
{{Определение
 
{{Определение
−
|definition= Паросочетание в недвудольном графе - произвольное множество ребер недвудольного графа, такое, что никакие два ребра не имеют общей вершины. Обозначается паросочетание как <tex>M</tex>.}}
+
|definition= Соцветие <tex>B</tex> графа <tex>G=(V,E)</tex> - цикл, состоящий из <tex>2k + 1</tex> ребер, из которых только <tex>k</tex> входят в соцветие <tex>B</tex>.}}
 
{{Определение
 
{{Определение
−
|definition= Вершины графа, инцидентные ребрам <tex>M</tex>, называются покрытыми, а неинцидентные - свободными.}}
+
|definition= Cжатие соцветия - граф <tex>G'</tex>, полученный из <tex>G</tex> сжатием соцветия в одну псевдо-вершину.}}
−
{{Определение
 
−
|definition= Чередующаяся цепь - путь в графе, для любых двух соседних ребер которого выполняется, что одно из них принадлежит паросочетанию <tex>M</tex>, а другое нет.}}
 
−
{{Определение
 
−
|definition= Дополняющая цепь - чередующаяся цепь, у которой оба конца свободны.}}
 
−
{{Определение
 
−
|definition= Соцветие <tex>B</tex> графа <tex>G=(V,E)</tex> - цикл, состоящий из <tex>2k + 1</tex> ребер, из которых только <tex>k</tex> входят в соцветие <tex>M</tex>}}
 
−
{{Определение
 
−
|definition= Cжатие соцветия - граф <tex>G'</tex>, полученный из <tex>G</tex> сжатием соцветия в одну псевдо-вершину}}
 
  
 
== Теорема Эдмондса ==
 
== Теорема Эдмондса ==
Строка 19: Строка 11:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
−
В графе <tex>G'</tex> существует увеличивающая цепь тогда и только тогда, когда существует увеличивающая цепь в <tex>G</tex>
+
Пусть в графе <tex>G</tex> существует соцветие <tex>B</tex>.<br />
 +
Тогда в <tex>G</tex> существует удлиняющий путь тогда и только тогда, когда существует удлиняющий путь в <tex>G\setminus B</tex>
 
|proof=
 
|proof=
 +
Пусть граф <tex>G'</tex> - граф, полученный <tex>G</tex> сжатием цветка <tex>B</tex> в псевдо-вершину <tex>B'</tex>.<br />
 +
 
<tex>\Rightarrow</tex>
 
<tex>\Rightarrow</tex>
  
 +
Пусть путь <tex>P</tex> является удлиняющим в графе <tex>G</tex>. Если <tex>P</tex> не проходит через <tex>B</tex>, то тогда он будет удлиняющим и в графе <tex>G'</tex>. <br />
 +
Пусть  проходит через <tex>B</tex>. Тогда что путь P представляет собой некоторый путь <tex>P_1</tex>, не проходящий по вершинам <tex>B</tex>, плюс некоторый путь <tex>P_2</tex>, проходящий по вершинам <tex>B</tex> и, возможно, другим вершинам. Но тогда путь <tex>P_1 + B'</tex>  будет являться удлиняющим путём в графе <tex>G'</tex>, что и требовалось доказать.
  
 
<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>B'</tex>, т.е. имеет вид <tex>(B', c, ...)</tex>. Тогда в соцветии <tex>B</tex> найдётся соответствующая вершина <tex>v</tex>, которая связана ребром с <tex>c</tex>.
 
}}
 
}}
  

Версия 13:55, 24 декабря 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]\triangleleft[/math]

Алгоритм

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_вырезания_соцветий&oldid=6259»