Полностью динамическая связность: верхняя и нижняя границы: различия между версиями

Для выполнения систематического поиска дуг замены алгоритм присваивает каждой дуге e уровень <math>\ell (e) \; </math> и на основе этих уровней поддерживает множество под-лесов остовного дерева F: для каждого уровня i лес <math>F_i</math> является под-лесом, порожденным древесными дугами уровня выше или равного i. Обозначив за L максимальный уровень дуги, получаем следующее:

Вначале все дуги имеют уровень 0; затем уровни прогрессивно увеличиваются, но никогда не уменьшаются. Изменения уровней дуг выполняются таким образом, чтобы поддерживать следующие инварианты, которые очевидным образом выполняются в начале процесса.