Динамическое подключение

В вычислительной и теории графов , A динамического подключения структура представляет собой структуру данных , которая динамически поддерживает информацию о компонентах связности графа.

Множество V вершин графа фиксировано, но множество ребер E может измениться. Вот три случая в порядке сложности:

• Ребра только добавляются к графу (это можно назвать инкрементной связностью );
• Ребра удаляются только из графа (это можно назвать декрементной связностью );
• Края можно добавлять или удалять (это можно назвать полностью динамической связью ).

После каждого добавления / удаления ребра динамическая структура связности должна адаптироваться так, чтобы она могла давать быстрые ответы на запросы вида «есть ли путь между x и y ?» (эквивалентно: «принадлежат ли вершины x и y одной компоненте связности?»).

Дополнительные возможности подключения [ править ]

Если ребра могут быть только добавлены, то проблема динамической связи может быть решена с помощью структуры данных с несвязным набором . Каждый набор представляет собой связанный компонент; существует путь между x и y тогда и только тогда, когда они принадлежат одному и тому же набору. Амортизированное время на операцию равно , где n - количество вершин, а α - обратная функция Аккермана . ^{[1] [2]}${\ Displaystyle \ Theta (\ альфа (п))}$

Ухудшение связи [ править ]

Случай, когда края могут быть только удалены, был раскрыт Шимоном Эвеном и Йосси Шилоахом . ^[3]

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

Ациклические графы (леса) [ править ]

Когда в лесу удаляется ребро u - v , дерево, содержащее это ребро, разбивается на два дерева: одно из них содержит u, а другое - v . Таблица обновляется следующим образом.

• Просканируйте дерево, начиная с u (используя любой алгоритм сканирования дерева, например DFS ).
• Сканировать дерево, начиная с v .
• Выполните две вышеуказанные процедуры параллельно, т. Е. Либо используя два параллельных процесса, либо чередуя их шаги (выполните шаг первого сканирования, затем шаг второго сканирования, затем шаг первого сканирования и т. Д.).
• Предположим, что первое завершающееся сканирование - это сканирование из u (чтобы мы знали, что дерево, содержащее u, является меньшим). Назначьте новое имя компонента каждому узлу в поддереве u .

Поскольку мы всегда переименовываем меньший подкомпонент, амортизированное время для операции удаления составляет .${\ Displaystyle О (\ журнал (п))}$

Общие графики [ править ]

Когда ребро удаляется в общем графе, мы не знаем, остается ли его компонент единственным компонентом (соединенным другими ребрами) или разбитым на два компонента. Таким образом, мы используем два процесса, которые работают параллельно (или чередуются). Процесс A проверяет, нарушает ли удаление ребра компонент, и если это так, оба процесса останавливаются. Процесс B проверяет, не нарушает ли удаление ребер компонент, которому оно принадлежит, и, если нет, снова оба процесса останавливаются.

Процесс А

аналогичен случаю ациклического графа: есть два подпроцесса, которые сканируют с обоих концов удаленного края. Если один из подпроцессов завершается до достижения другого конца, это означает, что компонент разбит на два подкомпонента, а имя меньшего подкомпонента обновляется, как и раньше. Таким образом, амортизированное время для операции удаления снова .${\ Displaystyle О (\ журнал (п))}$

Процесс B

использует структуру в ширину (BFS), которая инициализируется следующим образом. Выбирается вершина r, с которой начинается BFS. Единственная вершина на уровне 0 - r . Все вершины расстояния i от корня находятся на уровне i . Если G не подключен, новое сканирование начинается с некоторой непросканированной вершины v , v помещается на уровень 1, и искусственное ребро соединяет v с корнем r ; все вершины на расстоянии i от v теперь находятся на уровне i+1 и т. Д. Искусственные ребра вводятся для того, чтобы все связанные компоненты оставались в одной структуре BFS, и используются только для этой цели. Понятно, что искусственные края используются только в процессе Б.

Структура обладает следующими свойствами. Вершина v на уровне i , i > 0, имеет только три типа ребер: обратные ребра, которые соединяют ее с уровнем i −1 (есть по крайней мере одно такое ребро, которое может быть искусственным), локальные ребра, которые соединяют его с другими. ребер на уровне i (таких ребер ноль или более) или передних ребер, которые соединяют его с ребрами на уровне i + 1 (таких ребер ноль или более). Итак, для каждой вершины v мы поддерживаем три набора ребер (назад, локально и вперед).

Когда ребро u - v удаляется, есть два варианта: либо u и v находятся на одном уровне, либо они находятся на уровнях, число которых отличается на 1.

Случай 1

и u, и v находятся на одном уровне. В этом случае удаление кромки не может изменить компоненты. Ребро просто удаляется из наборов локальных ребер u и v , и процесс B останавливается (и, следовательно, процесс A также останавливается). Наша структура BFS все еще действует.

