4817
правок
Полностью динамическая связность: верхняя и нижняя границы: различия между версиями
Материал из WEGA
Полностью динамическая связность: верхняя и нижняя границы (посмотреть исходный код)
Версия от 15:29, 12 июля 2014
, 12 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 45: | Строка 45: | ||
Во время поиска на уровне <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. | Во время поиска на уровне <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-деревья), впервые предложенные в [ | Деревья каждого леса поддерживаются таким образом, что базовые операции, необходимые для реализации вставки и удаления дуг, могут быть выполнены за время O(log n). Имеются несколько вариантов базовых структур данных, которые могут выполнить такую задачу; например, для этой цели можно использовать деревья [[Эйлеров путь|Эйлерова пути]] (ET-деревья), впервые предложенные в [17]. | ||
Помимо вставки и удаления дуг из леса, ET-деревья также могут поддерживать такие операции, как нахождение в лесу дерева, содержащего заданную вершину, вычисление размера дерева и, что еще более важно, нахождение древесных дуг уровня <math>\ell \;</math> в дереве | Помимо вставки и удаления дуг из леса, ET-деревья также могут поддерживать такие операции, как нахождение в лесу дерева, содержащего заданную вершину, вычисление размера дерева и, что еще более важно, нахождение древесных дуг уровня <math>\ell \;</math> в дереве <math>T_v</math> и недревесных дуг уровня <math>\ell \;</math>, инцидентных <math>T_v</math>. Это можно сделать за счет дополнения ET-деревьев константным количеством информации для каждой вершины; подробнее об этом – в [11]. | ||
Используя идею амортизации на базе изменений уровня, можно доказать заявленную границу времени обновления в размере O( | |||
Используя идею амортизации на базе изменений уровня, можно доказать заявленную границу времени обновления в размере <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-деревьев. | |||
