1632
правки
Изменения
м
== Динамическая связность в лесах ==
Если задача построена так, что в графе нет и не может быть циклов, то её можно решить при помощи [[Деревья Эйлерова обхода|деревьев эйлерова обхода]]. Нужно только... [[Dynamic connectivity|читать продолжение в источнике]].
Время работы для упрощённой задачи {{---}} <tex>O(\log n)</tex>.
== Обобщение задачи о динамической связности ==
А это уже сложнее)0)
=== Псевдокод ===
<!--== Алгоритм ==
=== Время работы === // i think i'll tell it
== Частные случаи == // hahaha there is only one specific kind))0)
=== Деревья === //yes
=== Планарные графы === //da xz chtobi o nih govorit' ischo... -->
<!--
== Алгоритм ==
Время работы такого решения: ===Добавление ребра===Чтобы разобраться с тем, как изменится граф и остовный лес при добавлении и удалении ребра, введём функцию <tex>Ol(m e):E{\cdot rightarrow}[0;\alpha (log n))]</tex> и назовём её ''уровнем ребра'' <tex>e</tex>. Уровни ребра можно распределить любым способом, где но для всех <tex> i </tex> должно выполняться следующее свойство: размер каждой компоненты связности <tex>\alphaG_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>k0</tex> рёбер, . В этом случае изменится только <tex>iG_0</tex>-е соединяет вершины , так как в остальные подграфы <tex>v_iG_i</tex> и рёбра нулевого уровня не входят. После вставки нового ребра нам нужно проверить, были ли вершины <tex>u_iu</tex>, было добавлено запросом и <tex>L_iv</tex> в одной компоненте связности до того, как мы вставили ребро. Если они лежали в разных компонентах, то необходимо новое ребро добавить и удалено запросом в остовный лес <tex>R_iF_0</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>iG_0</tex><tex>\cup</tex> e<!-е рёбро графа нужно добавить на отрезок --insert(<tex>[L_i,R_i]G_0</tex>. Это делается аналогично тому, как в дереве отрезков происходит добавление на отрезке e)--> '''if not''' <tex>\mathrm{connected(процесс описан в статье "[[Несогласованные поддеревья. Реализация массового обновления]]"u,v), но без }</tex> <tex>F_0</tex> = <tex>F_0</tex> <tex>push\cup</tex>: нужно спуститься по дереву от корня и записать пару e<!---insert(<tex>u_i,v_iF_0</tex> в вершины дерева отрезков., e)-->
Теперь чтобы узнать===Удаление ребра==={{Утверждение|statement=Если ребро, которое мы хотим удалить, какие рёбра существуют во время выполнения <tex>i</tex>-го запросане принадлежит остовному лесу, достаточно посмотреть на путь то связность между любой парой вершин сохранится.|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> все компоненты должны быть деревьями.}}
=== СНМ с откатами ===Для тогоЧтобы найти <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>rG_{i+1}</tex> изменений. Каждое из них будет один раз занесено в массив и один раз отменено. Значит, запись в массив и откаты работают за что стоит <tex>O(\Theta(rlog n)</tex>. Но и сами изменения заняли Получаем сложность удаления одного ребра <tex>O(\Theta(rlog^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>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): '''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>Oe<!---delete(<tex>G_i</tex>, e)---> <tex>F_i</tex> = <tex>F_i\log nsetminus</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># Планарные графы. D. Eppstein доказал, что для планарных графов мы также можем выполнять запросы за '''if''' y <tex>\in T_v</tex> '''for''' j = i '''downto''' 0 <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)-->
* [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> в одной компоненте связности.
}}
== Динамическая связность в лесах ==
Если задача такова, что в графе нет и не может быть циклов, то она сводится к задаче о связности в [[Деревья Эйлерова обхода|деревьях эйлерова обхода]]. Время работы каждого запроса для упрощённой задачи {{---}} <tex>O(\log n)</tex>, где <tex>n</tex> {{---}} количество вершин в графе.
== Обобщение задачи для произвольных графов ==
Существуют задачи, в которых граф не обязательно на протяжении нашей работы после каждой операции добавления ребра остаётся лесом. Для решения таких задач в каждой компоненте связности выделим [[Остовные деревья: определения, лемма о безопасном ребре|остовные деревья]], которые образуют остовный лес.
[[Файл:Graph.jpg|530px|thumb|left|Граф]] [[Файл:Spanforest.jpg|530px|thumb|right|Остовный лес в графе]]
=== Решение упрощённой задачи Проверка связности======= Задача без удалений рёбер ====Если нет удалений Граф и его остовный лес {{---}} одно и то же с точки зрения связности. Поэтому проверка связности в графе сводится к проверке связности в остовном лесе и решается за <tex>O(\log n)</tex>.<!--Добавление рёбер, задачу можно решить при помощи рассмотреть с точки зрения [[СНМ (реализация с помощью леса корневых деревьев)|системы непересекающихся множеств]], такой запрос будет работать за <tex>O(\log n)</tex>. Каждая компонента Операция проверки сводится к проверке связности {{---}} одно множество в СНМ, остовном лесе и при добавлении рёбер они объединяютсяработает также за <tex>O(\log n)</tex>.-->
Очевидно, что <tex>G_{\log n} \subseteq G_{\log n-1} \subseteq \ldots \subseteq G_1 \subseteq G_0 === Построение дерева отрезков ===Рассмотрим массив запросовG</tex>. Каждое ребро Выделим в графе существует на некотором отрезке запросов: начиная с запроса добавления и заканчивая запросом удаления (либо концом запросов, если ребро не было удалено). Для каждого ребра можно найти этот отрезокграфах остовные леса таким образом, пройдя по массиву запросов и запоминаячто <tex>F_{\log n} \subseteq F_{\log n-1} \subseteq \ldots \subseteq F_1 \subseteq F_0</tex>, когда какое ребро было добавленогде <tex>F_i</tex> {{---}} остовный лес графа <tex>G_i</tex>.
=== Частные случаи =Псевдокод====
== См. также ==
== Источники информации ==
* [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Лекции {{---}} Академия Яндекса]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Связность в графах]]