Случай 2

u и v находятся на разных уровнях. Без ограничения общности предположим, что u находится на уровне i −1, а v находится на уровне i ; следовательно, край должен быть удален спереди ( u ) и сзади ( v ).

Случай 2.1

Если новая обратная сторона ( v ) не пуста, значит, компоненты не изменились: есть другие ребра, которые соединяют v назад. Процесс B останавливается (и процесс A также останавливается).

Случай 2.2

Если новый backward ( v ) пуст, то v больше не связан с уровнем i −1, и поэтому его расстояние от корня больше не i ; он должен быть не менее i +1. Кроме того, могут быть другие вершины, связанные с v , расстояние которых от корня увеличивается в результате удаления. Для вычисления обновленных расстояний мы используем очередь Q, которая изначально содержит только вершину v .

Пока Q не пуст:

1. w : = исключить из очереди (Q)
2. Удалите w с его уровня (скажем, j ) и поместите его на следующий уровень ( j +1).
3. Обновите местных соседей:
   • Для каждого ребра w - x в local ( w ) удалите его из local ( x ) и поместите в forward ( x ).
   • назад ( w ): = local ( w )
4. Обновить форвардных соседей:
   • Для каждого ребра w - x впереди ( w ) удалите его сзади ( x ) и поместите в local ( x ); если новый backward ( x ) пуст, поставить x в очередь на Q.
   • местный ( ш ): = вперед ( ш )
   • вперед ( w ): = пустой набор
5. Если новый backward ( w ) пуст, снова поставить w в очередь на Q.

Если удаление ребра не повреждает какой-либо компонент, а мы в случае 2.2, то в конечном итоге процедура остановится. В этом случае легко увидеть, что структура BFS поддерживается правильно. Если его удаление сломает компонент, процедура не остановится сама по себе. Однако процесс A, распознав разрыв, остановится, и оба процесса остановятся. В этом случае все изменения, внесенные в структуру BFS, игнорируются, и мы возвращаемся к структуре BFS, которая была у нас непосредственно перед удалением, за исключением того, что удаленное ребро теперь заменяется искусственным ребром. Ясно, что в этом случае v теперь является корнем дерева, которое включает новый компонент и, возможно, дополнительные компоненты через некоторые другие искусственные ребра. Также нет ребер, соединяющих потомков vс любыми вершинами, не являющимися потомками v , кроме искусственного ребра . ^[4]${\ displaystyle uv}$

всякий раз, когда в процедуре обрабатывается ребро, одна из его конечных точек опускается на один уровень. Поскольку самый низкий уровень, которого может достичь вершина в прогонах, которые завершаются процессом B, является стоимость ребра ограничена . Следовательно, амортизированное время на операцию удаления составляет .${\ displaystyle | V | -1}$${\ displaystyle 2 | V |}$${\ Displaystyle О (п)}$

Полностью динамическое соединение [ править ]

Ациклические графы (леса) [ править ]

Лес может быть представлен с помощью набора деревьев Link-cut или деревьев Эйлера . Тогда проблема динамической связности может быть легко решена, поскольку для каждых двух узлов x, y, x подключен к y тогда и только тогда, когда FindRoot (x) = FindRoot (y). Амортизированное время обновления и время запроса равны O (log ( n )).

Общие графики [ править ]

Общий граф может быть представлен его остовным лесом - лесом, который содержит дерево для каждой связной компоненты графа. Мы называем это остовного леса F . Сам F может быть представлен лесом деревьев тура Эйлера .

Операции запроса и вставки осуществляются с использованием соответствующих операций на деревьях ET , представляющих F . Сложные операции удалить, и , в частности, удаление край , который содержится в одном из остовных деревьев F . Это разбивает остовное дерево на два дерева, но возможно, что есть еще одно ребро, которое их соединяет. Задача состоит в том, чтобы быстро найти такое заменяющее ребро, если оно существует. Это требует более сложной структуры данных. Ниже описаны несколько таких структур.

Структура уровней [ править ]

Каждому ребру в графе присвоен уровень . Пусть L = lg n . Уровень каждого ребра, вставленного в граф, инициализируется значением L и может уменьшаться до 0 во время операций удаления.

Для каждого i от 0 до L определите Gi как подграф, состоящий из ребер, находящихся на уровне i или ниже, а Fi как остовный лес Gi . Наш прежний лес F теперь называется FL . Сохраним убывающую последовательность лесов FL ⊇ ... ⊇ F 0. ^{[5] [6]}

Операции [ править ]

Операции Query и Insert используют только самый большой лесной FL . С меньшими подграфами обращаются только во время операции удаления и, в частности, при удалении ребра, которое содержится в одном из остовных деревьев FL .

