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

Задача заключается в эффективной поддержке информации о связности в динамически меняющемся графе. Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким, как вставка дуги, удаление дуги и обновление веса дуги. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм называется [[полностью динамический алгоритм|полностью динамическим]], если он поддерживает как вставку дуг, так и удаление дуг. [[Частично динамический алгоритм]] поддерживает либо вставку, либо удаление дуг; [[инкрементный алгоритм]] поддерживает только вставку дуг, [[декрементный алгоритм|декрементный]] – только удаление.

'''Insert(x, y)''': вставляет новую дугу между вершинами x и y.

'''Delete(x, y)''': удаляет дугу между вершинами x и y.

Здесь представлено высокоуровневое описание алгоритма для решения задачи полностью динамической связности в неориентированных графах, описанной в [11]: алгоритм, разработанный Холмом, де Лихтенбергом и Торупом, отвечает на вопрос о связности за время <math>O(log \;  n/log \; log \; n)</math> в наихудшем случае и поддерживает вставку и удаление дуг за амортизированное время <math>O(log^2 n \; )</math>.

Алгоритм поддерживает [[остовный лес]] F на динамически меняющемся графе G. Дуги в F называются [[древесная дуга|древесными дугами]]. Пусть e – древесная дуга леса F; пусть T – дерево из F, содержащее эту дугу. При удалении дуги e деревья <math>T_1</math> и <math>T_2</math>, полученные из T в результате удаления e, могут быть связаны вновь в том и только том случае, если существует недревесная дуга в G, одна конечная точка которой располагается в <math>T_1</math>, а другая – в <math>T_2</math>. Такая дуга называется [[дуга замены|дугой замены]] для e. Иными словами, если имеется дуга замены для e, T восстанавливает связность при помощи этой дуги замены; в противном случае удаление e создает новую компоненту связности в графе G.

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

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

'''Инвариант (1)''': F – максимальный остовный лес графа G, если уровни дуг интерпретировать как их веса.

Инвариант (1) следует интерпретировать следующим образом. Пусть <math>(u, v) \; </math> – недревесная дуга уровня <math>\ell (u, v) \; </math>; пусть <math>u \cdot \cdot \cdot v \; </math> – уникальный путь между u и v в F (такой путь существует, поскольку F является остовным лесом графа G). Пусть e – любая дуга из пути <math>u \cdot \cdot \cdot v \; </math>, а <math>\ell (e) \; </math> – уровень этой дуги. В силу инварианта (1), <math>\ell (e) \ge \ell (u, v) \; </math>. Поскольку это выполняется для каждой дуги пути, а по построению <math>F_{\ell(u, v)}</math> содержит все древесные дуги уровня более или равного <math>\ell (u, v) \; </math>, то весь путь содержится в <math>F_{\ell(u, v)}</math>; иначе говоря, u и v являются связанными в <math>F_{\ell(u, v)}</math>.

Заметим, что при вставке новой дуги ей присваивается уровень 0. Затем ее уровень может быть увеличен не более <math>\mathcal {b} log_2 \; n \mathcal {c}</math> раз вследствие последовательности удалений дуг. Когда удаляется дуга e = (v, w) уровня <math>\ell (e) \; </math>, алгоритм ищет дугу замены с максимально высоким уровнем, если такая существует. В силу инварианта (1) такая дуга замены имеет уровень <math>\ell \le \ell (e) \; </math>. Следовательно, процедура замены <math>Replace((u, w), \ell (e)) </math> вызывается с параметрами <math>e \; </math> и <math> \ell (e)</math>. Далее будут вкратце описаны операции, выполняемые этой процедурой.

<math>Replace((u, w), \ell ) \; </math> находит дугу замены самого высокого уровня, не превышающего <math>\ell \;</math>, если такая существует. Если на уровне <math>\ell \;</math> такой дуги не существует, имеет место один из двух вариантов: если <math>\ell > 0 \;</math>, алгоритм рекурсивно переходит на уровень <math>\ell - 1 \;</math>; в противном случае <math>\ell = 0 \;</math>, и удаление дуги (v, w) разделяет деревья v и w в графе G.

Во время поиска на уровне <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>.'''

Границы, приведенные в теоремах 1 и 2, не могут сравниваться непосредственно, поскольку каждая из них жертвует оптимальностью времени исполнения одной операции (либо запроса, либо обновления) ради улучшения времени исполнения другой.

<math>max \{ t_u, t_q \} = \Omega ((\frac{log \; n}{log \; log \; n})^2) \; </math>

Для модели битового зонда наилучшая верхняя граница на одну операцию достигается при использовании алгоритма теоремы 2; она составляет O(log2 n/ log log log n). Следовательно, разрыв между верхней и нижней границами ограничен дважды логарифмическим множителем.

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

 

Исследования в области динамической связности оставляют открытые и довольно интересные вопросы. Первый из них заключается в том, можно ли сократить разрыв между верхней и нижней границами. Заметим, что нижняя граница, обозначенная теоремой 3, говорит о том, что возможны различные соотношения между запросами и обновлениями; можем ли мы разработать структуру данных с временем выполнения одного обновления o(log n) и временем выполнения одного запроса O(poly(log n))? Это должно быть особенно интересно для приложений, в которых число запросов значительно превышает число обновлений.

Наконец, возможно ли разработать алгоритм с совпадающими границами для обновлений и запросов O(log n) для графов общего вида? Заметим, что это возможно для специального случая планарных графов [5].

* ''[[Полностью динамическая высокая связность]]

* ''[[Полностью динамическая высокая связность в планарных графах]]

* ''[[Полностью динамическое транзитивное замыкание]]