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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Паросочетание в недвудольном графе)
Строка 1: Строка 1:
 +
{{В разработке}}
 
== Паросочетание в недвудольном графе==
 
== Паросочетание в недвудольном графе==
  

Версия 21:57, 23 декабря 2010

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

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

Определение:
Паросочетание в недвудольном графе - произвольное множество ребер недвудольного графа, такое, что никакие два ребра не имеют общей вершины. Обозначается паросочетание как [math]M[/math].


Определение:
Вершины графа, инцидентные ребрам [math]M[/math], называются покрытыми, а неинцидентные - свободными.


Определение:
Чередующаяся цепь - путь в графе, для любых двух соседних ребер которого выполняется, что одно из них принадлежит паросочетанию [math]M[/math], а другое нет.


Определение:
Дополняющая цепь - чередующаяся цепь, у которой оба конца свободны.


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


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


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

Теорема:
В графе [math]G'[/math] существует увеличивающая цепь тогда и только тогда, когда существует увеличивающая цепь в [math]G[/math]
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/math]


[math]\Leftarrow[/math]
[math]\triangleleft[/math]

Алгоритм

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