Когда такое ребро e = x - y удаляется, оно сначала удаляется из FL и из всех меньших остовных лесов, которым оно принадлежит, то есть из каждого Fi с i ≥ level ( e ). Затем ищем замену ребра.

Начните с наименьшего остовного леса, содержащего e , а именно Fi с i = level ( e ). Ребро e принадлежит некоторому дереву T ⊆ Fi . После удаления e дерево T разбивается на два меньших дерева: Tx, которое содержит узел x, и Ty, которое содержит узел y . Ребро Gi является ребром замены, если и только если оно соединяет узел в Tx с узлом в Ty . Предположим, что wlog, что Txявляется меньшим деревом (т.е. содержит не более половины узлов T ; мы можем определить размер каждого поддерева по аннотации, добавленной к деревьям Эйлера).

Мы перебираем все ребра ε уровня i и хотя бы одну вершину в Tx :

• Если другой узел ε находится в Ty , то заменяющее ребро найдено! Добавьте это ребро к Fi и ко всем содержащим леса до FL , и закончите. Остовные леса закреплены.
• Если другой узел ε находится в Tx , то это не ребро замены, и чтобы «наказать» его за потерю времени, мы уменьшаем его уровень на 1.

Анализ [ править ]

Уровень каждого ребра будет уменьшен не более lg n раз. Почему? Потому что с каждым уменьшением он попадает в дерево, размер которого не превышает половины размера его дерева на предыдущем уровне. Таким образом, на каждом уровне i количество узлов в каждом связном компоненте не превышает 2 ⁱ . Следовательно, уровень ребра всегда не меньше 0.

Для поиска каждого ребра, уровень которого уменьшается, требуется время (с помощью операций с деревом ET). В целом, для каждого вставленного ребра требуется время, пока оно не будет удалено, поэтому амортизированное время для удаления составляет . Оставшаяся часть удаления также требует времени, так как мы должны удалить край на большинстве уровней, а удаление с каждого уровня занимает (опять же с использованием операций ET). ${\ Displaystyle О (\ lg п)}$${\ Displaystyle О (\ lg ^ {2} п)}$${\ Displaystyle О (\ lg ^ {2} п)}$${\ Displaystyle О (\ lg ^ {2} п)}$${\ Displaystyle О (\ lg п)}$${\ Displaystyle О (\ lg п)}$

В целом амортизированное время на обновление составляет . Время выполнения запроса можно уменьшить до . ${\ Displaystyle О (\ lg ^ {2} п)}$${\ Displaystyle О (\ LG п / \ LG \ LG п)}$

Однако в худшем случае время на обновление может быть . Вопрос о том, можно ли улучшить время наихудшего случая, был открытым, пока он не был решен утвердительно структурой Катсета.${\ Displaystyle О (п)}$

Структура Cutset [ править ]

Для графа G (V, E) и подмножества T⊆V определим cutset (T) как набор ребер, соединяющих T с V \ T. Структура сечения - это структура данных, которая без сохранения всего графа в памяти может быстро найти ребро в срезе, если такое ребро существует. ^[7]

Начните с присвоения номера каждой вершине. Предположим, что есть n вершин; тогда каждую вершину можно представить числом с lg ( n ) битами. Затем присвойте каждому ребру номер, который представляет собой конкатенацию номеров его вершин - число с 2 битами lg ( n ).

Для каждой вершины v вычислите и сохраните xor ( v ), который является xor номеров всех смежных с ней ребер.

Теперь для каждого подмножества T⊆V можно вычислить xor (T) = xor значений всех вершин в T. Рассмотрим ребро e = u - v, которое является внутренним ребром T (т.е. как u, так и v находятся в Т). Число e входит в xor (T) дважды - один раз для u и один раз для v . Поскольку xor каждого числа с самим собой равно 0, e обращается в нуль и не влияет на xor (T). Таким образом, xor (T) фактически является xor всех ребер в cutset (T). Есть несколько вариантов:

• Если xor (T) = 0, то мы можем с уверенностью ответить, что cutset (T) пуст.
• Если xor (T) - номер действительного ребра e , то, вероятно, e - единственное ребро в cutset (T), и мы можем вернуть e . Мы можем также прочитать конечные точки е из числа е , разделив ее на LG ( п ) крайние левые биты и LG ( п ) крайние правые биты.
• Третий вариант состоит в том, что xor (T) - ненулевое число, которое не представляет собой действительное ребро. Это может произойти только при наличии двух или более ребер в cutset (T), поскольку в этом случае xor (T) является xor нескольких чисел ребер. В этом случае мы сообщаем об ошибке, поскольку знаем, что в наборе сечений есть ребра, но не можем идентифицировать ни одного ребра. ^[8]

Наша цель сейчас - справиться с этим третьим вариантом.

