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

Материал из WEGA
Перейти к навигации Перейти к поиску
 
(не показано 17 промежуточных версий 1 участника)
Строка 4: Строка 4:


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




Строка 11: Строка 11:
'''Connected(u, v)''': возвращает значение «истинно», если вершины u и v принадлежат к одной и той же связной компоненте графа, в противном случае возвращает значение «ложно».
'''Connected(u, v)''': возвращает значение «истинно», если вершины u и v принадлежат к одной и той же связной компоненте графа, в противном случае возвращает значение «ложно».


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


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


== Основные результаты ==
== Основные результаты ==
Здесь представлено высокоуровневое описание алгоритма для решения задачи полностью динамической связности в неориентированных графах, описанной в [11]: алгоритм, разработанный Холмом, де Лихтенбергом и Торупом, отвечает на вопрос о связности за время <math>O(log \;  n/log \; log \; n)</math> в наихудшем случае и поддерживает вставку и удаление дуг за амортизированное время <math>O(log^2 n \; )</math>.
Здесь представлено высокоуровневое описание алгоритма для решения задачи полностью динамической связности в неориентированных графах, описанной в [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.
Алгоритм поддерживает [[остовный лес]] 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 максимальный уровень дуги, получаем следующее:
Для выполнения систематического поиска ребер замены алгоритм присваивает каждому ребру e уровень <math>\ell (e) \; </math> и на основе этих уровней поддерживает множество под-лесов остовного дерева F: для каждого уровня i лес <math>F_i \; </math> является под-лесом, порожденным древесными ребрами уровня выше или равного i. Обозначив за L максимальный уровень ребра, получаем следующее:


F = F0 2 F1 2 F2 2 • • • 2 FL :
<math>F = F_0 \supseteq F_1 \supseteq F_2 \supseteq ... \supseteq F_L.</math>


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


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


Инвариант (2): Число вершин каждого дерева Fi не превышает n/2i.
'''Инвариант (1)''': F – максимальный остовный лес графа G, если уровни ребер интерпретировать как их веса.


Инвариант (1) следует интерпретировать следующим образом. Пусть (u, v) – недревесная дуга уровня l(u, v); пусть u ■ ■ ■ v – уникальный путь между u и v в F (такой путь существует, поскольку F является остовным лесом графа G). Пусть e – любая дуга из пути u ■ ■ ■ v, а l(e) – уровень этой дуги. В силу инварианта (1), l(e) > l(u, v). Поскольку это выполняется для каждой дуги пути, а по построению F^U;V) содержит все древесные дуги уровня более l(u, v), то весь путь содержится в F^U;V); иначе говоря, u и v являются связанными в F^uv).
'''Инвариант (2)''': Число вершин каждого дерева <math>F_i</math> не превышает <math>n/2^i \; </math>.
Из инварианта (2) следует, что максимальное число уровней равно L < blog2 nc.


Заметим, что при вставке новой дуги ей присваивается уровень 0. Затем ее уровень может быть увеличен не более bl°g2 раз вследствие последовательности удалений дуг. Когда удаляется дуга e = (v, w) уровня i(e), алгоритм ищет дугу замены с максимально высоким уровнем, если такая существует. В силу инварианта (1) такая дуга замены имеет уровень I < l{e). Следовательно, процедура замены Replace((u, w),l(e)) вызывается с параметрами e и l(e). Далее будут вкратце описаны операции, выполняемые этой процедурой.


Replace((u, w), I) находит дугу замены самого высокого уровня l< £, если такая существует. Если на уровне I такой дуги не существует, имеет место один из двух вариантов: если £ > 0, алгоритм рекурсивно переходит на уровень I — 1; в противном случае 1 = 0, и удаление дуги (v, w) разделяет деревья v и w в графе 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>.


