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

Задача заключается в эффективной поддержке информации о связности в динамически меняющемся графе. Динамический алгоритм на графе поддерживает заданное свойство 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.