Сначала создайте последовательность lg ( n ) уровней структур сечений, каждый из которых содержит примерно половину ребер с верхнего уровня (т. Е. Для каждого уровня выбирайте каждое ребро с верхнего уровня с вероятностью 1/2). Если на первом уровне xor (T) возвращает недопустимое значение, что означает, что cutset (T) имеет два или более ребра, то есть вероятность, что на следующем уровне, который содержит меньше ребер, xor (T) вернет допустимое значение. значение, так как cutset (T) будет содержать единственное ребро. Если xor (T) по-прежнему возвращает недопустимое значение, перейдите на следующий уровень и т. Д. Поскольку количество ребер уменьшается, возможны два случая:

• Хороший случай состоит в том, что мы в конечном итоге находим уровень, на котором cutset (T) содержит единственное ребро; затем возвращаем этот край и заканчиваем.
• Плохой случай состоит в том, что мы в конечном итоге находим уровень, на котором cutset (T) не содержит ребер; затем мы сообщаем о «неудаче», поскольку знаем, что в наборе сечений есть ребра, но не можем идентифицировать ни одно ребро.

Можно доказать, что вероятность успеха не менее 1/9.

Затем создайте коллекцию C  lg ( n ) независимых версий структуры уровней, где C - константа. В каждой версии выполняется независимое случайное уменьшение ребер от уровня к уровню. Попробуйте выполнить каждый запрос для каждой из версий, пока одна из них не будет успешной. Вероятность того, что все версии выйдут из строя, не превышает:

${\ displaystyle (1-1 / 9) ^ {C \ lg {n}} = 2 ^ {- 0,17C \ lg {n}} = n ^ {- 0,17C}}$

Правильно подобрав C, мы можем сделать вероятность отказа сколь угодно близкой к 0.

Операции [ править ]

Мы можем добавить структуру сечения к динамической структуре связности.

Операции Insert и Delete в структуре набора сечений выполняются точно так же: вставленное / удаленное ребро подвергается операции XOR в обеих конечных точках.

Когда ребро удаляется из связующего леса, используемого для структуры динамической связи, структура набора сечений используется для поиска заменяющего ребра.

Анализ [ править ]

Одна структура сечения требует только O ( n lg n ) памяти - только одно число с 2 lg n битами для каждой из n вершин. Нам не обязательно сохранять сами края. Для плотных графов это намного дешевле, чем хранить весь граф в памяти.

Мы должны сохранить версии lg ( n ), каждая из которых содержит уровни lg ( n ). Следовательно, общая потребность в памяти составляет .${\ Displaystyle О (п \ lg ^ {3} п)}$

В худшем случае время запроса составляет O (polylog ( n )). Это контрастирует со структурой уровня , в которой время запроса амортизировано O (polylog ( n )), но время наихудшего случая равно O ( n ).

Автономное динамическое подключение [ править ]

Если порядок, в котором будут удаляться ребра, известен заранее, мы можем решить проблему динамического подключения в журнале (n) для каждого запроса. Если мы сможем поддерживать Максимальный покрывающий лес, где ребра упорядочены по времени их удаления, мы знаем, что когда мы удаляем какое-то ребро, находящееся в лесу, не существует возможного ребра, которое могло бы его заменить. Если бы было какое-то ребро, которое соединяет те же два компонента, что и удаленное ребро, тогда это другое ребро было бы частью максимального покрывающего леса вместо того ребра, которое мы удалили. Это делает операцию удаления тривиальной: нам просто нужно разделить дерево на две части, если удаляемое ребро является частью нашего леса, или игнорировать операцию в противном случае.

Добавить ребро немного сложнее. Если мы добавим ребро e от u к v, то если u и v не соединены, то это ребро будет частью Максимального связующего леса. Если они подключены, мы хотим добавить u-> v в наш лес, если это может улучшить наш Максимальный покрывающий лес. Для этого нам нужно быстро проверить, какое ребро имеет наименьшее время удаления на пути от u до v. Если время удаления этого ребра наступает после времени удаления e, то e не может улучшить наш минимальный покрывающий лес. В противном случае другой край следует удалить и заменить на e.

Это требует от нас выполнения следующих операций: добавить кромку, вырезать кромку и запросить минимальную кромку на пути, что довольно легко сделать с помощью дерева отсечения ссылок в log (n) для каждой операции.

См. Также [ править ]

• Динамическая задача (алгоритмы)
• Уточнение раздела

Ссылки [ править ]

• См. Также: Thorup, M. (2000). Почти оптимальная возможность подключения полностью динамического графа . Материалы тридцать второго ежегодного симпозиума ACM по теории вычислений - STOC '00. п. 343. DOI : 10,1145 / 335305,335345 . ISBN 1581131844.