Во время поиска на уровне I подходящим образом выбранные древесные и недревесные дуги могут быть перемещены на более высокий уровень следующим образом. Пусть Tv и Tw – деревья в лесу Fi, полученные после удаления дуги (v, w), и пусть, без ограничения общности, Tv меньше Tw. Тогда Tv содержит не более и/2 вершин, поскольку Tv [ Tw [ f(v, w)g было деревом на уровне I и выполняется инвариант (2). Следовательно, дуги уровня I в Tv могут быть перемещены на уровень I + 1 с сохранением инвариантов. Наконец, одна за дугой посещаются недревесные дуги, инцидентные Tv: если дуга соединяет Tv и Tw, то дуга замены найдена и поиск останавливается; в противном случае ее уровень увеличивается на 1.
Из инварианта (2) следует, что максимальное число уровней равно <math>L \le \mathcal {b} log_2 \; n \mathcal {c}</math>.


Деревья каждого леса поддерживаются таким образом, что базовые операции, необходимые для реализации вставки и удаления дуг, могут быть выполнены за время O(log n). Имеются несколько вариантов базовых структур данных, которые могут выполнить такую задачу; например, для этой цели можно использовать деревья Эйлерова пути (ET-деревья), впервые предложенные в [    ].
Заметим, что при вставке нового ребра ему присваивается уровень 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>. Далее будут вкратце описаны операции, выполняемые этой процедурой.
Помимо вставки и удаления дуг из леса, ET-деревья также могут поддерживать такие операции, как нахождение в лесу дерева, содержащего заданную вершину, вычисление размера дерева и, что еще более важно, нахождение древесных дуг уровня I в дереве Tv и недревесных дуг уровня I, инцидентных Tv. Это можно сделать за счет дополнения ET-деревьев константным количеством информации для каждой вершины; подробнее об этом – в [11].


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


<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.


Теорема 1. Динамический граф G с n вершинами может поддерживать вставку и удаление дуг за амортизированное время O(log2 n) на одно обновление и отвечать на запросы о связности за время O(log n/loglog n) в наихудшем случае.


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


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


Используя идею амортизации на базе изменений уровня, можно доказать заявленную границу времени обновления в размере <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 и 2, не могут сравниваться непосредственно, поскольку каждая из них жертвует оптимальностью времени исполнения одной операции (либо запроса, либо обновления) ради улучшения времени исполнения другой.


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


Наилучшая известная нижняя граница для задачи динамической связности имеет место при использовании вычислительной модели битового зонда (bit-probe model); ее предложили Патраку и Тарнифа [ ]. Модель битового зонда представляет собой вариант модели клеточного зонда (cell-probe model) с однобитными клетками. В этой модели память организована в виде клеток, и алгоритм может производить чтение из клетки или запись в нее за константное время. Количество клеточных зондов рассматривается в качестве меры сложности. Формальное определение этой модели можно найти в [13].


Позднее Торуп [18] предложил еще одну структуру данных, которая позволяет обеспечить несколько иные временные границы:


Теорема 3. Рассмотрим реализацию битового зонда для задачи динамической связности, в которой операции обновления выполняются за амортизированное время tu, а запросы – за ожидаемое время tq. Тогда для среднего случая распределения входных данных tu = Q (log2n/log2(tu + tq)). В частности,
2!
((  log n
\\ log log n


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


Для модели битового зонда наилучшая верхняя граница на одну операцию достигается при использовании алгоритма теоремы 2; она составляет O(log2 n/ log log log n). Следовательно, разрыв между верхней и нижней границами ограничен дважды логарифмическим множителем.
 
Границы, приведенные в теоремах 1 и 2, не могут сравниваться непосредственно, поскольку каждая из них жертвует оптимальностью времени выполнения одной операции (либо запроса, либо обновления) ради улучшения времени выполнения другой.
 
 
Наилучшая известная нижняя граница для задачи динамической связности имеет место при использовании вычислительной модели [[битовый зонд|битового зонда]] (bit-probe model); ее предложили Патраку и Тарнифа [16]. Модель битового зонда представляет собой вариант модели [[клеточный зонд|клеточного зонда]] (cell-probe model) с однобитными клетками. В этой модели память организована в виде клеток, и алгоритм может производить чтение из клетки или запись в нее за константное время. Количество клеточных зондов рассматривается в качестве меры сложности. Формальное определение этой модели можно найти в [13].
 
 
Теорема 3. Рассмотрим реализацию битового зонда для задачи динамической связности, в которой операции обновления выполняются за ожидаемое амортизированное время <math>t_u</math>, а запросы – за ожидаемое время <math>t_q</math>. Тогда для среднего случая распределения входных данных <math>t_u = \Omega (log^2 \; n/ log^2 \; (t_u + t_q))</math>. В частности,
 
<math>max \{ t_u, t_q \} = \Omega \left ( \left ( \frac{log \; n}{log \; log \; n} \right ) ^2 \right ) \; </math>
 
 
Для модели битового зонда наилучшая верхняя граница на одну операцию достигается при использовании алгоритма теоремы 2; она составляет <math>O(log^2 \; n/ log \; log \; log \; n)</math>. Следовательно, разрыв между верхней и нижней границами ограничен дважды логарифмическим множителем.


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


== Открытые вопросы ==
== Открытые вопросы ==
Исследования в области динамической связности оставляют открытые и довольно интересные вопросы. Первый из них заключается в том, можно ли сократить разрыв между верхней и нижней границами. Заметим, что нижняя граница, обозначенная теоремой 3, говорит о том, что возможны различные соотношения между запросами и обновлениями; можем ли мы разработать структуру данных с временем выполнения одного обновления o(log n) и временем выполнения одного запроса O(poly(log n))? Это должно быть особенно интересно для приложений, в которых число запросов значительно превышает число обновлений.
Исследования в области динамической связности оставляют открытые и довольно интересные вопросы. Первый из них заключается в том, можно ли сократить разрыв между верхней и нижней границами. Заметим, что нижняя граница, обозначенная теоремой 3, говорит о том, что возможны различные соотношения между запросами и обновлениями; можем ли мы разработать структуру данных с временем выполнения одного обновления <math>o(log \; n)</math> и временем выполнения одного запроса <math>O(poly(log \; n))</math>? Это должно быть особенно интересно для приложений, в которых число запросов значительно превышает число обновлений.
Наконец, возможно ли разработать алгоритм с совпадающими границами для обновлений и запросов O(log n) для графов общего вида? Заметим, что это возможно для специального случая планарных графов [5].


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


== Экспериментальные результаты ==
== Экспериментальные результаты ==
Строка 85: Строка 90:
* ''[[Динамические деревья]]
* ''[[Динамические деревья]]
* ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]]
* ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]]
* ''[[Полностью динамическая высокая связность]]
* ''[[Полностью динамическая связность высоких степеней]]
* ''[[Полностью динамическая высокая связность в планарных графах]]
* ''[[Полностью динамическая связность высоких степеней в планарных графах]]
* ''[[Полностью динамические минимальные остовные деревья]]
* ''[[Полностью динамические минимальные остовные деревья]]
* ''[[Полностью динамическая проверка на планарность]]
* ''[[Полностью динамическая проверка на планарность]]
* ''[[Полностью динамическое транзитивное замыкание]]
* ''[[Полностью динамический алгоритм транзитивного замыкания]]
 


