Изменения

В этой статье будет приведено решение задачи online== Динамическая связность в лесах ==Если задача такова, что в графе нет и не может быть циклов, то есть отвечать на getона сводится к задаче о связности в [[Деревья Эйлерова обхода|деревьях эйлерова обхода]]. Время работы каждого запроса для упрощённой задачи {{-запрос --}} <tex>O(проверять наличие пути между вершинами\log n) мы будем сразу</tex>, где <tex>n</tex> {{---}} количество вершин в графе.

Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Добавление рёбер можно рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], такой запрос будет работать за <tex>O(\mathrm{\log}n)</tex>. Операция проверки сводится к проверке связности в остовном лесе и работает также за <tex>O(\mathrm{\log}n)</tex>. Попробуем выполнить операцию удаления ребра. Для этого решения таких задач в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес. Граф и его остовный лес {{---}} одно и то же с точки зрения связности. [[Файл:Graph.jpg|550px|thumb|left|Произвольный граф]] [[Файл:Spanforest.jpg|550px|thumb|right|Остовный лес в графе]]   

Осталось проверить, является ли ребро мостом. Будем искать ребро <tex>xy</tex> на уровне <tex>l(uv)</tex>, затем <tex>l(uv)===Проверка связности===Граф и его остовный лес {{--1</tex>, <tex>l(uv)-2</tex><tex>{{...}}</tex>одно и то же с точки зрения связности. Рассматривать будем меньшую из частей (будем считать, что Поэтому проверка связности в графе сводится к проверке связности в остовном лесе и решается за <tex>|TO(u)|\leqslant|T(vlog n)|</tex>, в противном случае просто поменяем исследуемые вершины местами). Если мы находим такое ребро, что оно ведёт в другую часть, то останавливаемся и говорим, что <tex>uv</tex> не мост. Иначе увеличиваем уровень ребра!--Добавление рёбер можно рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], чтобы заново к нему не обращаться или уменьшаем уровень и повторяем процедуру. Суммарная сложность сканирования рёбер такой запрос будет работать за <tex>O(|T(u)|\mathrm{\log}n)</tex>, так как . Операция проверки сводится к проверке связности в худшем случае мы проверяем каждую вершину из остовном лесе и работает также за <tex>TO(u)</tex>, а уровень ребра не превосходит <tex>\mathrm{\log}n)</tex>.-->

Общее время удаления одного ===Добавление ребра===Чтобы разобраться с тем, как изменится граф и остовный лес при добавлении и удалении ребра не превосходит , введём функцию <tex>Ol(\mathrme):E{\log}^2{nrightarrow}+S*\mathrm{[0;\log}n)]</tex>, где и назовём её ''уровнем ребра'' <tex>Se</tex> {{---}} число неудачных сканирований. Уровни ребра можно распределить любым способом, а но для всех <tex>mi </tex> запросов получаем должно выполняться следующее свойство: размер каждой компоненты связности <tex>G_i</tex> не превосходит <tex>O(\mathrmdfrac{\log}^2{n}*m+\mathrm{\log}n*\sum{S}) \leqslant O(\mathrm{\log}^2{n}*m+\mathrm{\log}n*\mathrm{\log}n*m) = O(2*\mathrm{\log}^2{ni}*m)</tex>, поэтому для одного запроса будем иметь время . Здесь графы <tex>G_i</tex> определяются так: <tex>OG_i=\langle V, E\rangle: \{e \in E \mid l(e) \mathrm{geqslant i\log}^2{n})</tex>.

Удобнее всего новому ребру давать уровень <!-- я лошара) --tex>0<!--== Алгоритм ===== Время работы === /tex>. В этом случае изменится только <tex>G_0</ i think i'll tell it== Частные случаи == tex>, так как в остальные подграфы <tex>G_i</tex> рёбра нулевого уровня не входят. После вставки нового ребра нам нужно проверить, были ли вершины <tex>u</ hahaha there is only one specific kind))0)=== Деревья === tex> и <tex>v<//yes === Планарные графы === //da xz... chtobi o nih govorit' ischo... --tex><!--== Алгоритм ===== Решение упрощённой задачи ======= Задача без удалений рёбер ====Если нет удалений рёберв одной компоненте связности до того, задачу можно решить при помощи [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]]как мы вставили ребро. Каждая компонента связности {{---}} одно множество Если они лежали в СНМразных компонентах, то необходимо новое ребро добавить и при добавлении рёбер они объединяютсяв остовный лес <tex>F_0</tex>.

