Изменения

Перейти к: навигация, поиск

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

2865 байт добавлено, 23:12, 15 января 2011
Алгоритм вырезания соцветий
Пусть дан произвольный граф <tex>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. <br>
 
===Общая идея===
 
#Сжимаем все соцветия
#Находим паросочетания в полученном графе поиском в глубину/ширину.
#Разжимаем соцветия, восстанавливая паросочетание.
 
===Пошаговое представление===
 
Алгоритм строит лес, содержащий деревья удлиняющих путей, корнями которых являются вершины не из паросочетания.
Также для каждой вершины <tex>v</tex> алгоритм в <tex>p(v)</tex> будет хранить родителя в дереве обхода.
Сначала проинициализируем пометим все вершины из паросочетания , включенные в паросочетание, непосещенными, все остальные - четными. Пока существует удлиняющий путь или пока есть непроверенное ребро из четной вершины <tex>v</tex>:#Выберем любое непроверенное ребро<tex>(v, w)</tex> из четной вершины <tex>v</tex> и проверяем:#*Вершина <tex>w</tex> нечетное - ничего не делаем. Такая ситуация возникает, когда <tex>(v, w)</tex> ребро из паросочетания или не из паросочетания#*Вершина <tex>w</tex> включено в паросочетание и непосещенное. Тогда помечаем <tex>w</tex> нечетным, а <tex>mate(w)</tex> четным. Присваиваем <tex>p(w) \gets v</tex>, а также <tex>p(mate(w)) \gets w</tex>#*<tex>w</tex> четное; вершины <tex>w, v</tex> лежат в разных деревьях - нашли удлиняющий путь от корня дерева, содержащего вершину <tex>v</tex> до корня дерева, содержащего вершину <tex>w</tex>.#*<tex>w</tex> четное; вершины <tex>w, v</tex> лежат в одном дереве - нашли соцветие. Пусть <tex>u</tex> - наименьший общий предок вершин <tex>v</tex> и <tex>w</tex>. Сожмем соцветие в псевдо-вершину <tex>b</tex>, <tex>p(b) \gets p(u)</tex>, а также для каждой вершины <tex>x</tex> в соцветии определим <tex>p(x) \gets b</tex> ===Псевдокод=== '''Edmonds''' { '''for''' <tex>u \in V</tex>''' if (вершина u не в паросочетании)''' { '''int''' '''last_v''' = '''find_augment_path''' (u); '''if (last_v != -1)''' '''выполнить чередование вдоль пути из u в last_v;''' } } int find_augment_path (root) { обход в ширину: v = текущая_вершина; for <tex>(v,w) \in E</tex> если обнаружили цикл нечётной длины, сжать его если пришли в свободную вершину, return если пришли в несвободную вершину, то добавить в очередь смежную ей в паросочетании return -1; }
52
правки

Навигация