В вычислительной технике и теории графов динамическая структура связности — это структура данных, которая динамически поддерживает информацию о связанных компонентах графа.
Множество вершин V графа фиксировано, но множество ребер E может меняться. Три случая, в порядке сложности, следующие:
После каждого добавления/удаления ребра динамическая структура связности должна адаптироваться таким образом, чтобы она могла быстро давать ответы на запросы вида «существует ли путь между x и y ?» (эквивалентно: «принадлежат ли вершины x и y одному и тому же связному компоненту?»).
Если ребра можно только добавлять, то проблема динамической связности может быть решена с помощью структуры данных непересекающихся множеств . Каждое множество представляет собой связанный компонент; между x и y существует путь тогда и только тогда, когда они принадлежат одному и тому же множеству. Амортизированное время на операцию равно , где n — число вершин, а α — обратная функция Аккермана . [1] [2]
Случай, когда ребра можно только удалять, был решен Шимоном Эвеном и Йосси Шилоахом. [3]
Структура использует таблицу , которая определяет для каждой вершины имя компонента, к которому она принадлежит. Таким образом, запрос на связность занимает постоянное время. Задача состоит в обновлении таблицы при удалении ребра.
Когда ребро u - v удаляется в лесу , дерево, содержащее это ребро, разбивается на два дерева: одно из них содержит u , а другое содержит v . Таблица обновляется следующим образом.
Поскольку мы всегда переименовываем меньший подкомпонент, амортизированное время для операции удаления составляет .
Когда ребро удаляется в общем графе, мы не знаем, остается ли его компонент единым компонентом (соединенным другими ребрами) или разбивается на два компонента. Поэтому мы используем два процесса, которые выполняются параллельно (или чередующимся образом). Процесс A проверяет, нарушает ли удаление ребра компонент, и если это так, оба процесса останавливаются. Процесс B проверяет, не нарушает ли удаление ребра компонент, к которому оно принадлежит, и если это не так, снова оба процесса останавливаются.
Структура имеет следующие свойства. Вершина v на уровне i , i > 0, имеет только три типа ребер: обратные ребра , которые соединяют ее с уровнем i −1 (существует по крайней мере одно такое ребро, которое может быть искусственным), локальные ребра , которые соединяют ее с другими ребрами на уровне i (существует ноль или более таких ребер), или прямые ребра , которые соединяют ее с ребрами на уровне i +1 (существует ноль или более таких ребер). Таким образом, для каждой вершины v мы поддерживаем три набора ребер (обратные, локальные и прямые).
При удалении ребра u - v возможны два варианта: либо u и v находятся на одном уровне, либо они находятся на уровнях, номера которых отличаются на 1.
Пока Q не пуст:
Если удаление ребра не нарушает ни одного компонента, и мы находимся в случае 2.2, то в конечном итоге процедура остановится. В этом случае легко увидеть, что структура BFS поддерживается правильно. Если его удаление нарушает компонент, то процедура не остановится сама по себе. Однако процесс A, распознающий разрыв, остановится, и оба процесса остановятся. В этом случае все изменения, внесенные в структуру BFS, игнорируются, и мы возвращаемся к структуре BFS, которая была у нас непосредственно перед удалением, за исключением того, что удаленное ребро теперь заменено искусственным ребром. Очевидно, что в этом случае v теперь является корнем дерева, которое включает новый компонент и, возможно, дополнительные компоненты, через некоторые другие искусственные ребра. Кроме того, нет ребер, соединяющих потомков v с какими-либо вершинами, которые не являются потомками v , за исключением искусственного ребра . [4]
всякий раз, когда ребро обрабатывается в процедуре, одна из его конечных точек опускается на один уровень. Поскольку самый низкий уровень, которого вершина может достичь в запусках, завершаемых процессом B, равен , стоимость одного ребра ограничена . Следовательно, амортизированное время на операцию удаления равно .
Лес может быть представлен с помощью набора деревьев ссылок или деревьев Эйлера . Тогда проблема динамической связности может быть легко решена, так как для каждых двух узлов x,y, x соединен с y тогда и только тогда, когда . Амортизированное время обновления и время запроса составляют O(log( n )).
Общий граф может быть представлен его остовным лесом - лесом , который содержит дерево для каждого связного компонента графа. Мы называем этот остовной лес F. Сам F может быть представлен лесом деревьев эйлерова тура .
Операции Query и Insert реализуются с использованием соответствующих операций на деревьях ET, представляющих F. Сложной операцией является Delete, и в частности удаление ребра, которое содержится в одном из остовных деревьев F. Это разбивает остовное дерево на два дерева, но возможно, что есть еще одно ребро, которое их соединяет. Задача состоит в том, чтобы быстро найти такое заменяющее ребро, если оно существует. Для этого требуется более сложная структура данных. Несколько таких структур описаны ниже.
Каждому ребру в графе назначается уровень . Пусть L =lg n . Уровень каждого ребра, вставленного в граф, инициализируется значением L и может уменьшаться до 0 во время операций удаления.
Для каждого i между 0 и L определим Gi как подграф, состоящий из ребер, которые находятся на уровне i или ниже, а Fi — остовной лес Gi . Наш лес F из предыдущего теперь называется FL . Мы сохраним убывающую последовательность лесов FL ⊇ ... ⊇ F 0. [5] [6]
Операции Query и Insert используют только самый большой лес FL . Меньшие подграфы просматриваются только во время операции Delete, и в частности, удаления ребра, которое содержится в одном из остовных деревьев 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 :
Уровень каждого ребра будет уменьшен не более чем в lg n раз. Почему? Потому что с каждым уменьшением оно попадает в дерево, размер которого не более чем в два раза меньше размера его дерева на предыдущем уровне. Таким образом, на каждом уровне i количество узлов в каждом связанном компоненте не более 2 i . Следовательно, уровень ребра всегда не менее 0.
Каждое ребро, уровень которого понижен, требует времени для поиска (с использованием операций дерева ET). В общей сложности, каждое вставленное ребро требует времени, пока оно не будет удалено, поэтому амортизированное время удаления составляет . Оставшаяся часть удаления также требует времени, поскольку нам нужно удалить ребро из большинства уровней, а удаление из каждого уровня занимает (снова с использованием операций ET).
В целом амортизированное время на обновление составляет . Время на запрос можно улучшить до .
Однако худшее время на обновление может быть . Вопрос о том, можно ли улучшить худшее время, оставался открытым, пока он не был решен утвердительно структурой Cutset.
Для данного графа G(V,E) и подмножества T⊆V определим cutset(T) как множество ребер, соединяющих T с V\T. Структура cutset — это структура данных, которая, не сохраняя весь граф в памяти, может быстро найти ребро в cutset, если такое ребро существует. [7]
Начните с присвоения номера каждой вершине. Предположим, что есть n вершин; тогда каждая вершина может быть представлена числом с lg( n ) битами. Затем присвойте номер каждому ребру, которое является конкатенацией номеров его вершин - число с 2 lg( n ) битами.
Для каждой вершины v вычислите и сохраните xor( v ), который является xor чисел всех смежных с ней ребер.
Теперь для каждого подмножества T⊆V можно вычислить xor(T) = xor значений всех вершин в T. Рассмотрим ребро e = u − v , которое является внутренним ребром T (т.е. и u, и v находятся в T). Число e дважды включено в xor(T) - один раз для u и один раз для v . Поскольку xor каждого числа с самим собой равен 0, e обращается в нуль и не влияет на xor(T). Таким образом, xor(T) на самом деле является xor всех ребер в cutset(T). Есть несколько вариантов:
Теперь наша цель — разобраться с этим третьим вариантом.
Сначала создайте последовательность из lg( n ) уровней структур cutset, каждый из которых содержит около половины ребер с верхнего уровня (т. е. для каждого уровня выберите каждое ребро с верхнего уровня с вероятностью 1/2). Если на первом уровне xor(T) возвращает недопустимое значение, что означает, что cutset(T) имеет два или более ребер, то есть вероятность, что на следующем уровне, который содержит меньше ребер, xor(T) вернет допустимое значение, поскольку cutset(T) будет содержать одно ребро. Если xor(T) все еще возвращает недопустимое значение, перейдите на следующий уровень и т. д. Поскольку количество ребер уменьшается, возможны два случая:
Можно доказать, что вероятность успеха составляет не менее 1/9.
Далее создайте коллекцию из C lg( n ) независимых версий структуры уровня, где C — константа. В каждой версии выполните независимое случайное сокращение ребер от уровня к уровню. Попробуйте каждый запрос на каждой из версий, пока одна из них не увенчается успехом. Вероятность того, что все версии потерпят неудачу, не превышает:
Правильным выбором C мы можем сделать вероятность отказа произвольно близкой к 0.
Мы можем добавить структуру разрезов к динамической структуре связности.
Операции вставки и удаления в структуре набора разрезов выполняются абсолютно одинаково: вставленное/удалённое ребро подвергается операции XOR с обеими его конечными точками.
При удалении ребра из остовного леса, используемого для динамической структуры связности, для поиска заменяющего ребра используется структура сечения.
Для одной структуры cutset требуется только O ( n lg n ) памяти — только одно число с 2 lg n битами для каждой из n вершин. Нам не нужно хранить сами ребра. Для плотных графов это намного дешевле, чем хранить весь граф в памяти.
Нам нужно сохранить lg( n ) версий, каждая из которых содержит lg( n ) уровней. Следовательно, общее требование к памяти составляет .
Время запроса в худшем случае составляет O (polylog( n )). Это контрастирует со структурой Level, в которой время запроса составляет O (polylog( n )) амортизировано, но время в худшем случае составляет O ( n ).
Если порядок, в котором будут удалены ребра, известен заранее, то мы можем решить проблему динамической связности за время на запрос. Если мы можем поддерживать максимальный охватывающий лес, где ребра упорядочены по времени их удаления, мы знаем, что когда мы удаляем некоторое ребро, которое находится в лесу, нет возможного ребра, которое может его заменить. Если бы было какое-то ребро, которое соединяет те же два компонента, что и удаленное ребро, то это другое ребро было бы частью максимального охватывающего леса вместо ребра, которое мы удалили. Это делает операцию удаления тривиальной: нам просто нужно разделить дерево на две части, если удаляемое ребро является частью нашего леса, или игнорировать операцию в противном случае.
Добавление ребра немного сложнее. Если мы добавим ребро ребро e от u до v, то если u и v не соединены, то это ребро будет частью максимального остовного леса. Если они соединены, мы хотим добавить u->v к нашему лесу, если это может улучшить наш максимальный остовный лес. Для этого нам нужно быстро проверить, какое ребро имеет наименьшее время удаления на пути от u до v. Если время удаления этого ребра наступает после времени удаления e, то e не может улучшить наш максимальный остовный лес. В противном случае другое ребро должно быть удалено и заменено на e.
Для этого нам необходимо выполнить следующие операции: добавить ребро, разрезать ребро и запросить минимальное ребро на пути, что можно довольно легко сделать с помощью дерева разрезов ссылок за log(n) на операцию.
