Задача о динамической связности

Задача:

Есть неориентированный граф из [math]n[/math] вершин, изначально не содержащий рёбер. Требуется обработать [math]m[/math] запросов трёх типов: [math]\mathrm{add(u,v)}[/math] — добавить ребро между вершинами [math]u[/math] и [math]v[/math]; [math]\mathrm{remove(u,v)}[/math] — удалить ребро между вершинами [math]u[/math] и [math]v[/math]; [math]\mathrm{connected(u,v)}[/math] — проверить, лежат ли вершины [math]u[/math] и [math]v[/math] в одной компоненте связности.

Динамическая связность в лесах

Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в деревьях эйлерова обхода. Время работы каждого запроса для упрощённой задачи — [math]O(\log n)[/math].

Обобщение задачи для произвольных графов

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

Граф

Остовный лес в графе

connected(u,v)

Граф и его остовный лес — одно и то же с точки зрения связности. Поэтому проверка связности в графе сводится к проверке связности в остовном лесе и решается за [math]O(\log n)[/math].

add(u,v)

Чтобы разобраться с тем, как изменится граф и остовный лес при добавлении и удалении ребра, введём функцию [math]l(e):E{\rightarrow}[0;\log n][/math] и назовём её уровнем ребра [math]e[/math]. Уровни ребра можно распределить любым способом, но для всех [math] i [/math] должно выполняться следующее свойство: размер каждой компоненты связности [math]G_i[/math] не превосходит [math]\dfrac{n}{2^i}[/math]. Здесь графы [math]G_i[/math] определяются так: [math]G_i=\langle V, E\rangle: \{e \in E \mid l(e) \geqslant i\}[/math].