== Литература ==
== Литература ==
Строка 131: Строка 135:


18. Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proc. 32nd ACM Symposium on Theory of Computing (STOC), 2000, pp. 343-350
18. Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proc. 32nd ACM Symposium on Theory of Computing (STOC), 2000, pp. 343-350
[[Категория: Совместное определение связанных терминов]]

Текущая версия от 10:41, 7 декабря 2024

Ключевые слова и синонимы

динамически связные компоненты; динамические остовные леса


Постановка задачи

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


В задаче полностью динамической связности нам требуется поддержка неориентированного графа G = (V, E) и выполнение последовательности следующих операций в различном порядке:

Connected(u, v): возвращает значение «истинно», если вершины u и v принадлежат к одной и той же связной компоненте графа, в противном случае возвращает значение «ложно».

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

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

Основные результаты

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

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


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

[math]\displaystyle{ F = F_0 \supseteq F_1 \supseteq F_2 \supseteq ... \supseteq F_L. }[/math]

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


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

Инвариант (2): Число вершин каждого дерева [math]\displaystyle{ F_i }[/math] не превышает [math]\displaystyle{ n/2^i \; }[/math].


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

Из инварианта (2) следует, что максимальное число уровней равно [math]\displaystyle{ L \le \mathcal {b} log_2 \; n \mathcal {c} }[/math].

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


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


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

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

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


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


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


Позднее Торуп [18] предложил еще одну структуру данных, которая позволяет обеспечить несколько иные временные границы:


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


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


