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

Во время поиска на уровне <math>\ell \;</math> подходящим образом выбранные древесные и недревесные дуги могут быть перемещены на более высокий уровень следующим образом. Пусть <math>T_v</math> и <math>T_w</math> – деревья в лесу <math>F_{\ell }</math>, полученные после удаления дуги (v, w), и пусть, без ограничения общности, <math>T_v</math> меньше <math>T_w</math>. Тогда <math>T_v</math> содержит не более <math>n/2^{\ell + 1}</math> вершин, поскольку <math>T_v \cup T_w \cup \{ (v, w) \} </math> было деревом на уровне <math>\ell \;</math> и выполняется инвариант (2). Следовательно, дуги уровня <math>\ell \;</math> в <math>T_v</math> могут быть перемещены на уровень <math>\ell + 1\;</math> с сохранением инвариантов. Наконец, одна за дугой посещаются недревесные дуги, инцидентные <math>T_v</math>: если дуга соединяет <math>T_v</math> и <math>T_w</math>, то дуга замены найдена и поиск останавливается; в противном случае ее уровень увеличивается на 1.

Деревья каждого леса поддерживаются таким образом, что базовые операции, необходимые для реализации вставки и удаления дуг, могут быть выполнены за время O(log n). Имеются несколько вариантов базовых структур данных, которые могут выполнить такую задачу; например, для этой цели можно использовать деревья [[Эйлеров путь|Эйлерова пути]] (ET-деревья), впервые предложенные в [17].

Помимо вставки и удаления дуг из леса, ET-деревья также могут поддерживать такие операции, как нахождение в лесу дерева, содержащего заданную вершину, вычисление размера дерева и, что еще более важно, нахождение древесных дуг уровня <math>\ell \;</math> в дереве <math>T_v</math> и недревесных дуг уровня <math>\ell \;</math>, инцидентных <math>T_v</math>. Это можно сделать за счет дополнения ET-деревьев константным количеством информации для каждой вершины; подробнее об этом – в [11].

Используя идею амортизации на базе изменений уровня, можно доказать заявленную границу времени обновления в размере <math>O(log^2 n) \; </math>. В частности, вставка дуги и повышение ее уровня требуют времени <math>O(log \; n)</math>. Поскольку это может случиться <math>O(log \; n)</math> раз, полная амортизированная стоимость вставки, включающая повышение уровня, составляет <math>O(log^2 n) \; </math>. Что касается удалений дуг, полная стоимость операций обрезания и связывания <math>O(log \; n)</math> лесов составляет <math>O(log^2 n) \; </math>; кроме того, имеется <math>O(log \; n)</math> рекурсивных вызовов процедуры Replace, каждый из них стоимостью <math>O(log \; n)</math>, плюс амортизированная стоимость операций повышений уровня. ET-деревья над <math>F_0 = F \; </math> позволяют получать ответы на запросы о связности за время <math>O(log \; n)</math> в наихудшем случае. Как было показано в [11], это время может быть уменьшено до <math>O(log \; n/log \; log \; n)</math> в случае использования <math>\Theta (log \; n)</math>-арной версии ET-деревьев.

'''Теорема 1. Динамический граф G с n вершинами может поддерживать вставку и удаление дуг за амортизированное время <math>O(log^2 \; n)</math> на одно обновление и отвечать на запросы о связности за время <math>O(log \; n/ log \; log \; n)</math> в наихудшем случае.'''

'''Теорема 2. Динамический граф G с n вершинами может поддерживать вставку и удаление дуг за амортизированное время <math>O(log \; n • (log \; log \; n)^3)</math> на одно обновление и отвечать на запросы о связности за время <math>O(log \; n/log \; log \; log \; n)</math>.'''

Задача динамической связности является базовой подзадачей множества других важных задач – таких как динамическая поддержка минимальных остовных деревьев и динамическая задача связности дуг и вершин. Кроме того, существуют различные варианты применения задачи динамической связности графа в других дисциплинах – от вычислительной биологии, в которой задача динамической связности графа оказывается полезной для динамического сопровождения поверхности молекул белка в ходе того, как молекулы претерпевают конформационные изменения [6], до обработки изображений, в которой требуется поддерживать связные компоненты растрового изображения [3].