1632
правки
Изменения
м
Попробуем выполнить операцию удаления ребра.<!--- Для этого ---->
Попробуем найти подходящую вершину Будем искать ребро <tex>xxy</tex> в следующим образом:# Выбираем любое ребро уровня <tex>i</tex>, выходящее из вершины, принадлежащей <tex>T_u</tex> следующим образом:. # Если исходящее выбранное ребро ведёт в <tex>T_v</tex>, то выходим из цикла и добавляем ребро <tex>xy</tex> в остовные леса <tex>F_i</tex>, для которых <tex>i\leqslant l(xy)</tex> и выходим из цикла;# Если исходящее выбранное ребро ведёт в другую вершину поддерева <tex>T_u</tex>, увеличиваем его уровень на <tex>1</tex>;
Пункт Пусть до момента, когда мы нашли нужное ребро, мы сделали <tex>S</tex> неудачных сканирований. После каждого такого сканирования нам приходится добавлять новые рёбра в <tex>2G_{i+1}</tex> выполняется за , что стоит <tex>O(\log n)</tex> за счёт добавления новых рёбер в . Получаем сложность удаления одного ребра <tex>G_O(\log^2{in}+1}</tex> и вызывается до <tex>S\cdot\log n)</tex> раз.<!--- Возможно, мы удалим мост, но это уже другая история, да и она всяко лучше логарифмов в квадрате... --->
Пусть до момента, когда мы нашли нужное ребро, мы сделали Выразим сложность одной операции <tex>S\mathrm{remove}</tex> неудачных сканированийдругим способом. Получаем Для <tex>n</tex> вершин и <tex>m</tex> вызовов процедуры сложность удаления одного ребра равна <tex>O(\log^2{n}\cdot m+\log n\cdot\displaystyle \sum_{i=1}^m S_i)</tex>, что не превосходит <tex>O(\log^2{n}\cdot m+S\log n\cdot\log n\cdot m)</tex>, так как уровень ребра <tex>m</tex> раз рос максимум до <tex>\log n</tex>. Отсюда суммарная сложность всех запросов равна <tex>O(\log^2{n}\cdot m)<!--- Возможно/tex>, а для одного запроса мы удалим мост, но это уже другая история, да и она всяко лучше логарифмов в квадрате..решаем задачу за <tex>O(\log^2{n})</tex>. --->
Выразим сложность одной операции <tex>\mathrm{remove}</tex> другим способом. Для <tex>m</tex> вызовов процедуры сложность равна <tex>O(\log^2{n}\cdot m+\log n\cdot\displaystyle \sum_{i=1}^m S_i)</tex>, что не превосходит <tex>O(\log^2{n} \cdot m+\log n\cdot\log n\cdot m)</tex>, так как уровень ребра <tex>m</tex> раз рос максимум до <tex>\log n</tex>. Отсюда суммарная сложность всех запросов равна <tex>O(\log^2{n}\cdot m)</tex>, а для одного запроса мы решаем задачу за <tex>O(\log^2{n})</tex>.===Псевдокод====
<!-----====Псевдокод==== '''function''' <tex>\mathrm{remove }</tex>('''Node''' u, '''Node''' v): '''whileEdge''' i e = <tex>\langle </tex>u, v<tex>\rangle</tex>= 0 '''Edgefor''' i = e .level '''downto''' 0 <tex>G_i</tex> = <tex>G_i\langle setminus</tex>e<!---delete(<tex>G_i</tex>x, ye)---> <tex>F_i</tex> = <tex>F_i\ranglesetminus</tex>e<!---delete(<tex>F_i</tex>, e)---> '''Edge''' e2 '''for''' e e2 = <tex>\langle </tex>x, y<tex>\rangle</tex> : ee2.level == i'''and''' x <tex>\in T_u</tex>
rollbackEdits.php mass rollback
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Для решения таких задач в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес.
[[Файл:Graph.jpg|550px530px|thumb|left|Граф]] [[Файл:Spanforest.jpg|550px530px|thumb|right|Остовный лес в графе]]
===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>.
====Псевдокод====
'''function''' <tex>\mathrm{add }</tex>('''Node''' u, '''Node''' v):
'''Edge''' e = <tex>\langle </tex>u, v<tex>\rangle</tex>
e.level = 0
<tex>G_0</tex> = <tex>G_0</tex> <tex>\cup</tex> e<!---insert(<tex>G_0</tex>, e)--> '''if not''' <tex>\mathrm{connected(u, v)}</tex> <tex>F_0</tex> = <tex>F_0</tex> <tex>\cup</tex> e<!---insert(<tex>F_0</tex>, e)-->
===remove(u,v)Удаление ребра===
{{Утверждение
|statement=Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то связность между любой парой вершин сохранится.
Чтобы найти <tex>xy</tex>, выберем из поддеревьев <tex>T_u</tex> и <tex>T_v</tex> наименьшее. Не умаляя общности, будем считать, что <tex>|T_u|\leqslant|T_v|</tex>. <!--ежу понятно--> Так как всегда из двух слагаемых можно выбрать одно такое, что оно не превосходит половины их суммы, имеем важное свойство: <tex>|T_u|\leqslant\dfrac{|T_u|+|T_v|}{2}=\dfrac{|T|}{2}</tex>. Также нам известно, что <tex>T \subseteq F_i</tex>, а значит, <tex>|T|\leqslant\dfrac{n}{2^i}</tex>. Отсюда <tex>|T_u|\leqslant\dfrac{n}{2^{i+1}}</tex>. Это неравенство позволит нам увеличивать уровни рёбер при необходимости.
# Если есть непроверенные рёбра на интересующем нас уровне <tex>i</tex>, переходим к пункту <tex>1</tex>;
# Если таких рёбер уровня <tex>i</tex> не осталось и <tex>i>0</tex>, рассматриваем уровень на единицу меньший и переходим к пункту <tex>1</tex>;
'''Замечание.''' Увеличив уровень ребра на единицу, нужно не забыть обновить <tex>G_{i+1}</tex> и <tex>F_{i+1}</tex>.
====Оценка времени работы====
Пункт <tex>12</tex> работает за <tex>O(\log^2 n)</tex>, так как после выхода из цикла мы добавляем ребро за <tex>O(\log n)</tex> на каждом уровне, а количество уровней не больше <tex>\log n</tex>.<!--5 сек, тут кажись я права всё-таки, нужен Лёха-->
'''if''' y <tex>\in T_v</tex>
'''for''' j = i '''downto''' 0
<tex>F_j</tex> = <tex>F_j</tex> <tex>\cup</tex> e2<!---insert(<tex>F_jF_i</tex>, ee2)--> '''breakreturn''' '''else''' e e2.level++ <tex>G_{i+1}</tex> = <tex>G_{i+1}</tex> <tex>\cup</tex> e2<!---insert(<tex>F_i</tex>, e2)-->
== См. также ==