Наилучшая известная нижняя граница для задачи динамической связности имеет место при использовании вычислительной модели битового зонда (bit-probe model); ее предложили Патраку и Тарнифа [16]. Модель битового зонда представляет собой вариант модели клеточного зонда (cell-probe model) с однобитными клетками. В этой модели память организована в виде клеток, и алгоритм может производить чтение из клетки или запись в нее за константное время. Количество клеточных зондов рассматривается в качестве меры сложности. Формальное определение этой модели можно найти в [13].


Теорема 3. Рассмотрим реализацию битового зонда для задачи динамической связности, в которой операции обновления выполняются за ожидаемое амортизированное время [math]\displaystyle{ t_u }[/math], а запросы – за ожидаемое время [math]\displaystyle{ t_q }[/math]. Тогда для среднего случая распределения входных данных [math]\displaystyle{ t_u = \Omega (log^2 \; n/ log^2 \; (t_u + t_q)) }[/math]. В частности,

[math]\displaystyle{ max \{ t_u, t_q \} = \Omega \left ( \left ( \frac{log \; n}{log \; log \; n} \right ) ^2 \right ) \; }[/math]


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

Применение

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

Открытые вопросы

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

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

Экспериментальные результаты

Обстоятельное эмпирическое исследование динамических алгоритмов связности было проведено в работах [1,12].


См. также

Литература

1. Alberts, D., Cattaneo, G., Italiano, G.F.: An empirical study of dynamic graph algorithms. ACM J. Exp. Algorithmics 2 (1997)

2. Beame, P., Fich, F.E.: Optimal bounds for the predecessor problem and related problems. J. Comp. Syst. Sci. 65(1), 38-72 (2002)

3. Eppstein, D.: Dynamic Connectivity in Digital Images. Inf. Process. Lett. 62(3), 121-126 (1997)

4. Eppstein, D., Galil, Z., Italiano, G.F., Nissenzweig, A.: Sparsification - a technique for speeding up dynamic graph algorithms. J. Assoc. Comp. Mach. 44(5), 669-696 (1997)

5. Eppstein, D., Italiano, G.F., Tamassia, R.,Tarjan, R.E., Westbrook, J., Yung, M.: Maintenance of a minimum spanning forest in a dynamic planegraph. J. Algorithms 13, 33-54 (1992)

6. Eyal, E., Halperin, D.: Improved Maintenance of Molecular Surfaces Using Dynamic Graph Connectivity. in: Proc. 5th International Workshop on Algorithms in Bioinformatics (WABI 2005), Mallorca, Spain, 2005, pp.401-413

7. Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees. SIAM J. Comp. 14, 781-798 (1985)

8. Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. In: Proc. 32nd Symp. Foundations of Computer Science, 1991, pp. 632-641

9. Henzinger, M.R., Fredman, M.L.: Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica 22(3), 351-362(1998)

10. Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM 46(4),502-516(1999)

11. Holm, J., de Lichtenberg, K.,Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48, 723-760 (2001)

12. Iyer, R., Karger, D., Rahul, H.,Thorup, M.: An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms. ACM J. Exp. Algorithmics 6 (2001)

13. Miltersen, P.B.: Cell probe complexity-a survey. In: 19th Conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Advances in Data Structures Workshop, 1999

14. Miltersen, P.B., Subramanian, S., Vitter, J.S., Tamassia, R.: Complexity models for incremental computation. In: Ausiello, G., Italiano, G.F. (eds.) Special Issue on Dynamic and On-line Algorithms. Theor. Comp. Sci. 130(1), 203-236 (1994)

15. Patrascu, M., Demain, E.D.: Lower Bounds for Dynamic Connectivity. In: Proc. 36th ACM Symposium on Theory of Computing (STOC), 2004, pp. 546-553

16. Patrascu, M., Tarnija, C.: On Dynamic Bit-Probe Complexity, Theoretical Computer Science, Special Issue on ICALP'05. In: Italiano, G.F., Palamidessi, С (eds.) vol. 380, pp. 127-142 (2007)

A preliminary version in Proc. 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), 2005, pp. 969-981

17. Tarjan, R.E., Vishkin, U.: An efficient parallel biconnectivity algorithm. SIAM J. Comp. 14,862-874 (1985)

18. Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proc. 32nd ACM Symposium on Theory of Computing (STOC), 2000, pp. 343-350