1294
правки
Полностью динамическая связность: верхняя и нижняя границы: различия между версиями
Материал из WEGA
Полностью динамическая связность: верхняя и нижняя границы (посмотреть исходный код)
Версия от 03:41, 7 декабря 2024
, 7 декабря 2024→Литература
Irina (обсуждение | вклад) |
KVN (обсуждение | вклад) |
||
| (не показаны 22 промежуточные версии 1 участника) | |||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача заключается в эффективной поддержке информации о связности в динамически меняющемся графе. Динамический алгоритм на графе поддерживает заданное свойство | Задача заключается в эффективной поддержке информации о связности в динамически меняющемся графе. Динамический алгоритм на графе поддерживает заданное свойство P графа, подверженного динамическим изменениям – таким, как вставка ребра, удаление ребра и обновление веса ребра. Динамический алгоритм должен быстро обрабатывать запросы о свойстве P, а также выполнять операции обновления быстрее, чем вычислять то же самое с нуля при помощи самого быстрого статического алгоритма. Алгоритм называется [[полностью динамический алгоритм|полностью динамическим]], если он поддерживает как вставку ребер, так и удаление ребер. [[Частично динамический алгоритм]] поддерживает либо вставку, либо удаление ребер; [[инкрементный алгоритм]] поддерживает только вставку ребер, [[декрементный алгоритм|декрементный]] – только удаление. | ||
| Строка 11: | Строка 11: | ||
'''Connected(u, v)''': возвращает значение «истинно», если вершины u и v принадлежат к одной и той же связной компоненте графа, в противном случае возвращает значение «ложно». | '''Connected(u, v)''': возвращает значение «истинно», если вершины u и v принадлежат к одной и той же связной компоненте графа, в противном случае возвращает значение «ложно». | ||
'''Insert(x, y)''': вставляет | '''Insert(x, y)''': вставляет новое ребро между вершинами x и y. | ||
'''Delete | '''Delete(x, y)''': удаляет ребро между вершинами x и y. | ||
== Основные результаты == | == Основные результаты == | ||
Здесь представлено высокоуровневое описание алгоритма для решения задачи полностью динамической связности в неориентированных графах, описанной в [ ]: алгоритм, разработанный Холмом, де Лихтенбергом и Торупом, отвечает на вопрос о связности за время O(log n/log log n) в наихудшем случае и поддерживает вставку и удаление | Здесь представлено высокоуровневое описание алгоритма для решения задачи полностью динамической связности в неориентированных графах, описанной в [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 максимальный уровень ребра, получаем следующее: | |||
<math>F = F_0 \supseteq F_1 \supseteq F_2 \supseteq ... \supseteq F_L.</math> | |||
Вначале все ребра имеют уровень 0; затем уровни прогрессивно увеличиваются, но никогда не уменьшаются. Изменения уровней ребер выполняются таким образом, чтобы поддерживать следующие инварианты, которые очевидным образом выполняются в начале процесса. | |||
'''Инвариант (1)''': F – максимальный остовный лес графа G, если уровни ребер интерпретировать как их веса. | |||
'''Инвариант (2)''': Число вершин каждого дерева <math>F_i</math> не превышает <math>n/2^i \; </math>. | |||
Инвариант (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>. | |||
Из инварианта (2) следует, что максимальное число уровней равно <math>L \le \mathcal {b} log_2 \; n \mathcal {c}</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> в наихудшем случае.''' | |||
Позднее Торуп [18] предложил еще одну структуру данных, которая позволяет обеспечить несколько иные временные границы: | |||
'''Теорема 2. Динамический граф G с n вершинами может поддерживать вставку и удаление ребер за амортизированное время <math>O(log \; n • (log \; log \; n)^3)</math> на одно обновление и отвечать на запросы о связности за время <math>O(log \; n/log \; log \; log \; n)</math>.''' | |||
Границы, приведенные в теоремах 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], до обработки изображений, в которой требуется поддерживать связные компоненты растрового изображения [3]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Исследования в области динамической связности оставляют открытые и довольно интересные вопросы. Первый из них заключается в том, можно ли сократить разрыв между верхней и нижней границами. Заметим, что нижняя граница, обозначенная теоремой 3, говорит о том, что возможны различные соотношения между запросами и обновлениями; можем ли мы разработать структуру данных с временем выполнения одного обновления o(log n) и временем выполнения одного запроса O(poly(log n))? Это должно быть особенно интересно для приложений, в которых число запросов значительно превышает число обновлений | Исследования в области динамической связности оставляют открытые и довольно интересные вопросы. Первый из них заключается в том, можно ли сократить разрыв между верхней и нижней границами. Заметим, что нижняя граница, обозначенная теоремой 3, говорит о том, что возможны различные соотношения между запросами и обновлениями; можем ли мы разработать структуру данных с временем выполнения одного обновления <math>o(log \; n)</math> и временем выполнения одного запроса <math>O(poly(log \; n))</math>? Это должно быть особенно интересно для приложений, в которых число запросов значительно превышает число обновлений. | ||
Наконец, возможно ли разработать алгоритм с совпадающими границами для обновлений и запросов <math>O(log \; n)</math> для графов общего вида? Заметим, что это возможно для специального случая планарных графов [5]. | |||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
| Строка 84: | Строка 90: | ||
* ''[[Динамические деревья]] | * ''[[Динамические деревья]] | ||
* ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | * ''[[Полностью динамический алгоритм нахождения кратчайших путей между всеми парами]] | ||
* ''[[Полностью динамическая | * ''[[Полностью динамическая связность высоких степеней]] | ||
* ''[[Полностью динамическая | * ''[[Полностью динамическая связность высоких степеней в планарных графах]] | ||
* ''[[Полностью динамические минимальные остовные деревья]] | * ''[[Полностью динамические минимальные остовные деревья]] | ||
* ''[[Полностью динамическая проверка на планарность]] | * ''[[Полностью динамическая проверка на планарность]] | ||
* ''[[Полностью | * ''[[Полностью динамический алгоритм транзитивного замыкания]] | ||
== Литература == | == Литература == | ||
| Строка 130: | Строка 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 | ||
[[Категория: Совместное определение связанных терминов]] | |||