Очевидно, что [math]G_{\log n} \subseteq G_{\log n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0 = G[/math]. Выделим в графах остовные леса таким образом, что [math]F_{\log n} \subseteq F_{\log n-1} \subseteq \ldots \subseteq F_1 \subseteq F_0[/math], где [math]F_i[/math] — остовный лес графа [math]G_i[/math].

Удобнее всего новому ребру давать уровень [math]0[/math]. В этом случае изменится только [math]G_0[/math], так как в остальные подграфы [math]G_i[/math] рёбра нулевого уровня не входят. После вставки нового ребра нам нужно проверить, были ли вершины [math]u[/math] и [math]v[/math] в одной компоненте связности до того, как мы вставили ребро. Если они лежали в разных компонентах, то необходимо новое ребро добавить и в остовный лес [math]F_0[/math].

Псевдокод

 function add (Node u, Node v):
   Edge e = <u, v>
   e.level = 0
   insert([math]G_0[/math], e)
   if not connected(u, v)
     insert([math]F_0[/math], e)

remove(u,v)

Утверждение:

Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то связность между любой парой вершин сохранится.

[math]\triangleright[/math]

Докажем от противного. Допустим, что это не так. Понятно, что при разрезании ребра нового пути между вершинами не появится. Предположим, что нарушилась связность для каких-то двух вершин. Значит, мы убрали мост. А любой мост принадлежит всем остовным деревьям его компоненты. Противоречие.

[math]\triangleleft[/math]

Таким образом, если мы удалили ребро не из остовного леса, то нам не придётся перестраивать лес и пересчитывать значение [math]\mathrm{connected(u,v)}[/math]. Рассмотрим случаи, когда мы берём ребро из леса. Тогда необходимо выяснить, не является ли данное ребро мостом в графе, и выполнить соответствующие действия.

Проверим, является ли ребро мостом. У ребра [math]uv[/math] известен уровень, пусть он равен [math]i[/math]. Попробуем найти другое ребро ([math]xy[/math]), соединяющее поддеревья [math]T_u[/math] и [math]T_v[/math], на которые распалось остовное дерево исследуемой компоненты [math]T[/math].

Утверждение:

[math]l(xy)\leqslant i[/math]

[math]\triangleright[/math]

От противного. Пусть [math]l(xy)=j[/math] и [math]j\geqslant i[/math]. Тогда вершины [math]x[/math] и [math]y[/math] каким-то образом связаны в [math]F_j[/math] (либо непосредственно ребром [math]xy[/math], либо каким-то другим путём). Но [math]F_j \subseteq F_i[/math]. Значит, в [math]F_i[/math] между [math]x[/math] и [math]y[/math] сохранился путь из рёбер уровня не меньше [math]j[/math] и появился другой путь через [math]uv[/math]. Приходим к противоречию, так как в [math]F_i[/math] все компоненты должны быть деревьями.

[math]\triangleleft[/math]

Чтобы найти [math]xy[/math], выберем из поддеревьев [math]T_u[/math] и [math]T_v[/math] наименьшее. Не умаляя общности, будем считать, что [math]|T(u)|\leqslant|T_v|[/math]. Так как хотя бы одно из двух слагаемых всегда не превосходит половины их суммы, имеем важное свойство: [math]|T(u)|\leqslant\dfrac{|T_u|+|T_v|}{2}=\dfrac{|T|}{2}[/math]. Также нам известно, что [math]T \subseteq F_i[/math], а значит, [math]|T|\leqslant\dfrac{n}{2^i}[/math]. Отсюда [math]|T(u)|\leqslant\dfrac{n}{2^{i+1}}[/math]. Это неравенство позволит нам увеличивать уровни рёбер при необходимости.

Попробуем найти подходящую вершину [math]x[/math] в [math]T_u[/math] следующим образом:

1. Если исходящее ребро ведёт в [math]T_v[/math], то выходим из цикла и добавляем ребро [math]xy[/math] в остовные леса [math]F_i[/math], для которых [math]i\leqslant l(xy)[/math] и выходим из цикла;
2. Если исходящее ребро ведёт в другую вершину поддерева [math]T_u[/math], увеличиваем его уровень на [math]1[/math];
3. Если есть непроверенные рёбра, переходим к пункту [math]1[/math];
4. Если таких рёбер уровня [math]i[/math] не осталось и [math]i\gt 0[/math], уменьшаем уровень на единицу и переходим к пункту [math]1[/math];
5. Если все рёбра просканированы и [math]i=0[/math], то [math]uv[/math] является мостом.

Замечание. Увеличив уровень ребра на единицу, нужно не забыть обновить [math]G_{i+1}[/math] и [math]F_{i+1}[/math].

Оценка времени работы

Пункт [math]1[/math] работает за [math]O(\log^2 n)[/math], так как мы добавляем ребро за [math]O(\log n)[/math] на каждом уровне, а количество уровней не больше [math]\log n[/math].

Пункт [math]2[/math] выполняется за [math]O(\log n)[/math] за счёт добавления новых рёбер в [math]G_{i+1}[/math] и вызывается до [math]\log n[/math] раз.

Пусть до момента, когда мы нашли нужное ребро, мы сделали [math]S[/math] неудачных сканирований. Получаем сложность удаления одного ребра [math]O(\log^2{n}+S\cdot\log n)[/math].

Выразим сложность одной операции [math]\mathrm{remove}[/math] другим способом. Для [math]m[/math] вызовов процедуры сложность равна [math]O(\log^2{n}\cdot m+\mathrm{\log}n\cdot\sum{S})[/math], что не превосходит [math]O(\log^2{n} \cdot m+\log n\cdot\log n\cdot m)[/math], так как уровень ребра [math]m[/math] раз рос максимум до [math]\log n[/math]. Отсюда суммарная сложность всех запросов равна [math]O(\log^2{n}\cdot m)[/math], а для одного запроса мы решаем задачу за [math]O(\log^2{n})[/math].

Псевдокод

 function remove (Node u, Node v):
   while i >= 0
     Edge e = <x, y>
     for e : e.level == i
       if y [math]\in T_v[/math] 
         for j = i downto 0
           insert([math]F_j[/math], e)
         break
       else e.level++
     i--

См. также

• Деревья эйлерова обхода
• Задача о динамической связности оффлайн

Источники информации

• Dynamic connectivity — Википедия
• Лекции — Академия Яндекса