Время работы такого решения====Псевдокод==== '''function''' <tex>\mathrm{add}</tex>('''Node''' u, '''Node''' v): '''Edge''' e = <tex>\langle </tex>u, v<tex>O(m \cdot rangle</tex> e.level = 0 <tex>G_0</tex> = <tex>G_0</tex> <tex>\alpha cup</tex> e<!---insert(n<tex>G_0</tex>, e)--> '''if not''' <tex>\mathrm{connected(u,v)}</tex> <tex>F_0</tex> = <tex>F_0</tex>, где <tex>\alphacup</tex> {{e<!---}} [[СНМ insert(реализация с помощью леса корневых деревьев<tex>F_0</tex>, e)#Функция Аккермана|обратная функция Аккермана]].-->

=== Построение дерева отрезков Удаление ребра==={{Утверждение|statement=Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, то связность между любой парой вершин сохранится.Рассмотрим массив запросов|proof=Докажем от противного. Каждое ребро в графе существует на некотором отрезке запросов: начиная с запроса добавления и заканчивая запросом удаления (либо концом запросовДопустим, если ребро что это не было удалено)так. Для каждого Понятно, что при разрезании ребра можно найти этот отрезокнового пути между вершинами не появится.Предположим, пройдя по массиву запросов и запоминаячто нарушилась связность для каких-то двух вершин. Значит, когда какое ребро было добавленомы убрали мост. А любой мост принадлежит всем остовным деревьям его компоненты. Противоречие.}}[[Файл:Is_there_xy.jpg|200px|thumb|right|Компонента связности T.]]

Пусть есть <tex>k</tex> рёберТаким образом, если мы удалили ребро не из остовного леса, <tex>i</tex>-е соединяет вершины <tex>v_i</tex> то нам не придётся перестраивать лес и пересчитывать значение <tex>u_i</tex>\mathrm{connected(u, было добавлено запросом <tex>L_i</tex> и удалено запросом <tex>R_iv)}</tex>.

Построим на массиве запросов [[Дерево отрезков. Построение|дерево отрезков]], в каждой его вершине будем хранить список пар. <tex>i</tex>-е рёбро графа нужно добавить на отрезок <tex>[L_iРассмотрим случаи,R_i]</tex>когда мы берём ребро из леса. Это делается аналогично томуТогда необходимо выяснить, как в дереве отрезков происходит добавление на отрезке (процесс описан является ли данное ребро мостом в статье "[[Несогласованные поддеревья. Реализация массового обновления]]")графе, но без <tex>push</tex>: нужно спуститься по дереву от корня и записать пару <tex>u_i,v_i</tex> в вершины дерева отрезковвыполнить соответствующие действия.

Теперь чтобы узнатьПроверим, какие рёбра существуют во время выполнения является ли ребро мостом. У ребра <tex>uv</tex> известен уровень, пусть он равен <tex>i</tex>-го запроса. Попробуем найти другое ребро (<tex>xy</tex>), соединяющее поддеревья <tex>T_u</tex> и <tex>T_v</tex>, достаточно посмотреть на путь от корня дерева отрезков до листа, который соответствует этому запросу {{---}} рёбра, записанные в вершинах этого пути, существуют во время выполнения запросакоторые распалось остовное дерево исследуемой компоненты <tex>T</tex>.

{{Утверждение|statement=Если ребро <tex>xy</tex> существует, то его уровень не больше <tex>i</tex>.|proof=От противного. Пусть <tex>l(xy)= Ответы на запросы ===Обойдём дерево отрезков в глубинуj</tex>, начиная с корнягде <tex>j > i</tex>. Будем поддерживать граф, состоящий из рёбер, которые содержатся на пути от текущей Тогда вершины дерева отрезков до корня. При входе <tex>x</tex> и <tex>y</tex> каким-то образом связаны в вершину добавим в граф рёбра<tex>F_j</tex> (либо непосредственно ребром <tex>xy</tex>, записанные в этой вершинелибо каким-то другим путём). При выходе из вершины нужно откатить граф к состоянию, которое было при входеНо <tex>F_j \subseteq F_i</tex>. Когда мы добираемся до листаЗначит, в граф уже добавлены все рёбра, которые существуют во время выполнения соответствующего запроса, <tex>F_i</tex> между <tex>x</tex> и <tex>y</tex> сохранился путь из рёбер уровня не меньше <tex>j</tex> и только онипоявился другой путь через <tex>uv</tex>. Поэтому если этот лист соответствует запросу третьего типаПриходим к противоречию, его следует выполнить и сохранить ответтак как в <tex>F_i</tex> все компоненты должны быть деревьями.}}

Для поддержания такого графа Чтобы найти <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>xy</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>i</tex>, переходим к пункту <tex>1</tex>;# Если таких рёбер уровня <tex>i</tex> не осталось и <tex>i>0</tex>, рассматриваем уровень на единицу меньший и переходим к пункту <tex>1</tex>;# Если все рёбра просканированы и <tex>i=0</tex>, значение)то <tex>uv</tex> является мостом.

Чтобы откатить состояние СНМ'''Замечание.''' Увеличив уровень ребра на единицу, пройдём по этому массиву в обратном порядке нужно не забыть обновить <tex>G_{i+1}</tex> и присвоим старые значения обратно<tex>F_{i+1}</tex>. Для лучшего понимания ознакомьтесь с приведённой ниже реализацией====Оценка времени работы====Пункт <tex>2</tex> работает за <tex>O(\log^2 n)</tex>, так как после выхода из цикла мы добавляем ребро за <tex>O(\log n)</tex> на каждом уровне, а количество уровней не больше <tex>\log n</tex>.<!--5 сек, тут кажись я права всё-таки, нужен Лёха-->

Нужно заметитьПусть до момента, что эвристику сжатия путей когда мы нашли нужное ребро, мы сделали <tex>S</tex> неудачных сканирований. После каждого такого сканирования нам приходится добавлять новые рёбра в этом случае применять не следует. Эта эвристика улучшает асимптотическое время работы<tex>G_{i+1}</tex>, но это время работы не истинное, а амортизированное. Из-за наличия откатов к предыдущим состояниям эта эвристика не даст выигрышачто стоит <tex>O(\log n)</tex>. СНМ с ранговой эвристикой же работает за Получаем сложность удаления одного ребра <tex>O(\log^2{n}+S\cdot\log n)</tex> на запрос истинно.<!--- Возможно, мы удалим мост, но это уже другая история, да и она всяко лучше логарифмов в квадрате... --->

Запоминание изменений Выразим сложность одной операции <tex>\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+\log n\cdot\log n\cdot m)</tex>, если оно истинное, а не амортизированное. Действительно: пусть в СНМ произошло так как уровень ребра <tex>rm</tex> изменений. Каждое из них будет один раз занесено в массив и один раз отмененорос максимум до <tex>\log n</tex>. Значит, запись в массив и откаты работают за Отсюда суммарная сложность всех запросов равна <tex>O(\Theta(rlog^2{n}\cdot m)</tex>. Но и сами изменения заняли , а для одного запроса мы решаем задачу за <tex>O(\Theta(rlog^2{n})</tex> времени, значит, откаты не увеличили асимптотическое время работы.

'''function''' <tex>\mathrm{remove}</tex>('''Node''' u, '''Node''' v): '''Edge''' e =<tex>\langle </tex>u, v<tex>\rangle</tex> '''for''' i = e.level '''downto''' 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)---> '''Edge''' e2 '''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> '''for''' j =i '''downto''' 0# Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за <tex>F_j</tex> = <tex>F_j</tex> <tex>\cup</tex>Oe2<!---insert(\log n)<tex>F_i</tex>, e2)--> '''return''' '''else''' e2.level++ <tex>G_{i+1}</tex> = <tex>G_{i+1}</tex> <tex>\cup</tex> e2<!---insert(<tex>F_i</tex>, e2)-->