Тема: Алгоритм Эдмондса нахождения наибольшего паросочетания
Доброго времени суток!
Пытаюсь разобраться в алгоритме нахождения наибольшего паросочетания в произвольных графах
http://e-maxx.ru/algo/matching_edmonds,
но никак не пойму почему асимптотика наивного алгоритма с сжатием цветка за O(n) составляет
O(n(m+n^2))=O(n^3)
Почему производится сложение m+n^2, а не умножение? Разве не нужно заново запускать обход в ширину после сжатия цветка?
К примеру, есть граф с восемью вершинами:
0 7
0 1
0 6
1 5
1 4
5 4
6 2
2 3
3 4
и пусть уже найдено паросочетание (0,1) и (4,5).
Если для поиска новой увеличивающей цепи запускать обход из вершины 6, то найдется нечетный цикл (цветок)
(1-4-5),
но в вершину 7, дающую увеличивающую цепь (6-2-3-4-5-1-0-7) мы уже не попадаем!
Цикл (1-4-5) делает цикл (6-0-1-4-3-2) нечетным за счет объединения вершин 1-4, что требует
нового обхода по графу!