52
правки
Изменения
→Алгоритм вырезания соцветий
Пусть дан произвольный граф <tex>G(V, E)</tex> и требуется найти максимальное паросочетание в нём. <br>
[[Файл:blossom1.jpg|thumb|right|Рис. 1]]
===Общая идея===
[[Файл:blossom2.jpg|thumb|right|Рис. 2]]
#Сжимаем все соцветия
#Находим паросочетания в полученном графе поиском в глубину/ширину.
return -1;
}
== Оценка сложности ==
Всего имеется <tex>V</tex> итераций, на каждой из которых выполняется обход в ширину за <tex>O(E)</tex>, кроме того, могут происходить операции сжатия цветков — их может быть <tex>O(V)</tex>. Если уметь сжимать соцветие за <tex>O(V)</tex>, то общая асимптотика алгоритма составит <tex>O(V(E + V^2)) = O(V^3)</tex>.
