693
правки
Изменения
→Обобщение задачи для произвольных графов
===connected(u,v)Проверка связности===
Граф и его остовный лес {{---}} одно и то же с точки зрения связности. Поэтому проверка связности в графе сводится к проверке связности в остовном лесе и решается за <tex>O(\log n)</tex>.<!--Добавление рёбер можно рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], такой запрос будет работать за <tex>O(\log n)</tex>. Операция проверки сводится к проверке связности в остовном лесе и работает также за <tex>O(\log n)</tex>.-->
===add(u,v)Добавление ребра===
Чтобы разобраться с тем, как изменится граф и остовный лес при добавлении и удалении ребра, введём функцию <tex>l(e):E{\rightarrow}[0;\log n]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Уровни ребра можно распределить любым способом, но для всех <tex> i </tex> должно выполняться следующее свойство: размер каждой компоненты связности <tex>G_i</tex> не превосходит <tex>\dfrac{n}{2^i}</tex>. Здесь графы <tex>G_i</tex> определяются так: <tex>G_i=\langle V, E\rangle: \{e \in E \mid l(e) \geqslant i\}</tex>.
<tex>F_0</tex> = <tex>F_0\bigcup</tex> e<!---insert(<tex>F_0</tex>, e)-->
===remove(u,v)Удаление ребра===
{{Утверждение
|statement=Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то связность между любой парой вершин сохранится.
'''Edge''' e = <tex>\langle </tex>u, v<tex>\rangle</tex>
i = e.level
'''while''' i <tex>\geqslant</tex>= 0
<tex>G_i</tex> = <tex>G_i\setminus</tex>e<!---delete(<tex>G_i</tex>, e)--->
<tex>F_i</tex> = <tex>F_i\setminus</tex>e<!---delete(<tex>F_i</tex>, e)--->
'''for''' e2 = <tex>\langle </tex>x, y<tex>\rangle</tex> : e2.level == i '''and''' x <tex>\in T_u</tex>
'''if''' y <tex>\in T_v</tex>
'''while''' i <tex>\geqslant</tex>= 0
<tex>F_i</tex> = <tex>F_i\bigcup</tex> e2<!---insert(<tex>F_i</tex>, e2)-->
i--
'''breakreturn'''
'''else'''
e2.level++
