1632
правки
Изменения
м
Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>.
написать про уровни и остовные леса <tex>\mathrm{navernoe.}</tex>
<!-- === Псевдокод === xz -->
<!--== Алгоритм ==
=== Время работы === // i think i'll tell it
== Частные случаи == // hahaha there is only one specific kind))0)
=== Деревья === //yes
=== Планарные графы === //da xz chtobi o nih govorit' ischo... -->
<!--Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Для решения таких задач в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес. [[Файл:Graph.jpg|530px|thumb|left|Граф]] [[Файл:Spanforest.jpg|530px|thumb|right|Остовный лес в графе]] == Алгоритм ==
=== Решение упрощённой задачи ===
==== Задача без удалений рёбер ====
Если нет удалений рёбер, задачу можно решить при помощи [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]]. Каждая компонента связности {{---}} одно множество в СНМ, и при добавлении рёбер они объединяются.
Время работы такого решения: <tex>O(m \cdot \alpha (n))</tex>, где <tex>\alpha</tex> {{---}} [[СНМ (реализация с помощью леса корневых деревьев)#Функция Аккермана|обратная функция Аккермана]].
Пусть есть ===Добавление ребра===Чтобы разобраться с тем, как изменится граф и остовный лес при добавлении и удалении ребра, введём функцию <tex>l(e):E{\rightarrow}[0;\log n]</tex> и назовём её ''уровнем ребра'' <tex>ke</tex> рёбер. Уровни ребра можно распределить любым способом, но для всех <tex>i</tex>-е соединяет вершины должно выполняться следующее свойство: размер каждой компоненты связности <tex>v_iG_i</tex> и не превосходит <tex>u_i\dfrac{n}{2^i}</tex>, было добавлено запросом . Здесь графы <tex>L_iG_i</tex> и удалено запросом определяются так: <tex>R_iG_i=\langle V, E\rangle: \{e \in E \mid l(e) \geqslant i\}</tex>.
Построим на массиве запросов [[Дерево отрезков. Построение|дерево отрезков]]Очевидно, в каждой его вершине будем хранить список пар. что <tex>iG_{\log n} \subseteq G_{\log n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0 = G</tex>-е рёбро графа нужно добавить на отрезок . Выделим в графах остовные леса таким образом, что <tex>[L_i,R_i]F_{\log n} \subseteq F_{\log n-1} \subseteq \ldots \subseteq F_1 \subseteq F_0</tex>. Это делается аналогично тому, как в дереве отрезков происходит добавление на отрезке (процесс описан в статье "[[Несогласованные поддеревья. Реализация массового обновления]]"), но без где <tex>pushF_i</tex>: нужно спуститься по дереву от корня и записать пару {{---}} остовный лес графа <tex>u_i,v_iG_i</tex> в вершины дерева отрезков.
Теперь чтобы узнатьУдобнее всего новому ребру давать уровень <tex>0</tex>. В этом случае изменится только <tex>G_0</tex>, какие так как в остальные подграфы <tex>G_i</tex> рёбра существуют во время выполнения нулевого уровня не входят. После вставки нового ребра нам нужно проверить, были ли вершины <tex>iu</tex>-го запроса, достаточно посмотреть на путь от корня дерева отрезков и <tex>v</tex> в одной компоненте связности до листатого, который соответствует этому запросу {{---}} рёбракак мы вставили ребро. Если они лежали в разных компонентах, записанные то необходимо новое ребро добавить и в вершинах этого пути, существуют во время выполнения запросаостовный лес <tex>F_0</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> времени, значит, откаты не увеличили асимптотическое время работы.
Вместо описанного способа откатывания состояния СНМ можно использовать [[Персистентные структуры данных|персистентный]] СНМ, но этот вариант сложнее и имеет меньшую эффективность. <!- если бы ещё псевдокод и что-то там ещё, я забыла ->====Псевдокод====
* [http://se.math.spbu.ru/SE/diploma/2012/s/Kopeliovich_diploma.pdf http://se.math.spbu.ru/SE/diploma/2012/s/Kopeliovich_diploma.pdf]
rollbackEdits.php mass rollback
{{Задача
|definition = Есть [[Основные_определения:_граф,_ребро,_вершина,_степень,_петля,_путь,_цикл#Неориентированные_графы|неориентированный граф]] из <tex>n</tex> вершин, изначально не содержащий рёбер. Требуется обработать <tex>m</tex> запросов трёх типов:
* <tex>\mathrm{add(u,v)}</tex> {{---}} добавить ребро между вершинами <tex>u</tex> и <tex>v</tex>,;* <tex>\mathrm{remove(u,v)}</tex> {{---}} удалить ребро между вершинами <tex>u</tex> и <tex>v</tex>,;
* <tex>\mathrm{connected(u,v)}</tex> {{---}} проверить, лежат ли вершины <tex>u</tex> и <tex>v</tex> в одной компоненте связности.
}}
== Динамическая связность в лесах ==
Если задача такова, что в графе нет и не может быть циклов, то её можно решить при помощи она сводится к задаче о связности в [[Деревья Эйлерова обхода|деревьев деревьях эйлерова обхода]]. Нужно только... [[Dynamic connectivity|читать продолжение Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>, где <tex>n</tex> {{---}} количество вершин в источнике]]графе.
== Обобщение задачи для произвольных графов ==
=== Построение дерева отрезков Проверка связности===Рассмотрим массив запросовГраф и его остовный лес {{---}} одно и то же с точки зрения связности. Каждое ребро Поэтому проверка связности в графе существует на некотором отрезке запросов: начиная с запроса добавления сводится к проверке связности в остовном лесе и заканчивая запросом удаления решается за <tex>O(либо концом запросов, если ребро не было удалено\log n)</tex>. Для каждого ребра <!--Добавление рёбер можно найти этот отрезокрассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], пройдя по массиву запросов такой запрос будет работать за <tex>O(\log n)</tex>. Операция проверки сводится к проверке связности в остовном лесе и запоминая, когда какое ребро было добавленоработает также за <tex>O(\log n)</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)--> ===Удаление ребра===Обойдём дерево отрезков в глубину{{Утверждение|statement=Если ребро, которое мы хотим удалить, не принадлежит остовному лесу, начиная с корнято связность между любой парой вершин сохранится.|proof=Докажем от противного. Будем поддерживать графДопустим, состоящий из рёберчто это не так. Понятно, которые содержатся на что при разрезании ребра нового пути от текущей вершины дерева отрезков до корнямежду вершинами не появится.Предположим, что нарушилась связность для каких-то двух вершин. При входе в вершину добавим в граф рёбраЗначит, записанные в этой вершинемы убрали мост. А любой мост принадлежит всем остовным деревьям его компоненты. Противоречие.}}[[Файл:Is_there_xy.jpg|200px|thumb|right|Компонента связности T. При выходе ]] Таким образом, если мы удалили ребро не из вершины нужно откатить граф к состояниюостовного леса, то нам не придётся перестраивать лес и пересчитывать значение <tex>\mathrm{connected(u, которое было при входеv)}</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> все компоненты должны быть деревьями.}}
'''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)-->
== См. также ==
== Источники информации ==
* [https://en.wikipedia.org/wiki/Dynamic_connectivity Dynamic connectivity {{---}} Википедия]
* [http://coursesnumeralis.csail.mit.eduru/6.851algoritmyi-i-strukturyi-dannyih-poiska-dinamicheskaya-svyaznost-v-grafah-babenko-maksim/spring12/scribe/L20.pdf http://courses.csail.mit.edu/6.851/spring12/scribe/L20.pdfЛекции {{---}} Академия Яндекса]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Связность в графах]]
