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

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

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

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

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

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

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

Декрементная связность

Случай, в котором можно удалять только ребра, решили Шимон Эвен и Йосси Шилоах .

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

Ациклические графы (леса)

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

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

Поскольку мы всегда переименовываем меньший подкомпонент, амортизированное время операции удаления равно $O(\log(n))$.

Общие графики

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

Процесс А

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

Процесс Б

использует структуру в ширину (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

Если новый back( 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 ) и поместите в front( x ).
   • назад( ш ) := местный( ш )
4. Обновление ближайших соседей:
   • Для каждого ребра w - x в front( w ) удалите его из back( x ) и поместите в local( x ); если новый back( x ) пуст, поставьте x в очередь Q.
   • локальный( ш ) := вперед( ш )
   • вперед( w ) := пустой набор
5. Если новый back( w ) пуст, снова поставьте w в очередь на Q.

Если удаление ребра не нарушает ни один компонент и мы находимся в случае 2.2, то в конечном итоге процедура остановится. В этом случае легко увидеть, что структура BFS поддерживается правильно. Если его удаление приведет к поломке компонента, процедура не остановится сама по себе. Однако процесс A, распознав разрыв, остановится, и оба процесса остановятся. В этом случае все изменения, внесенные в структуру BFS, игнорируются, и мы возвращаемся к структуре BFS, которая была у нас непосредственно перед удалением, за исключением того, что удаленное ребро теперь заменяется искусственным ребром. Очевидно, что в этом случае v теперь является корнем дерева, которое включает новый компонент и, возможно, дополнительные компоненты через некоторые другие искусственные ребра. Также нет ребер, соединяющих потомков v с любыми вершинами, которые не являются потомками вершины v , за исключением искусственного ребра ⁠ $u-v$⁠ .

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

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

Ациклические графы (леса)

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

Общие графики

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

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

Структура уровня

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

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

Операции

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

Сначала мы уменьшаем уровень каждого ребра Tx на 1. Затем мы перебираем все ребра ε с уровнем i и хотя бы одним узлом в Tx :

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

Анализ

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

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

В целом амортизированное время на одно обновление составляет $O(\lg ^{2}n)$. Время на запрос можно сократить до $O(\lg n/\lg \lg n)$.

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

Структура Cutset

Учитывая граф G(V,E) и подмножество T⊆V, определите Cutset(T) как набор ребер, соединяющих T с V\T. Структура набора разрезов — это структура данных, которая, не сохраняя в памяти весь граф, может быстро найти ребро в наборе разрезов, если такое ребро существует.

Начните с присвоения номера каждой вершине. Предположим, есть 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 . Мы также можем прочитать конечные точки e из числа e, разделив его на самые левые биты lg( n ) и самые правые биты lg( n ).
• Третий вариант заключается в том, что xor(T) — это ненулевое число, которое не представляет собой реальное ребро. Это может произойти только в том случае, если в Cutset(T) есть два или более ребер, поскольку в этом случае xor(T) является xor нескольких чисел ребер. В этом случае мы сообщаем «ошибка», поскольку знаем, что в наборе разрезов есть ребра, но не можем идентифицировать ни одно ребро.

Наша цель сейчас — обработать этот третий вариант.

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

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

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

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

$(1-1/9)^{C\lg {n}}=2^{-0.17C\lg {n}}=n^{-0.17C}$

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

Операции

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

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

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

Анализ

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

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

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

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

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

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

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

См. также

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

Ссылки

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